c语言123456789=100编程思想

来源：百度知道 编辑：UC知道 时间：2024/07/05 05:20:21
题目是:在这九个数中间添加+,-符号，使得1 2 3 4 5 6 7 8 9 ＝100成立.
现已有完整程序,但是算法思想不理解,请高手针对下面程序给出详细算法思想.好的话可以追加分数.
main()
{
char op,str[80];
int i,j,s,n,m,ptr;
for (i=0;i<=6561;i++) /*i是每一种枚举的情况，把i分解为八位3进制数，每一位表示每一个位置的符号*/
{
s=0; /*该方式下的和*/
m=1; /*作操作数*/
n=i; /*获取i在3进制下的每一位会破坏i，所以借用变量n来获取*/
op='+'; /*第一次操作方式为+*/
ptr=0; /*指针用来记录运算过程*/
str[ptr++]='1'; /*首先记录一个1*/
for (j=2;j<=9;j++) /*八次循环，每次的下一个操作数是j*/
{
if (n%3) /*3进制下的第j-1位数，如果不是0，则要完成先前的操作*/
{
if (op=='+') s+=m; else s-=m;m=j;
}
switch(n%3) /*根据这一位的情况进行处理*/
{
case 0:m=m*10+j;break;
case 1:op='+';break;
case 2:op='-';break;
}
if (n%3) str[ptr++]=op; /*记录运算模式*/
str[ptr++]='0'+j;
n/=3;
}
if (op=='+') s+=m; else s-=m;
str[ptr]='\0';
if (s==100) printf("FO

就是个深度优先搜索。

枚举所有符号可能添加的情况。

{
s=0; /*该方式下的和*/
m=1; /*作操作数*/
n=i; /*获取i在3进制下的每一位会破坏i，所以借用变量n来获取*/
op='+'; /*第一次操作方式为+*/
ptr=0; /*指针用来记录运算过程*/
str[ptr++]='1'; /*首先记录一个1*/
for (j=2;j<=9;j++) /*八次循环，每次的下一个操作数是j*/
{
if (n%3) /*3进制下的第j-1位数，如果不是0，则要完成先前的操作*/
{
if (op=='+') s+=m; else s-=m;m=j;
}
这段是在做拆符号的事情，就是根据i的值确定那8个空格填什么
switch(n%3) /*根据这一位的情况进行处理*/
{
case 0:m=m*10+j;break;
case 1:op='+';break;
case 2:op='-';break;
}
if (n%3) str[ptr++]=op; /*记录运算模式*/
str[ptr++]='0'+j;
n/=3;
}
就是按照填好的符号，计算表达式的结果
然后就是判断是不是是100。

1. 模型表示
在1 2 3 4 5 6 7 8 9九个数字中插入“+”或“-”符号使得结果为100，实际上是有八个地方需要插入符号。用下划线表示可以填入符号的位置1_2_3_4_5_6_7_8_9=100：而这样问题就变成了在这8个地方插入适当的“+”“-”符号使等式成立。
2. 算法设计
为得出符合条件的符号插入方式，选择了深度优先搜索，枚举所有符号可能添加的情况并计算它们的和，如果和等于100则输出。因为有8个位置可以插入符号，并且符号有“+”“-”和无符号3种可能。所以采用一