UVa 10344 - 23 out of 五， 智力小游戏：算23点

UVa 10344 - 23 out of 5， 智力小游戏：算23点

10344 - 23 out of 5700431.42%188273.33%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=1285

原题：

Your task is to write a program that can decide whether you can find an arithmetic expression consisting of five given numbers (1<=i<=5) that will yield the value 23.
For this problem we will only consider arithmetic expressions of the following from:

where : {1,2,3,4,5} -> {1,2,3,4,5} is a bijective function

and  {+,-,*} (1<=i<=4)

样例输入：

1 1 1 1 1

1 2 3 4 5

2 3 5 7 11

0 0 0 0 0

样例输出：

Impossible

Possible

Possible

题目大意：

这题的题意较好题解，游戏规则和扑克牌的“算24点”基本一样。

规则是这样的：给你5张牌， 然后要你任意用+，-， * 这三个符号，对这5个数字进行计算，使它们之和为23.

要你编程来判断所有的5张牌能否实现23点。

思路与总结：

这个游戏相信很多人小时候都玩过， 如果小时候就能编一个小程序来帮我们，那就。。。。。。看来会编程还是有点用的，

至少可以骗骗小孩...

如果用利用计算机，用递归回溯算法来做的话，那么将是很简单的一件事，只需要暴力地搜索出所有的排列，用所有的符号，

即可轻轻松松得到答案

代码实现:

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int arr[5];bool vis[5], flag;void dfs(int cur, int sum){     if(flag) return; // 一旦找到方案，就可以一直退栈了        for(int i=0; i<5; ++i)if(!vis[i]){        vis[i] = true;        if(!cur)             dfs(cur+1, arr[i]);        else{            dfs(cur+1, sum-arr[i]);  // 减法            dfs(cur+1, sum+arr[i]); // 加法            dfs(cur+1, sum*arr[i]); // 乘法        }        vis[i] = false;  // 回溯    }    if(cur==5 && sum==23){        flag=true; return;    }}int main(){#ifdef LOCAL    freopen("input.txt","r",stdin);#endif    while(~scanf("%d%d%d%d%d",&arr[0],&arr[1],&arr[2],&arr[3],&arr[4])){        if(!arr[0] && !arr[1] && !arr[2] && !arr[3] && !arr[4]) break;        flag = false;        memset(vis, 0, sizeof(vis));        dfs(0, 0);        if(flag) printf("Possible\n");        else printf("Impossible\n");     }    return 0;}

——  生命的意义，在于赋予它意义。
 
               原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)