点击打开链接
题目意思:给定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;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
uva532 Dungeon Master的源代码,并且AC了
tpcw-nyu-uva-client 客户端
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC