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

10344-23 out of 5

7004

31.42%

1882

73.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 (转载请标明)