经典递归问题--快算24 POJ--3983

快算24

Description

Input

Output

Sample Input

5 5 1 5

Sample Output

5*(5-(1/5))

解题思路：这个题目一开始我就想着用递归去做，等想到剪枝的时候分析了一下问题规模发现其实如果数字固定的话 括号的分法就5种（可以自己在纸上验算一下），符号的情况就64种，完全可以枚举出来。然后在网上搜了一下答案，果然都是用枚举法做的。这里贴一个答案：

#include 
  
   
#include 
   
     #include 
    
      //四种符号 char operators[4] = {'+', '-', '*', '/'}; //符号运算 double calc( double a, int operatorr, double b) { switch (operators[operatorr]) { case '+': return a + b; break; case '-': return a - b; break; case '*': return a * b; break; case '/': return a / b; break; } } int calculator(int i, int j, int k, double a, double b, double c, double d) { if (calc(calc(a, i, b),j,calc(c, k, d)) - 24.0 == 0) { printf("(%.0lf%c%.0lf)%c(%.0lf%c%.0lf)\n",a, operators[i], b, operators[j], c, operators[k], d); return 1; } if (calc(calc(calc(a, i, b), j, c), k, d) - 24.0 == 0) { printf("((%.0lf%c%.0lf)%c%.0lf)%c%.0lf)\n",a, operators[i], b, operators[j], c, operators[k], d); return 1; } if (calc(calc(a, i, calc(b, j, c)), k, d) - 24.0 == 0) { printf("(%.0lf%c(%.0lf%c%.0lf))%c%.0lf)\n",a, operators[i], b, operators[j], c, operators[k], d); return 1; } if (calc(a, i, calc(calc(b, j, c), k, d)) - 24.0 == 0) { printf("%.0lf%c((%.0lf%c%.0lf)%c%.0lf)\n",a, operators[i], b, operators[j], c, operators[k], d); return 1; } if (calc(a, i, calc(b, j, calc(c, k, d))) == 24.0) { printf("%.0lf%c(%.0lf%c(%.0lf%c%.0lf))\n",a, operators[i], b, operators[j], c, operators[k], d); return 1; } return 0; } int main() { double a,b,c,d; while (scanf("%lf %lf %lf %lf", &a, &b, &c, &d) != EOF) { for (int i = 0; i < 4; ++ i) { for(int j = 0; j < 4; ++ j) { for(int k = 0; k < 4; ++ k) { if(calculator(i,j,k,a,b,c,d))//题目中说有唯一解，找到后直接跳出 goto success; } } } success: continue; } return 0; }
    
   
  

这样写起来貌似也还算简洁。但是考虑到最近一直在训练自己的递归思想，所以还是选择了用递归去解这道题目，过程中发现还是没有枚举来的简单。尤其是打印答案的步骤！

递归的思路是：a b c d 四个操作数，先选取两个操作数，遍历四种运算符，每次遍历后变成3个操作数，再次选取两个操作数，遍历四种操作符，剩下两个。重复遍历，答案如果是24就是问题的出口，如果不是倒退上一层。求的问题的解之后，要打印问题的解，所以需要知道操作数的优先顺训和具体的操作符。这个题目归规定操作数的顺序不变其实已经简化了题目的难度。

// 算24.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include
  
   
#include
   
     #include
    
      using namespace std; double a[4]={0.0}; int c[4]={0}; int record[4]={0}; char op[3]={0}; int cnt=0; void rever() { for(int i=0;i<3;i++) { if(a[i]==0) { a[i]=a[i+1]; a[i+1]=0; } } } void op_add(int i,int j) { a[i]+=a[j]; a[j]=0; rever(); } void op_sub(int i,int j) { a[i]-=a[j]; a[j]=0; rever(); } void op_mul(int i,int j) { a[i]*=a[j]; a[j]=0; rever(); } void op_div(int i,int j) { a[i]/=a[j]; a[j]=0; rever(); } bool ans(double a,double b) { if(a+b==24||a*b==24||a-b==24) return true; if(b!=0) { if(a/b==24) return true; } return false; } void copy(double b[],double c[]) { for(int i=0;i<4;i++) b[i]=c[i]; } bool cal(int n) { if(n==1) { if(a[0]==24) return true; else return false; } int i=0; double b[4]={0}; copy(b,a); for(;i
     
      >temp; a[i]=temp; c[i]=temp; } if(cal(4)) print(); return 0; } void print() { switch(record[2]) { case 0: if(record[1]==0) { printf("((%d%c%d)%c%d)%c%d",c[0],op[2],c[1],op[1],c[2],op[0],c[3]); break; } printf("(%d%c%d)%c(%d%c%d)",c[0],op[2],c[1],op[1],c[2],op[0],c[3]); break; case 1: if(record[1]==0) { printf("(%d%c(%d%c%d))%c%d",c[0],op[2],c[1],op[1],c[2],op[0],c[3]); break; } printf("%d%c((%d%c%d)%c%d)",c[0],op[2],c[1],op[1],c[2],op[0],c[3]); break; case 2: if(record[1]==0) { printf("(%d%c%d)%c(%d%c%d)",c[0],op[2],c[1],op[1],c[2],op[0],c[3]); break; } printf("%d%c(%d%c(%d%c%d))",c[0],op[0],c[1],op[1],c[2],op[2],c[3]); break; } }
     
    
   
  

有兴趣的同学可以想想顺序不定的情况。