首页 > 代码库 > uva10344 - 23 out of 5
uva10344 - 23 out of 5
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)
Input
The Input consists of 5-Tupels of positive Integers, each between 1 and 50.
Input is terminated by a line containing five zero‘s. This line should not be processed.
Output
For each 5-Tupel print "Possible" (without quotes) if their exists an arithmetic expression (as described above) that yields 23. Otherwise print "Impossible".
Sample Input
1 1 1 1 1
1 2 3 4 5
2 3 5 7 11
0 0 0 0 0
Sample Output
Impossible
Possible
Possible
// 题意：输入5个整数，按照某种顺序排列后依次进行+, -或者*，使得最终结果为23。判断是否有解
// 算法：回溯
time 1.692
#include<cstdio>#include<cstring>#include<iostream>#include<string>#include<algorithm>using namespace std;int a[5];int b[5];char op[5];int vis[5];int possible;void dfs(int d, int s){ if(d==5) { if(s==23) { possible=1;#ifndef ONLINE_JUDGE printf("(((%d ", b[0]); for(int i=1;i<4;i++) printf("%c %d) ", op[i], b[i]); printf("%c %d ", op[4], b[4]); printf("\n");#endif } return; } for(int i=0;i<5;i++) { //第一个数 if(d==0) { if(!vis[i]) { vis[i]=1; b[d]=a[i]; dfs(d+1, a[i]); vis[i]=0; } } else { if(!vis[i]) { vis[i]=1; b[d]=a[i]; op[d]=‘+‘; dfs(d+1, s+a[i]); op[d]=‘-‘; dfs(d+1, s-a[i]); op[d]=‘*‘; dfs(d+1, s*a[i]); vis[i]=0; } } }}int main(){#ifndef ONLINE_JUDGE freopen("./uva10344.in", "r", stdin);#endif while(scanf("%d%d%d%d%d", a, a+1, a+2, a+3, a+4)==5 && (a[0] || a[1] || a[2] || a[3] || a[4])) { possible=0; dfs(0, 0); if(possible) puts("Possible"); else puts("Impossible"); } return 0;}
找到后立刻返回，time 0.945
学习点，dfs时判断扩展点的返回值，如果已经成功，就直接返回。
#include<cstdio>#include<cstring>#include<iostream>#include<string>#include<algorithm>using namespace std;int a[5];int vis[5];bool dfs(int d, int s){ if(d==5) return s==23; for(int i=0;i<5;i++) if(!vis[i]) { vis[i]=1; //第一个数 if(d==0) { if(dfs(d+1, a[i])) return true; } else { if(dfs(d+1, s+a[i])) return true; if(dfs(d+1, s-a[i])) return true; if(dfs(d+1, s*a[i])) return true; } vis[i]=0; } return false;}int main(){#ifndef ONLINE_JUDGE freopen("./uva10344.in", "r", stdin);#endif while(scanf("%d%d%d%d%d", a, a+1, a+2, a+3, a+4)==5 && (a[0] || a[1] || a[2] || a[3] || a[4])) { memset(vis, 0, sizeof(vis)); if(dfs(0, 0)) puts("Possible"); else puts("Impossible"); } return 0;}
next_permutation 计算差点超时： 2.388
#include<cstdio>#include<cstring>#include<iostream>#include<string>#include<algorithm>using namespace std;int a[5];bool check(int k){ int s=a[0]; for(int j=1;j<5;j++) { switch(k%3) { case 0: s+=a[j]; break; case 1: s-=a[j]; break; case 2: s*=a[j]; break; } k/=3; } return s==23;}int main(){#ifndef ONLINE_JUDGE freopen("./uva10344.in", "r", stdin);#endif while(scanf("%d%d%d%d%d", a, a+1, a+2, a+3, a+4)==5 && (a[0] || a[1] || a[2] || a[3] || a[4])) { sort(a, a+5); int ok=0; do { for(int i=0;i<81;i++) if(check(i)) { ok=1; break; } }while(!ok && next_permutation(a, a+5)); if(ok) puts("Possible"); else puts("Impossible"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。