第三题：等式变换
输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如：
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序，统计满足输入整数的所有整数个数。
输入： 正整数，等式右边的数字
输出： 使该等式成立的个数
样例输入：5
样例输出：21
无意中在别人博客中看到了这道题 就做个试试 结果做了一个多小时 调试气死人啊。。。
我也就这水平了 唉。
#include <stdio.h>
int oper[9];
int result,sum;
void dfs(int x,int count)
{
if(count>8)
return ;
oper[count]=x;
if(count==8)
{
int num=1;
int curresult=0;
int lastresult=1;
int i=1;
for(i=1;i<9;i++)
{
if(oper[i]==2)
lastresult=lastresult*10+(++num);
else
break;
}
while(++num<=9)
{
int op=oper[i];
curresult=num;
for(int j=i+1;j<9;j++)
{
if(oper[j]==2)
curresult=curresult*10+(++num);
else
{
i=j;
break;
}
}
if(op==0)
lastresult+=curresult;
else if(op==1)
lastresult-=curresult;
}
if(lastresult==result)
{
printf("************************\n");
for(int i=1;i<=8;i++)
{
printf("%d",i);
if(oper[i]==0)
printf("+");
if(oper[i]==1)
printf("-");
}
printf("9=%d\n",result);
printf("************************\n");
sum++;
}
return ;
}
dfs(0,count+1);//+
dfs(1,count+1);//-
dfs(2,count+1);//
}
int main()
{
while(~scanf("%d",&result))
{
sum=0;
dfs(0,0);
printf("%d\n",sum);
}
}
题目转自这个博客
