Author |
Topic: 1 TO 100 and 100 to 1 (Read 1866 times) |
|
raghuram
Newbie
Gender: 
Posts: 2
|
 |
1 TO 100 and 100 to 1
« on: Jan 11th, 2004, 9:39am » |
 Quote  Modify
|
Try this:
Write a C++ program to print numbers from 1 to 100 and then 100 to 1 without using using loops, conditions like "if","else" etc.
Remember that recursion is not a solution since we would be using 'if'.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 TO 100 and 100 to 1
« Reply #1 on: Jan 11th, 2004, 10:29am » |
Quote Modify
|
heh.. well..
I'll keep it short, just fill in the blanks yourself 
cout << 1 << 2 << 3 .... << 99 << 100
<< 100 << 99 << .... << 3 << 2 << 1 ;
You could also do something recursive, without if's by using the preprocessor, and templates..
(I'd have to brush up on that material first though..)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 TO 100 and 100 to 1
« Reply #2 on: Jan 11th, 2004, 11:11am » |
Quote Modify
|
Code:#include <iostream>
template<int i>
class P
{
public:
P()
{
std::cout << i << std::endl;
P<i+1>();
std::cout << i << std::endl;
}
};
class P<100>
{
public:
P()
{
std::cout << 100 << std::endl;
std::cout << 100 << std::endl;
}
};
int main()
{
P<1>();
} |
|
compile with the option -ftemplate-depth-100 if your template depth isn't default 100 or greater
I also tried with a function template, but for some reason it won't work. So function objects it is then..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 TO 100 and 100 to 1
« Reply #3 on: Jan 11th, 2004, 11:22am » |
Quote Modify
|
I don't know why I make it so difficult for myself.. This is much easier..
Code:int p(int i, int j)
{
std::cout << i << std::endl;
(i-j) && p(i+1,j);
std::cout << i << std::endl;
}
int main()
{
p(1,100);
}
|
|
Who needs IFs anyway..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: 1 TO 100 and 100 to 1
« Reply #4 on: Jan 14th, 2004, 12:44am » |
Quote Modify
|
on Jan 11th, 2004, 11:22am, towr wrote: Code:int p(int i, int j)
{
std::cout << i << std::endl;
(i-j) && p(i+1,j);
std::cout << i << std::endl;
}
int main()
{
p(1,100);
} |
|
|
|
towr, I don't see why this code even works  :
What does this line ('(i-j) && p(i+1,j);') do? and why will the program stop when it reaches to 100 ?
Waiting for your reply...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 TO 100 and 100 to 1
« Reply #5 on: Jan 14th, 2004, 2:13am » |
Quote Modify
|
C and C++ don't really distinguish between booleans and integers, and they are lazy evaluators.
So on encountering a logical AND they will evaluate the first argument, and if it is false than the whole expression must be false, regardless of the second argument. Which is why, being lazy, they don't evaluate it.
In the end A&&B is equivalent if(A) B;
I suppose I could have used an implication as well (!A || B) as there is no difference here unless you do anything with the return value
To be honest I'd expected the compiler to at least want the function to explicitly return some value. But probably there's an implicit one, whatever it is though, it too is irrelevant, since the value of the expression (i-j)&&p(i+1,j) isn't used. So wether it be true or false, who cares..
One other thing to note
Unlike the arguments of a function, which may not be evaluated in the order you wrote them (moreso, they are usually evaluated in reverse order, try some f(i,i++) to check it out), operands of logical operators are guaranteed to be evaluated from left to right (unless they're irrelevant). Which you can neatly abuse in some cases.
In the end though, I think it is computationally more efficient to use an if-statement. At best the compiler will recognize A&&B is the same. Though to be sure I ought to look at the assembly code it compiles to..
|
| « Last Edit: Jan 14th, 2004, 2:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 1 TO 100 and 100 to 1
« Reply #6 on: Jan 14th, 2004, 2:18am » |
Quote Modify
|
I hope towr doesn't mind me replying for him.
Dudidu,
the logic is very simple(not to mention cute and innovative as well),
the statement (i-j) && p(i+1,j) is a (true-false statement).
The next statement after this will be executed if and only if the truth value of this statement is determined.
Note that as long as (i-j)!=0 , the function p(i+1,j) will be called so that its value could be determined. As soon as (i-j) becomes zero , the compiler proceeds ahead without checking the value of p(i+1,j). (Smart trick this one!!)
What happens next is potential backtracking... to print 100 to 1.
This is a beautiful code towr!!!!! 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 TO 100 and 100 to 1
« Reply #7 on: Jan 14th, 2004, 2:26am » |
Quote Modify
|
on Jan 14th, 2004, 2:18am, TenaliRaman wrote:| I hope towr doesn't mind me replying for him. |
|
heh, nor after me
Quote:| This is a beautiful code towr!!!!! |
|
Thanx..
It's not that special though, these are tricks most people learn if they ever have to write source codes that are as short as possible, which goes for many players in a MOO (where you generally have very limited quota, like 10 or 50k to start with).
|
| « Last Edit: Jan 14th, 2004, 2:29am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: 1 TO 100 and 100 to 1
« Reply #8 on: Jan 14th, 2004, 2:35am » |
Quote Modify
|
on Jan 14th, 2004, 2:18am, TenaliRaman wrote:| the logic is very simple... |
|
TenaliRaman Thx,
I didn't pay enough attention to think how '(i-j) && p(i+1,j)' is evaluated  .
P.S. - Very Nice !!!, towr.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1 TO 100 and 100 to 1
« Reply #9 on: Jan 14th, 2004, 4:16am » |
Quote Modify
|
The easiest way to check towr's last solution is to compile and run it - it works.
What I would like to point your attention to - is that the same code may be trivially modified to get a program in C. It also works perfectly well. But raghuram asked for the C++ code... Was it written deliberately to indicate that the C code won't do that - let the author speak. And also:
Quote:| Remember that recursion is not a solution since we would be using 'if'. |
|
I tend to agree, because - even if we don't see 'if' at the C++ level - we will see its equivalent at one or more intermidiate levels.
In that sense, the first towr's solution (using templates) is more correct, since it doesn't use any run time recursion. By the way, when I presented this riddle to my friend (he is considered here as C++ guru), he immediately gave the template solution.
Nice puzzle, raghuram!
|
|
IP Logged |
|
|
|
raghuram
Newbie
Gender:
Posts: 2
|
|
Re: 1 TO 100 and 100 to 1
« Reply #10 on: Jan 15th, 2004, 8:44am » |
Quote Modify
|
Barukh, You guessed it right. I deliberately meant C++ as I was expecting a solution without recursion. There's indeed a solution without recursion and such a solution works only in C++. This solution does not need any templates at all.The solution given by Towr is really good but it can be done using an equivalent 'C' code as well.
Here's a big hint:
Think about constructors and destructors.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: 1 TO 100 and 100 to 1
« Reply #11 on: Jan 15th, 2004, 9:38am » |
Quote Modify
|
Raghuram,
I personally appreciate innovative answers and i feel both of towr's solution were well within the specified rules of the problem. (Note that it said not to use 'if' and not that the problem mustn't be done using recursion).
Anyways,
this is your expected answer i feel,
Code:
#include<iostream.h>
int count=0;
class dummy
{
public:
dummy()
{
count++;
cout<<count;
}
~dummy()
{
cout<<count;
count--;
}
};
int main()
{
dummy d[100];
return 0;
}
|
|
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 1 TO 100 and 100 to 1
« Reply #12 on: Jan 15th, 2004, 10:10am » |
Quote Modify
|
[edit]Gah, a half an hour gap, and I don't notice someone else's beaten me to the punch..
ah well..[/edit]
Well, maybe this suits you better..
Though I'm not thouroughly convinced it works in every flavour C++ (I have some doubts about the order in which the destructors are called, and also about how the vector is filled)
But it works in g++ 3.0
(of course there's a hidden loop here, and probably in every solution except the first I gave, which is simply explicitly throwing all the number to the out stream)
Code:#include <iostream>
#include <vector>
class P
{
static int c;
int d;
public:
P(int i)
:d(c++)
{ std::cout << d << std::endl; }
P(P const &_)
:d(c++)
{ std::cout << d << std::endl; }
~P()
{ std::cout << (101-d) << std::endl; }
};
int P::c = 1;
int main()
{
std::vector<P> p(99, P(1));
}
|
|
I'll go see if I can find any other solutions..
|
| « Last Edit: Jan 15th, 2004, 10:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: 1 TO 100 and 100 to 1
« Reply #13 on: Jan 19th, 2004, 12:03am » |
Quote Modify
|
Here's another solution which doesn't have this destructor order problem.
Code:#include <cstdlib>
#include <iostream>
void F_pf(int n) { cout << n << endl; }
void F_pb(int n) { cout << (201-n) << endl; }
void F_ex(int n) { exit(0); }
typedef void (*pF) (int);
pF FP[3] = {F_pf, F_pb, F_ex}; // Pointers to functions
struct T {
static int n;
T(void)
{
FP[ (n-1) / 100 ]( n );
n++;
T t;
}
};
int T::n = 1;
main()
{
T t;
}
|
|
Although implemented as a C++ program, it may be easily re-written in C using recursion - and still (IMHO) without using loops and conditional statements!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print