Join 107,400 C++ Programmers for FREE! Ask your question and get quick answers from experts. There are 1,159 online right now! We've got more than 500 tutorials and 2,000 snippets. Join and find out why Dream.In.Code is the #1 programming help community on the internet! Registration is fast and FREE... Join Now!
Every so often I read an assignment on here that I find interesting as a challenge.
One of the threads has a questions similar to my current challenge:
Write a program to find the maximum value of an arbitrary number of elements (integers if you must) without the use of the if-statement.
Now, one could use vargs and loop though using the max() function to find the max... but I wanted to challenge myself. Here was my first solution -- not the best but I like it for a first attempt.
CODE
#include <iostream> #include <algorithm> using namespace std;
/* * The challange: find the maximum value of a arbitraty list of values wihtout * the use of the conditional-control strucutes. */ template <class T> class FindMax { private: T currentMax; int state; //states 0 = no data; non-zero = current max stored. public: FindMax() : state(0) { }
Either way, it is the same sort of result that is much easier and more efficient then that of a class definition and its members, and it is performing the same task. In the fine words of Chris, I'm not sayin', I'm just sayin'.
In theory, if you can find the maximum of two numbers without an if, then you can do it for any. The problem is, what do you class as an 'if'? I would rule out the ternary operator, since that's just an abbreviated if/else. Also, the std::max function may use an if or ternary operator behind-the-scenes. - And of course, there's this "while" trick to emulate an if statement (Which can also be mimicked using 'for' too)
CODE
int max = 5; int num = 6; while( max < num ) { max = num; break; }
IMHO, that's cheating too, but it depends on the rules. and obviously there needs to be some kind of selection somewhere (even if its loop-based, or done by the compiler), computers can't make decisions based purely on sequence.
Also, what are the constraints by which the numbers must be stored or retrieved? must the numbers be known at compile time? Must they be retrieved from the user/a file? may they be stored in a container? If so, may the container be modified?
This would be one of my suggestions, although it has the same problem as std::max, being that sort() will do all kinds of 'if' statements behind the scenes
It depends on the rules - whether the challenge is one for finding unorthodox ways to use high-level language constructs (from a language point of view, an if is different to while, which is different to for, etc), or whether the challenge is one of machine instruction constructs. I assume its the former, since to perform selection, whilst ruling out all possible machine constructs which allow it to perform selection, is paradoxical (there's also the switch/case statement which could also be classed as 'cheating' along with the while/for statement)
This post has been edited by Bench: 16 Feb, 2008 - 05:11 AM
This idea just came to me - it escapes from the usual program-flow selection, and goes with boolean logic for object/variable selection. (Though you could still argue that its like the ternary 'if' in disguise)
CODE
#include <iostream>
int greatest( int num1, int num2 ) { int nums[2] = { 0 }; bool num1pos = ( num1 < num2 ); nums[ num1pos ] = num1; nums[ !num1pos ] = num2; return nums[0]; }
Neat class. Seriously, I never got into << overloads, it a nice example of seeing them in action. Like the template to, can use it for anything.
Of course, what constitutes an "if" is subjective. Bench showed a while construct. No if, but still conditional. If you choose to call another function and declare a win, you've simple deferred your if.
The only thing really required is a single functioning max, from which you can derive the rest. Here's my solution.
I myself do not consider the Ternary operation a version of the if-statement. I is an operator -- an out of paradigm operator not a control structure.
I allowed the use of max since (AFAIK) it used the conditional operator not the if-statement. Personally I would also say that the use of assembly language to write your own if statement was perfectly valid (but I am a softy).
Here is my second attempt. This one uses the variable arguments approach:
CODE
template <class T> class GetMax { private: T currentMax; int state; public: GetMax() : state(0) { } T operator()(const T& in) { currentMax = std::max(state ? currentMax : in , in); state = 1; }
T operator()() { return currentMax; state = 0; } };
template <class T, int len> T maximum(T first, ...) { va_list args; va_start(args, first); GetMax<T> gm; gm(first); int length = len - 1; //One is used up by "first" for (; length > 0; --length) { gm(va_arg(args, T)); } va_end(args); return gm(); }
int main() { int a = maximum<int, 6>(55, 1, 2, 10, 37, 6); cout << a << endl; system("Pause"); return 0; }
This one is very much like the last one, but at least it looks more "function like" than using the "<<" operator. Now off to read all the other solutions -- I really didn't expect so much interest.
RogerB -- That works of course -- I myself was trying to avoid the use of the array argument but I like the simplicity.
Bench -- I like the while() trick. See this is exactly why I posted this topic. To see what I can learn from other peoples solutions.
BENCH!!! That is awesome! I was trying to think of a bit-twiddling way to find the max but I had not been using the full potential of the language in my thinking! I don't think this ever would have occurred to me. -- mostly because I never assume that true == 1... For the bool I believe it always does. Well done!
I suppose I could use a similar trick to avoid having to use the state variable in my class.
Stealing shamelessly from Bench here is my newest edition. Now all I have to do is remove the use of the for loop and I am truly free of conditional control structures.
CODE
#include <iostream> #include <iostream> #include <cstdarg> using namespace std;
/* * The challange: find the maximum value of a arbitraty list of values wihtout * the use of the conditional-control strucutes. * NOTE: The use of the chooseOne<T>() and greatest<T>() functions were inspired * by Bench's int greatest(int, int) function use arrays to resolve a binary condition. */
template <class T> T chooseOne(T first, T second, bool choice) { T order[2]; order[0] = first; order[1] = second; return order[choice]; }
template <class T> T greatest( T first, T second ) { return chooseOne<T>(first, second, (first < second)); //if (f < s) true = 1, return s, else return f }
template <class T> class GetMax { private: T currentMax; int state; public: GetMax() : state(0) { } T operator()(const T& in) { currentMax = greatest<T>(chooseOne<T>(in, currentMax, state) , in); state = 1; }
T operator()() { return currentMax; state = 0; } };
template <class T, int len> T maximum(T first, ...) { va_list args; va_start(args, first); GetMax<T> gm; gm(first); int length = len - 1; //One is used up by "first" for (; length > 0; --length) { gm(va_arg(args, T)); } va_end(args); return gm(); }
int main() { int a = maximum<int, 6>(55, 1, 65, 10, 37, 6); cout << a << endl; system("Pause"); return 0; }
I had to check myself in TC++PL whether or not (true == 1) was standard, or just a convention - as far as I can tell, its standard, at least for C++ '03.
As for eliminating the control loop - I would try a recursive solution - using your 'chooseOne' function with 'T' as a function pointer. one of those functions would be a do-nothing function, to terminate the recursion, the other would point to the current function as per the usual recursion idiom. (Similar to the way in which template metaprogramming loops are usually implemented) - I doubt whether its very elegant. I can't see exactly how it could fit into that program either, it may take some restructuring, but its the only method of looping I can think of, which wouldn't involve a control structure somewhere.
This certainly turned out to be an interesting little problem though
This post has been edited by Bench: 16 Feb, 2008 - 01:57 PM
16 Feb, 2008 - 02:03 AM
|