搞定24点游戏!用回溯法轻松解决算法设计与分析中的难题
最编程
2024-01-23 20:36:09
...
问题描述: 给定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\n");
else printf("No answer!\n");
}
上一篇: 如何用4、5、6、7凑出24点?
下一篇: 玩转24点:探索编程之美的小游戏