uva 10344 - 23 out of 5
点击打开链接
题目意思：给定5个数，还有三种运算符 * + - ，问我们是否能够由这些数和运算符最后的值为23。
解题思路：我们知道5个数的全排列为5!种，那么我们只要去枚举这个全排列中每一个排列进行搜索，是否有23点出现有的话标记ans为1，直接退出。(注意必须全排列的查找，不能只按输入的顺序)
代码：
//计算5个数3个运算符能否组成23点//我们知道5个数的全排列为5!种，那么我们只要去枚举这个全排列中每一个排列进行搜索，是否有23点出现有的话标记ans为1，直接退出。(注意必须全排列的查找，不能只按输入的顺序)#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;int ans;int num[5];char ope[3] = {'*' , '+' , '-'};//运算符数组//搜索void dfs(int k , int sum){ if(k >= 5){//如果计算完成，判断是否有23点出现 if(sum == 23) ans = 1; return; } if(k < 5){ for(int i = 0 ; i < 3 ; i++){//搜索三种符号 //三种情况回溯，注意现场的恢复 if(i == 0){ sum *= num[k]; dfs(k+1 , sum); sum /= num[k]; } if(i == 1){ sum += num[k]; dfs(k+1 , sum); sum -= num[k]; } if(i == 2){ sum -= num[k]; dfs(k+1 , sum); sum += num[k]; } } ++k;//下一个数 }}//int main(){ int sum; while(1){ sum = 0; ans = 0; for(int i = 0 ; i < 5 ; i++){ scanf("%d" , &num[i]); sum += num[i]; } if(sum == 0) break;//全为0直接退出 else{ sort(num , num+5);//先排序 dfs(1 , num[0]);//求一下第一个顺序 if(ans) printf("Possible\n"); else{ while(next_permutation(num , num+5)){//全排列 dfs(1 , num[0]); if(ans){//搜索到了，直接退出 break; } } if(ans) printf("Possible\n"); else printf("Impossible\n"); } } } return 0;}