由一个小学五年级暑假作业想到的算法问题

从9到1 ，9个数， 相邻的两个数可以连在一起， 只使用加 和 减号连接， 使这些函数加起来的总和等于100； 例如 98 ＋ 7 - 6 + 5 - 4 ＋ 3 - 2 - 1 ＝ 100.
当然 可以由98 76 等等多过两位数， 本来是找几种， 要问的是看有多少种这样的组合？ 大家怎么写代码啊？

krh2001(边城浪子)

#include <stdio.h>

int Compr(const char* exps , int first, int n)
{
int count = 0;
int i, part, m;
char  buffer[128];

if(n == 0)
{
if(first == 100)
{
printf("%s = 100\n", exps);
return 1;
}
}
else
{
for(i = 1; i <= n; i++) // 取几位数
{
part = 0;
for(m = 0; m < i; m++)
part = part * 10 + (n - m);
sprintf(buffer, "%s + %d", exps, part);
count += Compr(buffer, first + part, n - i);
sprintf(buffer, "%s - %d", exps, part);
count += Compr(buffer, first - part, n - i);
}
}
return count;
}

int ComprFirst(int n)
{
int count = 0;
int i, part, m;
char  buffer[128];

for(i = 1; i <= n; i++) // 取几位数
{
part = 0;
for(m = 0; m < i; m++)
part = part * 10 + (n - m);
sprintf(buffer, "%d", part);
count += Compr(buffer, part, n - i);
}
return count;
}

int main()
{
int count;
count = ComprFirst(9);
printf(" Total : %d\n", count);
return 0;
}

 

结果:

9 + 8 + 76 + 5 + 4 - 3 + 2 - 1 = 100
9 + 8 + 76 + 5 - 4 + 3 + 2 + 1 = 100
9 - 8 + 7 + 65 - 4 + 32 - 1 = 100
9 - 8 + 76 - 5 + 4 + 3 + 21 = 100
9 - 8 + 76 + 54 - 32 + 1 = 100
98 + 7 + 6 - 5 - 4 - 3 + 2 - 1 = 100
98 + 7 - 6 + 5 - 4 + 3 - 2 - 1 = 100
98 + 7 - 6 + 5 - 4 - 3 + 2 + 1 = 100
98 + 7 - 6 - 5 + 4 + 3 - 2 + 1 = 100
98 - 7 + 6 + 5 + 4 - 3 - 2 - 1 = 100
98 - 7 + 6 + 5 - 4 + 3 - 2 + 1 = 100
98 - 7 + 6 - 5 + 4 + 3 + 2 - 1 = 100
98 - 7 - 6 + 5 + 4 + 3 + 2 + 1 = 100
98 - 7 - 6 - 5 - 4 + 3 + 21 = 100
98 - 76 + 54 + 3 + 21 = 100
 Total : 15
Press any key to continue