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-6vector
vec;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-6vector
vec;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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Python 爬虫-Scrapy框架基本使用
下一篇:Python 爬虫-股票数据的Scrapy爬虫

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月03日 11时13分40秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

oracle同时报604和12507,V$SES_OPTIMIZER_ENV 查不到刚修改的隐含参数, 2019-04-21
zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解 2019-04-21
linux配置匿名ftp服务器,在Linux环境中使用vsftpd搭建ftp实现匿名上传详细配置 2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘 2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD 2019-04-21
.net core linux 桌面应用,C# dotnet core + AvaloniaUI 开发桌面软件,hello world 2019-04-21
linux tcp 113错误,linux系统报tcp_mark_head_lost错误的处理方法 2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式... 2019-04-21
python学画画_python学画画(下) 2019-04-21
云栖社区 mysql_【直播结束,已更新回放】PG、MySQL到底哪个好?云栖说这次请来五位专家撕了一下-阿里云开发者社区... 2019-04-21
老男孩mysql 百度云_英语语录:除了你,没人能掌控你的幸福 2019-04-21
mysql驱动多次执行问题_Laravel5.2队列驱动expire参数设置带来的重复执行问题 数据库驱动... 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