Re: Make 100 by using + - x / and 1~9

In article <2007102518411575249-kirakun@earthlinknet>,
Kira Yamato <kirakun@xxxxxxxxxxxxx> wrote:

On 2007-10-25 18:35:42 -0400, Kira Yamato <kirakun@xxxxxxxxxxxxx> said:

On 2007-10-25 17:22:50 -0400, 131208@xxxxxxxxx said:

1 ( ) 2 ( ) 3 ( ) 4 ( ) 5 ( ) 6 ( ) 7 ( ) 8 ( ) 9 = 100

( ) only can be among +, - , x, /

The empty space is not allowed.

How many solutions are there?

Ooops. My code had a "off-by-1" bug. The correct output should be

1*2*3*4+5+6+7*8+9=100
1-2+3*4*5+6*7+8-9=100
1-2+3*4*5-6+7*8-9=100
1+2+3+4+5+6+7+8*9=100
1*2*3+4+5+6+7+8*9=100
1-2*3+4*5+6+7+8*9=100
1+2*3+4*5-6+7+8*9=100
1-2*3-4+5*6+7+8*9=100
1+2-3*4+5*6+7+8*9=100
1+2*3*4*5/6+7+8*9=100
1*2*3*4+5+6-7+8*9=100
1-2*3-4-5+6*7+8*9=100
1+2-3*4-5+6*7+8*9=100
1+2+3-4*5+6*7+8*9=100
1*2*3-4*5+6*7+8*9=100

Source code: C++
#include <iostream>

int main()
{
char ops[] = "+-*/";
for(long i = 0; i<= 4*4*4*4*4*4*4*4-1; i++)
{
long j = i;
std::cout << "1";
for(int k = 2; k <= 9; k++)
{
std::cout << ops[j & 3] << k;
j>>=2;
}
std::cout << endl;
}
return 0;
}

[...]

Here is a C program that generates the
expressions using a Gray code.
The Gray code expression generator runs in 0.1 sec,
and the above expression generator runs in 1.8 sec.

A Gray code is generally useful and fast for
generating consecutive subsets of a set.
An n-bit Gray code gives a Hamilton walk on an n-cube.

------------------
#include <stdio.h>

#define GCL 16

int main (void)
{
char expr[] = "1+2+3+4+5+6+7+8+9";
int Gray[GCL];
int idx;

for(idx = 0; idx < GCL; ++idx) Gray[idx] = 0;

for(idx = GCL;;)
{
puts(expr);

if(idx == 0) while(Gray[idx++] == 0);
else idx = 0;
if(idx >= GCL) break;

Gray[idx] ^= 0x01;
switch(expr[idx | 0x01])
{
case '+': expr[idx | 0x01] = '-'; break;
case '-': expr[idx | 0x01] = '*'; break;
case '*': expr[idx | 0x01] = '/'; break;
case '/': expr[idx | 0x01] = '+'; break;
default: break;
}
}
return 0;
} /* main */

#undef GCL

--
Michael Press
.