HDU1427 速算24点

解题思路:

枚举所有可能的情况。

首先对四个数字进行全排列,对于每一种排列,通过dfs模拟出带不同括号的情况,对于每一种情况,再进行加减乘除的运算,看有没有一种情况能算出24的结果。

这里还有2个问题:

1 要对输入进行转换,尤其是A、10、J、Q、K这样的特殊牌。

2 在进行除法运算前要进行判断,首先除数不能为0,不然程序会崩溃,然后要能整除。

代码:

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 int k;
 7 int card[4];
 8 char temp[4];
 9 //处理几张特殊的牌 
10 void tra(int i)
11 {
12     if(strcmp(temp, "A")==0)        card[i]=1;
13     else if(strcmp(temp, "10")==0)        card[i]=10;
14     else if(strcmp(temp, "J")==0)        card[i]=11;
15     else if(strcmp(temp, "Q")==0)        card[i]=12;
16     else if(strcmp(temp, "K")==0)        card[i]=13;
17     else card[i] = (int)(temp[0]-48);
18 }
19 int judge24(int n)
20 {
21     return (n == 24);
22 }
23 void dfs(int sum,int cur, int m)
24 {
25     if(k == 1)    return;
26   if(m == 3)
27   {
28     if(judge24(sum+cur) || judge24(sum-cur) || judge24(sum*cur))
29     {
30         //printf("%d %d
",sum,cur);
31         k = 1;
32     }
33     else if(cur!=0 && sum%cur==0 && judge24((sum/cur)))
34     {//注意除数不能为0且必须能整除 
35         //printf("%d %d
",sum,cur);
36         k=1;
37     }
38     return;
39   }
40   //通过这种搜索虚拟不同的括号从而改变运算顺序 
41   dfs(sum+cur, card[m+1], m+1);
42   dfs(sum-cur, card[m+1], m+1);
43   dfs(sum*cur, card[m+1], m+1);
44   if(cur!=0 && sum%cur==0)  dfs(sum/cur, card[m+1], m+1);
45 
46   dfs(sum, cur+card[m+1], m+1);
47   dfs(sum, cur-card[m+1], m+1);
48   dfs(sum, cur*card[m+1], m+1);
49   if(card[m+1]!=0 && cur%card[m+1]==0)  dfs(sum, cur/card[m+1], m+1);
50 }
51 int main(void)
52 {
53     //freopen("1427.in", "r", stdin);
54     while(scanf("%s",temp) != EOF)
55   {
56       k = 0;
57       tra(0);
58     for(int i=1; i<4; i++)
59     {
60         scanf("%s",temp);
61         tra(i);    //用于字符转化为数字 
62     }
63     sort(card, card+4);//要先排序才能进行全排列 
64     do
65     {
66       dfs(card[0], card[1], 1);    //对于每一个排列,进行dfs来构造不同的运算顺序 
67     }while(next_permutation(card, card+4) && k==0);//通过全排列构造不同的算式 
68     if(k == 0)  printf("No
");
69     else printf("Yes
");
70   }
71     return 0;
72 }//2015-07-25 
原文地址:https://www.cnblogs.com/mycd/p/5657145.html