24点游戏_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
阅读已结束，下载文档到电脑
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩53页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢2010年6月 专题开发/技术/项目大版内专家分月排行榜第二
2010年4月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。Time Limit: 20 Sec
Memory Limit: 256 MB
http://acm./#/problem/show/1252
Description
24点就是给你一串数字，问你是否通过加减乘除括号构成24点。
沈爷觉得这个很好玩，就决定考考你，给你4个数，可以交换位置，可以用加减乘除和括号，是否能构成24点呢？
注意哦~这里的除法并不是整数除法，比如样例
第一行T，表示有多少组测试数据，1≤T≤50
接下来T行，每行4个正整数a1,&a2,&a3,&a4，表示每个数都是多少，1≤ai≤13
对于每一次询问，如果能够凑成24点，输出yes，否则输出no
Sample Input
Sample Output
对于这题笔者是看了大牛的正解之后才知道该如何用DFS（深搜）来解决这个问题；
下面就贴出代码吧：
#include&iostream&
#include&algorithm&
#include&cmath&
#include&cstdio&
double value[4];
//对于此处的判断是否是24点，是实数而且考虑负数
bool DFS(int n)
if(fabs(value[n-1]-24)&1e-6)
for(int i=0;i&n;++i)
for(int j=i+1;j&n;++j)
double x1 = value[i];
double x2 = value[j];
value[j] = value[n-1];
//将后面的数提到前面来，以便于后面的计算
value[i] = x1+x2; if(DFS(n-1))
value[i] = x1*x2; if(DFS(n-1))
value[i] = x1-x2; if(DFS(n-1))
value[i] = x2-x1; if(DFS(n-1))
value[i] = x2/x1; if(DFS(n-1)) }
value[i] = x1/x2; if(DFS(n-1)) }
//对于数value[j]没有满足条件，所以还原原来的数
value[i] = x1;
value[j] = x2;
//若n为数都不满足的话，就返回false
int main(void)
while(T--)
cin&&value[0]&&value[1]&&value[2]&&value[3];
if(DFS(4))
cout&&&yes\n&;
cout&&&no\n&;
如果你还没搞清楚状况的话可以点击一下下面的传送门：
路漫漫其修远兮，吾将hold下去！
8÷(3–8÷3)对
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：10833次
排名：千里之外
原创：61篇
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'之前发了一篇博文&&，有人颇不以为然。我想说的是，发这篇文章是说明我可以用计算机求出24点的所有组合的解法。而在实际的运用中，如果要使用24点的算法有时还不见得利用查表法来得简单和快速。毕竟，要短时间内写出正确的算法并验证，也不是一件很容易的事。
24点游戏的规则：给定4个正整数（1到10），利用加减乘除运算，得出运算结果为24的运算式
1，2，3，4&&（1+2+3）*4=24
1，5，5，5&&（5-1/5）*5=24
网上比较常见的24点算法是动态规划算法（这个在博客园中也能搜索到）。
定义6个二元运算符：加、减、乘、除、反减、反除
然后从4个数中任选2个数，通过一种运算（6个运算中的1个）得到一个新数
问题就演化成3个数的24点
重复上面的步骤，直到剩下一个数，如果这个数是24，则之前的运算过程就是24点的解答之一。如果这个数不是24，说明之前的运算不正确，再重新计算。如果所有的数的组合和运算的组合都尝试后，仍然没有找到解答，说明这4个数没有解
算一算运算一组解需要多少种可能性
第一步，从4个数中，任选两个数，6个运算符，则一共有C（4，2）*6=6*6=36
第二步，从3个数中，任选两个数，6个运算符，则一共有C（3，2）*6=3*6=18，则前两步一共有36*18=648种
第三步，6个运算符，则一共有6，最终求一组解的要搜索的可能性有648*6=3888种
上面是求一组解，要搜索的可能性，一共3888种
如果要得出所有组合的解，先要算出一共有多少种组合
4个数都不相同，C（10，4）=210
只有2个数相同，C（10，3）*3=360
2组2个数相同，C（10，2）=45
只有3个数相同，C（10，2）*2=90
4个数都相同，C（10，1）=10
则一共有210+360+45+90+10=715组
则求出所有组合的解，则一共要搜索715*种可能性
说白了，24点的算法就是一种穷举法
换一种思路，介绍我的24点的穷举法
上面的算法是对数和运算符进行穷举和搜索
我的算法是对运算式进行穷举
无论给什么样的是4个数，运算式总是不变的，举例来说：
N+N+N+N=24，这是一种运算式
N*N+N*N=24，这是另一种运算式
N/（N-N/N）=24，这又是另一种运算式
下面这个例子：
N+N-（N-N）=24
N+N-N+N=24
上面虽然是两种不同的运算式，但本质是同一种运算式（肯定同时成立或同时不成立），穷举的时候只要穷举其中一个就行了
再看下面这个例子
N/(N+N+N)=24
虽然是一个运算式，但是这个运算式是不可能成立的，也就是无解运算式，穷举的时候是不需要穷举该运算式的
下面这个表格是我整理的所有的运算式，其中有的运算式有等价运算式，有的运算式是无解运算式，按照上面的讲法，这两类运算式在穷举的时候都不需要穷举
24点运算式表
等价运算式
N+N+N+N=24
N+N+N-N=24
N+N+N*N=24
N+(N+N)*N=24
(N+N+N)*N=24
N+N+N/N=24
N+(N+N)/N=24
(N+N+N)/N=24
N+N-N+N=24
N+N+N-N=24
N+N-(N+N)=24
N+N-N-N=24
N+N-N-N=24
N+N-(N-N)=24
N+N-N+N=24 N+N+N-N=24
N+N-N*N=24
N+(N-N)*N=24
(N+N-N)*N=24
N+N-N/N=24
N+(N-N)/N=24
(N+N-N)/N=24
N+N*N+N=24
(N+N)*N+N=24
N+N*(N+N)=24
(N+N)*N+N=24
(N+N)*(N+N)=24
N+N*N-N=24
(N+N)*N-N=24
N+N*(N-N)=24
(N+N)*(N-N)=24
N+N*N*N=24
(N+N)*N*N=24
(N+N*N)*N=24
N+N*N/N=24
(N+N)*N/N=24
(N+N*N)/N=24
N+N/N+N=24
(N+N)/N+N=24
N+N/(N+N)=24
(N+N)/(N+N)=24
N+N/N-N=24
(N+N)/N-N=24
N+N/(N-N)=24
(N+N)/(N-N)=24
N+N/N*N=24
N+N*N/N=24
(N+N)/N*N=24
(N+N)*N/N=24
(N+N/N)*N=24
N+N/(N*N)=24
N+N/N/N=24
(N+N)/(N*N)=24
(N+N)/N/N=24
N+N/N/N=24
(N+N)/N/N=24
(N+N/N)/N=24
N+N/(N/N)=24
N+N/N*N=24
N+N*N/N=24
(N+N)/(N/N)=24
(N+N)/N*N=24
(N+N)*N/N=24
N-N+N+N=24
N+N+N-N=24
N-(N+N)+N=24
N-N-N+N=24
N+N-N-N=24
N-(N+N+N)=24
N-N-N-N=24
N-N+N-N=24
N+N-N-N=24
N-(N+N)-N=24
N-N-N-N=24
N-(N+N-N)=24
N-N-N+N=24
N+N-N-N=24
N-N+N*N=24
N+N*N-N=24
N-(N+N)*N=24
N-(N+N*N)=24
(N-N+N)*N=24
(N+N-N)*N=24
(N-(N+N))*N=24
(N-N-N)*N=24
N-N+N/N=24
N-(N+N)/N=24
N-(N+N/N)=24
N-N-N/N=24
(N-N+N)/N=24
(N+N-N)/N=24
(N-(N+N))/N=24
(N-N-N)/N=24
N-N-N+N=24
N+N-N-N=24
N-(N-N)+N=24
N-N+N+N=24
N+N+N-N=24
N-(N-N+N)=24
N-N+N-N=24
N+N-N-N=24
N+N-N-N=24
N-N+N+N=24
N+N+N-N=24
N-N-(N+N)=24
N-N-N-N=24
N-N-N-N=24
N-N-(N-N)=24
N-N-N+N =24
N+N-N-N=24
N-(N-N)-N=24
N-N+N-N=24
N+N-N-N=24
N-(N-N-N)=24
N-N+N+N=24
N+N+N-N=24
N-(N-(N-N))=24
N-N+N-N=24
N+N-N-N=24
N-N-N*N=24
N-(N-N)*N=24
N+(N-N)*N=24
(N-N-N)*N=24
(N-(N-N))*N=24
(N-N+N)*N=24
(N+N-N)*N=24
N-N-N/N=24
N-(N-N)/N=24
N+(N-N)/N=24
(N-N-N)/N=24
(N-(N-N))/N=24
(N-N+N)/N=24
(N+N-N)/N=24
N-N*N+N=24
N+N-N*N=24
(N-N)*N+N=24
N+(N-N)*N=24
N-N*(N+N)=24
N-(N+N)*N=24
(N-N)*(N+N)=24
(N+N)*(N-N)=24
N-(N*N+N)=24
N-N*N-N=24
N-N-N*N=24
N-N*N-N=24
N-N-N*N=24
(N-N)*N-N=24
N-N*(N-N)=24
N+N*(N-N)=24
N+(N-N)*N=24
(N-N)*(N-N)=24
N-(N*N-N)=24
N-N*N+N=24
N+N-N*N=24
N-N*N*N=24
(N-N)*N*N=24
(N-N*N)*N=24
N-N*N/N=24
(N-N)*N/N=24
(N-N*N)/N=24
N-N/N+N=24
N+N-N/N=24
(N-N)/N+N=24
N+(N-N)/N=24
N-N/(N+N)=24
(N-N)/(N+N)=24
N-(N/N+N)=24
N-N/N-N=24
N-N-N/N=24
N-N/N-N=24
N-N-N/N=24
(N-N)/N-N=24
N-N/(N-N)=24
N+N/(N-N)=24
(N-N)/(N-N)=24
N-(N/N-N)=24
N-N/N+N=24
N+N-N/N=24
N-N/N*N=24
(N-N)/N*N=24
(N-N/N)*N=24
N-N/(N*N)=24
N-N/N/N=24
(N-N)/(N*N)=24
(N-N)/N/N=24
N-N/N/N=24
(N-N)/N/N=24
(N-N/N)/N=24
N-N/(N/N)=24
N-N/N*N=24
N-N*N/N=24
(N-N)/(N/N)=24
(N-N)/N*N=24
(N-N)*N/N=24
N*N+N+N=24
N+N+N*N=24
N*(N+N)+N=24
N+(N+N)*N=24
N*(N+N+N)=24
(N+N+N)*N=24
N*N+N-N=24
N-N+N*N=24
N*(N+N)-N=24
(N+N)*N-N=24
N*(N+N-N)=24
(N+N-N)*N=24
N*N+N*N=24
N*(N+N)*N=24
(N+N)*N*N=24
(N*N+N)*N=24
(N+N*N)*N=24
N*(N+N*N)=24
(N+N*N)*N=24
N*N+N/N=24
N*(N+N)/N=24
(N+N)*N/N=24
(N*N+N)/N=24
(N+N*N)/N=24
N*(N+N/N)=24
(N+N/N)*N=24
N*N-N+N=24
N-N+N*N=24
N*(N-N)+N=24
N+(N-N)*N=24
N*(N-N+N)=24
(N+N-N)*N=24
N*N-(N+N)=24
N*N-N-N=24
N*(N-(N+N))=24
N*(N-N-N)=24
(N-N-N)*N=24
N*N-N-N=24
N*(N-N)-N=24
(N-N)*N-N=24
N*(N-N-N)=24
(N-N-N)*N=24
N*N-(N-N)=24
N*N-N+N=24
N-N+N*N=24
N*(N-(N-N))=24
N*(N-N+N)=24
(N+N-N)*N=24
N*N-N*N=24
N*(N-N)*N=24
(N-N)*N*N=24
(N*N-N)*N=24
N*(N-N*N)=24
(N-N*N)*N=24
N*N-N/N=24
N*(N-N)/N=24
(N-M2)*N/N=24
(N*N-N)/N=24
N*(N-N/N)=24
(N-N/N)*N=24
N*N*N+N=24
N+N*N*N=24
N*N*(N+N)=24
(N+N)*N*N=24
N*(N*N+N)=24
(N+N*N)*N=24
N*N*N-N=24
N*N*(N-N)=24
(N-N)*N*N=24
N*(N*N-N)=24
(N*N-N)*N=24
N*N*N*N=24
N*N*N/N=24
N*N/N+N=24
N+N*N/N=24
N*N/(N+N)=24
N*(N/N+N)=24
(N+N/N)*N=24
N*N/N-N=24
N*N/(N-N)=24
N*(N/N-N)=24
N*N/N*N=24
N*N*N/N=24
N*N/(N*N)=24
N*N/N/N=24
N*N/N/N=24
N*N/(N/N)=24
N*N/N*N=24
N*N*N/N=24
N/N+N+N=24
N+N+N/N=24
N/(N+N)+N=24
N+N/(N+N)=24
N/(N+N+N)=24
N/N+N-N=24
N-N+N/N=24
N/(N+N)-N=24
N/(N+N-N)=24
N/N+N*N=24
N*N+N/N=24
N/(N+N)*N=24
N*N/(N+N)=24
(N/N+N)*N=24
(N+N/N)*N=24
N/(N+N*N)=24
N/N+N/N=24
N/(N+N)/N=24
(N/N+N)/N=24
(N+N/N)/N=24
N/(N+N/N)=24
N/((N+N)/N)=24
N/(N+N)*N=24
N*N/(N+N)=24
N/N-N+N=24
N-N+N/N=24
N/N-(N+N)=24
N/N-N-N=24
N/(N-N)+N=24
N+N/(N-N)=24
N/(N-N+N)=24
N/(N+N-N)=24
N/(N-(N+N))=24
N/(N-N-N)=24
N/N-N-N=24
N/N-(N-N)=24
N/N-N+N=24
N+N/N-N=24
N/(N-N)-N=24
N/(N-N-N)=24
N/(N-(N-N))=24
N/(N-N+N)=24
N/(N+N-N)=24
N/N-N*N=24
N/(N-N)*N=24
N*N/(N-N)=24
N/(N-N*N)=24
(N/N-N)*N=24
N/N-N/N=24
N/(N-N)/N=24
(N/N-N)/N=24
N/(N-N/N)=24
N/((N-N)/N)=24
N/(N-N)*N=24
N*N/(N-N)=24
N/N*N+N=24
N+N*N/N=24
N/N*(N+N)=24
(N+N)*N/N=24
N/(N*N+N)=24
N/(N+N*N)=24
N/(N*(N+N))=24
N/N/(N+N)=24
N/(N+N)/N=24
N/N*N-N=24
N*N/N-N=24
N/N*(N-N)=24
N*(N-N)/N=24
N/(N*N-N)=24
N/(N*(N-N))=24
N/N/(N-N)=24
N/(N-N)/N=24
N/(N*N)-N=24
N/N/N-N=24
N/N*N*N=24
N*N*N/N=24
N/(N*N)*N=24
N/N/N*N=24
N*N/N/N=24
N/(N*N*N)=24
N/N/N/N=24
N/N*N/N=24
N*N/N/N=24
N/(N*N)/N=24
N/N/N/N=24
N/(N*N/N)=24
N/N/N*N=24
N*N/N/N=24
N/N/N+N=24
N/N/(N+N)=24
N/(N/N+N)=24
N/(N+N/N)=24
N/(N/(N+N))=24
N/N*(N+N)=24
(N+N)*N/N=24
N/N/N-N=24
N/N/(N-N)=24
N/(N/N-N)=24
N/(N/(N-N))=24
N/N*(N-N)=24
(N-N)*N/N=24
N/N/N*N=24
N*N/N/N=24
N/N/(N*N)=24
N/N/N/N=24
N/(N/N)*N=24
N/N*N*N=24
N*N*N/N=24
N/(N/N*N)=24
N/N*N/N=24
N*N/N/N=24
N/N/N/N=24
N/N/(N/N)=24
N/N/N*N=24
N*N/N/N=24
N/(N/N)/N=24
N/N*N/N=24
N*N/N/N=24
N/(N/N/N)=24
N/N*N/N=24
N*N/N/N=24
算一算，要求出所有组合的解，需要穷举多少种可能
需要穷举的运算式一共有50个
之前说一共有715组，这715组每个组一共有4！=24中排列方式，24钟排列方式代入到50个运算式，则一共需要穷举
715*24*50=858000
是不是远小于之前的2779920种
既然都是穷举，还不如把所有的结果都保存起来，这样穷举的可能性就只有200种不到了，秒杀所有的算法
我想说的是，有时查表计算并不是一种坏的算法。要知道很多语言中求三角函数都是利用查表来快速计算的
最后，说一句题外话，请教各位网友一个计算机的问题
我有一台电脑，WIN7系统。近阶段出现一个怪现象
在开机进入系统后，插入U盘，能正确识别使用U盘
在过了一段时间后（大约半小时后），再插入U盘，要么没有反应，要么能识别出盘符，但是不能识别U盘内的东西。
重启系统后，还是在进入系统后能识别U盘，但过了一段时间，问题照旧。
哪位网友能给出解决方案？
阅读(...) 评论()