题目：算24点【递归式搜索】
题目描述
您可以使用的运算只有：+，-，，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果须是整数，所以一些除法运算是不允许的（例如，(22)/4是合法的，2*(2/4)是不合法的）。下面我们给出一个游戏的具体例子：
若给出的4个操作数是：1 2 3 7，则一种可能的解答是1+2+3*7=24。
本题不要求输出具体计算过程。
输入输出格式
输入格式：
只有一行，四个1到9之间的自然数。
输出格式：
如果有解的话，只要输出“yes”。如果没有解则输出“no”。
注意：不要输出引号“”。
#include<bits/stdc++.h>
using namespace std;
int num[5];
bool b[5];
void dfs(int t,int res){
// printf("%d\t%d\n",t,res);
if(t==5){
if(res==24) printf("yes"),exit(0);
return;
}
for(int i=1;i<=4;i++){
if(b[i]==1) continue;
b[i]=1;
dfs(t+1,res+num[i]);
dfs(t+1,res-num[i]);
dfs(t+1,res*num[i]);
if(res%num[i]==0) dfs(t+1,res/num[i]);
b[i]=0;
}
}
int main(){
for(int i=1;i<=4;i++) scanf("%d",&num[i]);
dfs(1,0);
printf("no\n");
}
输入7 7 8 9本应该输出no但程序输出的是yes
第一个数字应该不能除，因为一开始res=0，然后进来就会出现res%num[0]==0, 也就是0%7==0, 相当于直接少了一个数字，最后7+8+9=24
你没有判断num[i]是否为零，就除了，所以答案会错，改了答案就对了。
#include<bits/stdc++.h>
using namespace std;
int num[5];
bool b[5];
void dfs(int t,int res){
// printf("%d\t%d\n",t,res);
if(t == 5){
if(res == 24) printf("yes"), exit(0);
return;
}
for(int i = 1; i <= 4; i++){
if(b[i]) continue;
b[i] = 1;
dfs(t + 1, res + num[i]);
dfs(t + 1, res - num[i]);
dfs(t + 1, res * num[i]);
if(num[i] && res % num[i] == 0) dfs(t + 1, res / num[i]);
b[i] = 0;
}
}
int main(){
for(int i = 1; i <= 4; i++) scanf("%d", &num[i]);
dfs(1, 0);
printf("no\n");
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
char op[3], o[5]="+-*/";
float n[4], on[10];
int used[4] = {0}, top=0, tp=0, x;
void chk(float k);
void search24(int d);
float calc(float n1, float n2, char o);
void make(int i, float p, float q, char o, int d);
int main( void )
{
printf("please input 4 card number:");
scanf("%f%f%f%f", &n[0], &n[1], &n[2], &n[3]);
search24(0);
printf("No answer.");
return 0;
}
void chk(float k)
{
if( (tp != 3) || ( fabs(k-24.0) > 0.000001 )) //没有用完3个运算符或者结果不为24就退出.
return;
for(x=0; x<5; x+=2) //这样设计是为了使3个选中的符号都可以得到输出.
printf("%g%c%g=%g", on[x], op[x/2], on[x+1], //分析得到的.
calc(on[x], on[x+1], op[x/2]));
system("pause");
exit(0);
}
float calc(float n1, float n2, char o)
{
switch(o){
case '+': return (n1+n2);
case '-': return (n1-n2);
case '*': return (n1*n2);
case '/': return (n1/n2);
default: exit(0);
}
}
void make(int i, float p, float q, char o, int d)
{
if(fabs(q)>0.000001 || o!='/') //除数不为0,或者为0的时候不能为除数.
n[i] = calc(p, q, o);
op[tp++] = o;
chk(n[i]);
search24(d+1);
tp--; //因为是全是全局变量,所以在做试验性的循环递归问题时,如果失败,要在递归函数后面重新恢复回原来的值
}
void search24(int d)
{
int i, j, k;
float p, q;
if(d>=3) //控制递归深度,就是运算符的输出个数.
return;
for(i=0; i<4; i++)
for(j=0; j<4; j++)
if( (i!=j)&& (used[i]+used[j] == 0) ) //i!=j是防止重复,(used[i]+used[j] == 0)是防止又再匹配已经用过的j,
//但是i可以新来.
{
used[j] = 1; //j得到匹配之后,赋值为1,表示已经使用
p=n[i];
q=n[j];
on[top++] = p;
on[top++] = q;
for(k=0; k<4; k++) //运算符的循环试用.
make(i, p, q, o[k], d);
n[i] = p; //因为是全是全局变量,所以在做试验性的循环递归问题时,
used[j] = 0; //如果失败,要在递归函数后面重新恢复回原来的值
top -= 2; //
}
}
#include<bits/stdc++.h>
using namespace std;
int num[5];
bool b[5];
void dfs(int t,int res){
if(t==5){
if(res==24) printf("yes"),exit(0);
return;
}
for(int i=1;i<=4;i++){
if(b[i]==1) continue;
b[i]=1;
dfs(t+1,res+num[i]);
dfs(t+1,res-num[i]);
dfs(t+1,res*num[i]);
// 添加除数为0的判断
if(num[i] != 0 && res%num[i]==0) dfs(t+1,res/num[i]);
b[i]=0;
}
}
int main(){
for(int i=1;i<=4;i++) scanf("%d",&num[i]);
dfs(1,0);
printf("no\n");
}
请注意，由于存在递归过程中的多种运算符顺序，代码的运行时间可能会比较长。在某些情况下，可能需要等待较长时间才能得到结果。