C语言设计之回溯算法.doc

《C语言设计之回溯算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言设计之回溯算法（24点）姚铸问题叙述：24点：从键盘输入4个数字进行加减乘除，要求结果为24输入要求   第一行：4321输出   24=12*2   2=2*1   12=4*3问题分析：这个问题是我们小时候都应该玩过。问题的重点在于输入的数据要进行运算后得到24这个值是问题的难点。4个数之间无序的运算有很多种情况。用程序去实现24点，就需要4个数之间进行每一种的讨论。用穷举是能够计算出来的。但是时间复杂度值太大。算法设计：这类型问题的解决方案重点在于4个数算出的结果如果不能在该步运算出24能否后悔还原会

2、上一次循环或递归。这里的后悔就联想到回溯算法。算法思想：从算法设计得到了回溯算法。后悔正是回溯算法的中心思想。在得不到真正的结果的时候退回上一步。在结果计算的时候运用if或while语言对程序结束进行控制。特殊测试：5551这组数据计算24点是成立的。在运算的过程中会出现小数。参考程序（这是我自己写出的程序代码，经过测试没有问题。）：递归算法实现回溯：#includeinti=0;voiddian(floata,floatb,floatc,floatd,intj); /*回朔声明*/voidji

3、a(floata,floatb,floatc,floatd,intj)  /*进行加的运算*/ {if((a*b!=0)&&(j<4)&&(i!=1))    {dian(a+b,c,d,0,j+1);    if(i==1) printf("%g=%g+%g",a+b,a,b);} }voidjian(floata,floatb,floatc,floatd,intj) /*进行减的运算*/ {if((a*b!=0)&&(j<4)&&(i!=1))    {dian(a-b,c,d,0,j+1);     d

4、ian(b-a,c,d,0,j+1);    if(i==1)      printf("%g=%g-%g",a-b,a,b);} }voidcheng(floata,floatb,floatc,floatd,intj) /*进行乘的运算*/ {if((a*b!=0)&&(j<4)&&(i!=1))    {dian(a*b,c,d,0,j+1);    if(i==1)      printf("%g=%g*%g",a*b,a,b);} }voidchu(floata,floatb,floatc,flo

5、atd,intj)  /*进行除的运算*/ {if((a*b!=0)&&(j<4)&&(i!=1))    {dian(a/b,c,d,0,j+1);    if(i==1)      printf("%g=%g/%g",a/b,a,b);} }voiddian(floata,floatb,floatc,floatd,intj) /*进行回朔*/ {  jia(a,b,c,d,j);  cheng(a,b,c,d,j);  jian(a,d,b,c,j);  chu(a,d,b,c,j);  jia(a,c,

6、b,d,j);  cheng(a,c,b,d,j);  jia(a,d,c,b,j);  cheng(a,d,c,b,j);  jian(a,b,c,d,j);  chu(a,b,c,d,j);  jian(b,a,c,d,j);  chu(b,a,c,d,j);  jian(d,a,b,c,j);  chu(d,a,b,c,j);  jian(a,c,b,d,j);  chu(a,c,b,d,j); /*进行交换（这里可以用程序嵌套简化）*/  if((j==3)&&(a+b+c+d==24))  /*运算的结

7、果是否是24，如果为24将记号改为1*/      i=1; }voidmain() {floata,b,c,d;  printf("input4num");  scanf("%f%f%f%f",&a,&b,&c,&d);  if(i==0)dian(a,b,c,d,0);  if(i==0)dian(b,a,c,d,0);  if(i==0)dian(c,b,a,d,0);  if(i==0)dian(d,a,b,c,0); }