给1~9中间填符号.doc

C+编程趣题：给19中间填符号这是一个挺经典也有点难度的C/C+编程题：在1 2 3 4 5 6 7 8 9九个数字中插入“+”或“-”符号使得结果为100，编程实现所有的组合。注：数字的顺序不能改变。如： 123 - 45 - 67 + 89 = 100 12 - 3 -4 + 5 - 6 + 7 + 89 = 100小豆子无意中看到，兴趣浓浓。网上流传的答案版本就是用九个for循环遍历。这显然不是一个好的方案，如果不是九个数，而是九十个数，就得扩展到九十个for循环，优化空间太小。小豆子经过两天的思索，想到了一个解决方法。自己认为要比现有的方法巧妙，而且没有用到很高深的C知识，比较易懂。现给出程序如下，已经过调试，可直接运行（该方法的具体思路见末尾）。如果有缘人也在做这个程序，欢迎和小豆子切磋！#include #include #include #define NUM 6561 /38:6561int mici(int x, int i)/求解xiint res = 1;for (; i0; i-) res *= x;return (res);int main(int argc, char *argv)int data9;int index, level;int i, j, k=0;int pre_sign;int temp = 0;int sum = 0;int x = 2;for (i=0; i1; level-)/有8处符号需要判断pre_sign = index%3; /该空的符号，规定0：+，1：-；2：连接index = index/3;/往上一层（即上一个空）的位置switch(pre_sign)case 0: if (temp = 0) datak = level; elsedatak = temp;temp = 0;x = 2;k+;break;case 1: if (temp = 0) datak = 0 - level; elsedatak = 0 - temp;temp = 0;x = 2;k+;break;case 2:if (temp = 0)temp = level + (level-1)*10;else temp = temp + (level-1)*mici(10,x);x+;break;default:break;if (pre_sign = 2)/处理数字1datak = temp;elsedatak = 1;k = 0; /将这些变量复位很重要，以免影响下一轮！temp = 0;x = 2;for (j=0; dataj!=0; j+)/求和sum = sum + dataj;if (sum = 100)for (j=j-1; j=0; j-)/逆序输出，这样1在前面if (dataj 0) cout+dataj;elsecoutdataj;cout = sum/*.i*/endl; /i for testsum = 0;return(0);/*-算法详述：-问题分析：1_2_3_4_5_6_7_8_9 如图所示，有8个空需要填符号（+，-，连接），一共有6561种情况。 可以建立一个三叉树对情况编号。规定0：+，1：-，2：连接。 start空格1 0 1 2空格2 0 1 2 3 4 5 6 7 8空格3 012 345 678 9空格8 012345676560如图所示，比如给定情况number，则number%3求的本空格的符号，number/3进入上一层的编号，依次类推，直到从树叶回溯至树根，确定8个空的符号各是什么-程序说明：外层循环i相当于遍历树叶节点06560，index则是取出某一具体树叶，回溯时的编号过程 将每个数字放在数组data中，便于最后计算。 比如判断7前面是+，就将+7放进data；如果是-，就将-7放进data； 如果是连接符，就先将67放进temp，再判断前一个符号（