24点游戏
发布日期:2022-04-02 18:15:37
浏览次数:6
分类:博客文章
本文共 5797 字,大约阅读时间需要 19 分钟。
2017-08-05 22:44:37
一、判断是否有解
问题描述:
问题求解:
public boolean judgePoint24(int[] nums) { double[] nums_ = new double[4]; for (int i = 0; i < 4; i++) nums_[i] = nums[i] * 1.0; return helper(nums_, 4); } private boolean helper(double[] nums, int n) { if (n == 1) return Math.abs(nums[0] - 24) < 0.001; double[] nums_ = Arrays.copyOf(nums, n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double[] res = calc(nums[i], nums[j]); for (double k : res) { nums_[i] = k; nums_[j] = nums[n - 1]; if (helper(nums_, n - 1)) return true; nums_[j] = nums[j]; nums_[i] = nums[i]; } } } return false; } private double[] calc(double i, double j) { return new double[]{i + j, i - j, j - i, j * i, i / j, j / i}; }
二、打印所有解
24点的计算问题我从小就在玩,而且还玩的不错。不过学习编程之后呢,一直没有系统的解决过这个问题。之前做华为的编程测试题的时候有一条算24的题,是采用的暴力枚举的方式进行的。这次采用了递归的方法进行计算。算法思想如下:
- n个数算24,必有两个数要先算。这两个数算的结果,和剩余n-2个数,就构成了n-1个数求24的问题
- 枚举先算的两个数,以及这两个数的运算方式。
- 边界条件:一个数算24
- 注意:浮点数比较是否相等,不能用 ==
double a[5];#define EPS 1e-6vectorvec;string str;bool isZero(double x) {return fabs(x) <= EPS;}string d2s(double in){ stringstream s; string rst; s< >rst; return rst;}bool count24(double a[],int n){// 用数组a 里的 n 个数,计算24 if( n == 1 ) { if(isZero( a[0] - 24) ) { for(int i=0;i < n-1; ++i) for(int j = i+1;j < n; ++j) { // 枚举两个数的组合 int m = 0; // 还剩下m 个数, m = n - 2 for(int k = 0; k < n; ++k) if( k != i && k!= j) b[m++] = a[k];// 把其余数放入b vec.push_back(a[i]); vec.push_back(a[j]); b[m] = a[i]+a[j]; str.append("+"); if(count24(b,m+1)) return true; str.pop_back(); str.append("-"); b[m] = a[i]-a[j]; if(count24(b,m+1)) return true; b[m] = a[j]-a[i]; if(count24(b,m+1)) return true; str.pop_back(); b[m] = a[i]*a[j]; str.append("*"); if(count24(b,m+1)) return true; str.pop_back(); if( !isZero(a[j])) { b[m] = a[i]/a[j]; str.append("/"); if(count24(b,m+1)) return true; str.pop_back(); } if( !isZero(a[i])) { str.append("/"); b[m] = a[j]/a[i]; if(count24(b,m+1)) return true; str.pop_back(); } vec.pop_back(); vec.pop_back(); } return false;} string print(int i,int j,double ans=24) { if(i<0||j<0) return d2s(vec[1]); if(str[j]=='+') return d2s(vec[i])+"+("+print(i-2,j-1,vec[i+1])+")"; if(str[j]=='*') return d2s(vec[i])+"*("+print(i-2,j-1,vec[i+1])+")"; if(str[j]=='-') { if(abs((vec[i]-vec[i+1]-ans))<=EPS) return d2s(vec[i])+"-("+print(i-2,j-1,vec[i+1])+")"; else return "("+print(i-2,j-1,vec[i+1])+")-"+d2s(vec[i]); } if(str[j]=='/') { if(abs((vec[i]/vec[i+1]-ans))<=EPS) return d2s(vec[i])+"/("+print(i-2,j-1,vec[i+1])+")"; else return "("+print(i-2,j-1,vec[i+1])+")/"+d2s(vec[i]); } }int main(){ for(int i = 0;i < 4; ++i) cin >> a[i]; if( count24(a,4)) { cout << "YES" << endl; cout< <
如果需要输出所有的解:
double a[5];#define EPS 1e-6vectorvec;string str;bool isZero(double x) { return fabs(x) <= EPS;}string d2s(double in){ stringstream s; string rst; s< >rst; return rst;}string print(int i,int j,double ans=24){ if(i<0||j<0) return d2s(vec[1]); if(str[j]=='+') return d2s(vec[i])+"+("+print(i-2,j-1,vec[i+1])+")"; if(str[j]=='*') return d2s(vec[i])+"*("+print(i-2,j-1,vec[i+1])+")"; if(str[j]=='-') { if(abs((vec[i]-vec[i+1]-ans))<=EPS) return d2s(vec[i])+"-("+print(i-2,j-1,vec[i+1])+")"; else return "("+print(i-2,j-1,vec[i+1])+")-"+d2s(vec[i]); } if(str[j]=='/') { if(abs((vec[i]/vec[i+1]-ans))<=EPS) return d2s(vec[i])+"/("+print(i-2,j-1,vec[i+1])+")"; else return "("+print(i-2,j-1,vec[i+1])+")/"+d2s(vec[i]); }}void count24(double a[],int n){// 用数组a 里的 n 个数,计算24 if( n == 1 ) { if(isZero( a[0] - 24) ) { for(int i=0;i < n-1; ++i) for(int j = i+1;j < n; ++j) { // 枚举两个数的组合 int m = 0; // 还剩下m 个数, m = n - 2 for(int k = 0; k < n; ++k) if( k != i && k!= j) b[m++] = a[k];// 把其余数放入b vec.push_back(a[i]); vec.push_back(a[j]); b[m] = a[i]+a[j]; str.append("+"); count24(b,m+1); str.pop_back(); str.append("-"); b[m] = a[i]-a[j]; count24(b,m+1); str.pop_back(); str.append("-"); b[m] = a[j]-a[i]; count24(b,m+1); str.pop_back(); str.append("*"); b[m] = a[i]*a[j]; count24(b,m+1); str.pop_back(); if( !isZero(a[j])) { b[m] = a[i]/a[j]; str.append("/"); count24(b,m+1); str.pop_back(); } if( !isZero(a[i])) { str.append("/"); b[m] = a[j]/a[i]; count24(b,m+1); str.pop_back(); } vec.pop_back(); vec.pop_back(); }}int main(){ for(int i = 0;i < 4; ++i) cin >> a[i]; count24(a,4); return 0;}
转载地址:https://www.cnblogs.com/hyserendipity/p/7292126.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月03日 11时13分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么?
2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍
2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解
2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘
2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD
2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式...
2019-04-21
python学画画_python学画画(下)
2019-04-21
老男孩mysql 百度云_英语语录:除了你,没人能掌控你的幸福
2019-04-21
mysql获取刚新增的数据库_如何取得刚插入数据库的数据的id mysql
2019-04-21
python将10到1递减_(Python)如何将3个递减列表合并成一个递减列表?
2019-04-21
python脚本怎么用来处理数据_长时间运行数据处理python脚本的程序结构
2019-04-21
python转成c 语言_将Python对象转换为C void类型
2019-04-21