【算法设计与分析】（6）算24点问题（回溯法）

问题描述： 给定4个正整数，用算术运算符"+”，"-”，"*”，"/”将这4 个正整数连接起来，使最终的得数恰为24。 编程任务（建议用回溯方法）： 判断给定的4个数能否组成24。

数据输入： 1行 4个正整数。 结果输出: 1行，如果能得到24则输出Yes，否则输出"No answer!”。

例如： 输入 1 2 3 7

输出 Yes

将4个整数存入数组，递归的调用一个函数，用算数符连接四个数，若不等于24则改变算数符。

#include<stdio.h>
#include<string.h>
#include<math.h>
  int judge=0;
  
  void search(float a[50],int n)
  {
  	int i,j;
  	if (n==1)
  	{
	 for (i=0;i<=3;i++)
	 if (fabs(a[i]-24)<0.01)
	  judge=1;
	}
	else 
	{
	 for (i=0;i<=2;i++)
  	  for (j=i+1;j<=3;j++)
  	  if (a[i]!=0&&a[j]!=0)
      {
	   float a1=a[i],a2=a[j];
	   	
	   if (a2!=0)
	   {
	   	a[i]=1.0000*a1/a2;
	   	a[j]=0;
	   	search(a,n-1);
	   	a[i]=a1;a[j]=a2;
	   }
	   
	   
	   {
	   	 a[i]=a2-a1;
	   a[j]=0;
	   search(a,n-1);
	   a[i]=a1;a[j]=a2;
	   }
	  
	 
	  
	   {
	   	 a[i]=a1*a2;
	   a[j]=0;
	   search(a,n-1);
	   a[i]=a1;a[j]=a2;
	   }
	  
	   
	   a[i]=a1+a2;
	   a[j]=0;
	   search(a,n-1);
	   a[i]=a1;a[j]=a2;
	   
	   
	   a[i]=a1-a2;
	   a[j]=0;
	   search(a,n-1);
	   a[i]=a1;a[j]=a2;
	   
	   
	   if (a1!=0)
	   {
	   	a[i]=1.0000*a2/a1;
	   	a[j]=0;
	   	search(a,n-1);
	   	a[i]=a1;a[j]=a2;
	   }
	  }  	
	}
  		
  }
  
  int main()
  {
   float a[50];
   int i;
   memset(a,0,sizeof(a));
   for (i=0;i<4;i++)
    scanf("%f",&a[i]);
    
	search(a,4);
   if (judge==1)
    printf("Yes
");
   else printf("No answer!
");  
   
  }