题目链接:
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;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
PDF试题
uva705 Slash Maze 的代码,在UVaOJ上通过
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
tpcw-nyu-uva-client 客户端
uva532 Dungeon Master的源代码,并且AC了
Uva软件测试2015-PT_MA2_2 Zacharopoulos Theologos 吉多·卢皮亚斯(Guido Loupias) 耶勒·范·阿塞玛约恩·亚历山大·格里戈罗夫(Yoan-Alexander Grigorov)