- 浏览: 197392 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
NIghtmare28:
太好用了, 谢谢
Create Local Cloudera Parcels Repo to Save Your ASS -
oyxccyj:
你好,请问下你如上的问题解决了吗?我现在也遇到同样的问题,网上 ...
Homework - HBase Shell, Java Client and MapReduce Job -
20131007:
用java描述算法?
基础数据结构和算法二:Selection sort -
ender35:
第二种实现仅能用于数组排序
计数排序(Counting Sort) -
fy616508150:
我想知道有括号参加运算怎么办
算24算法实现
1、 概述
给定4个整数,其中每个数字只能使用一次;任意使用 + - * / ( ) ,构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏。这方面的程序很多,一般都是穷举求解。本文介绍一种典型的算24点的程序算法,并 给出两个具体的算24点的程序:一个是面向过程的C实现,一个是面向对象的java实现。
2、基本原理
基本原理是穷举4个整数所有可能的表达式,然后对表达式求值。
表达式的定义: expression = (expression|number) operator (expression|number)
因为能使用的4种运算符 + - * / 都是2元运算符,所以本文中只考虑2元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。
由上所述,构造所有可能的表达式的算法如下:
(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
(2.1) 对 + - * / 每一个运算符,
(2.1.1) 根据此排列的两个数字和运算符,计算结果
(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组,重复步骤 2
(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉
可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。
在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。
括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。
这是 csdn 算法论坛前版主海星的代码,程序非常简练、精致:(由busycai注释)
/***** * *算 24点(包括小数) *输出计算过程 * *****/ #include <iostream> #include <string> #include <cmath> using namespace std; const double PRECISION = 1E-6; const int COUNT_OF_NUMBER = 4; const int NUMBER_TO_BE_CAL = 24; double number[COUNT_OF_NUMBER]; string expression[COUNT_OF_NUMBER]; bool Search(int n) { /*n==1表示一次计算结束,number[0]中即为计算的结果*/ if (n == 1) { if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) { /*expression[0]中保存了求解过程*/ cout << expression[0] << endl; return true; } else { return false; } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { double a, b; string expa, expb; a = number[i]; b = number[j]; /********************************** *将剩下的有效数字往前挪, *由于两数计算结果保存在number[i]中, *所以将数组末元素覆盖number[j]即可 **********************************/ number[j] = number[n - 1]; expa = expression[i]; expb = expression[j]; expression[j] = expression[n - 1]; /*计算a+b*/ expression[i] = '(' + expa + '+' + expb + ')'; number[i] = a + b; if ( Search(n - 1) ) return true; /*计算a-b*/ expression[i] = '(' + expa + '-' + expb + ')'; number[i] = a - b; if ( Search(n - 1) ) return true; /*计算b-a*/ expression[i] = '(' + expb + '-' + expa + ')'; number[i] = b - a; if ( Search(n - 1) ) return true; /*计算(a*b)*/ expression[i] = '(' + expa + '*' + expb + ')'; number[i] = a * b; if ( Search(n - 1) ) return true; /*计算(a/b)*/ if (b != 0) { expression[i] = '(' + expa + '/' + expb + ')'; number[i] = a / b; if ( Search(n - 1) ) return true; } /*计算(b/a)*/ if (a != 0) { expression[i] = '(' + expb + '/' + expa + ')'; number[i] = b / a; if ( Search(n - 1) ) return true; } /*恢复现场*/ number[i] = a; number[j] = b; expression[i] = expa; expression[j] = expb; } } return false; } void main() { for (int i = 0; i < COUNT_OF_NUMBER; i++) { char buffer[20]; int x; cin >> x; number[i] = x; itoa(x, buffer, 10); expression[i] = buffer; } if ( Search(COUNT_OF_NUMBER) ) { cout << "Success." << endl; } else { cout << "Fail." << endl; } }
使用任一个 c++ 编译器编译即可。
4、Java实现
这里的Java实现只是本人模仿C++代码编写,面向对象的版本再进一步补充。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class TwentyFourWithoutGUI { private static final int COUNT_OF_NUMBER = 4; private static final int NUMBER_TO_REATCH = 24; // 精度 private static final double PRECISION = 1E-6; // 存放计算的表达式串 private static String[] expression = new String[COUNT_OF_NUMBER]; // 四个实数,计算24点,因为可能有小数 private static double[] number = new double[COUNT_OF_NUMBER]; static boolean searchResult(int n) { // 递归结束条件 if (n == 1) return (Math.abs(number[0] - NUMBER_TO_REATCH) < PRECISION); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // 进行组合 double opNumber1 = number[i]; // 保存起来,在方法最后再恢复,以便继续计算 double opNumber2 = number[j]; // 保存起来,在方法最后再恢复,以便继续计算 number[j] = number[n - 1]; // 将最后一个数挪过来 String exp1 = expression[i]; // 保存起来,在方法最后再恢复,以便继续计算 String exp2 = expression[j]; // 保存起来,在方法最后再恢复,以便继续计算 expression[j] = expression[n - 1]; // 将最后一个式子挪过来 expression[i] = "(" + exp1 + " + " + exp2 + ")"; // 看看加法能否算出 // 将运算结果放在number[i]中 number[i] = opNumber1 + opNumber2; if (searchResult(n - 1)) return true; expression[i] = "(" + exp1 + " - " + exp2 + ")"; // 看看减法能否算 number[i] = opNumber1 - opNumber2; if (searchResult(n - 1)) return true; expression[i] = "(" + exp2 + " - " + exp1 + ")"; number[i] = opNumber2 - opNumber1; if (searchResult(n - 1)) return true; expression[i] = "(" + exp1 + " * " + exp2 + ")"; // 看看乘法能否算 number[i] = opNumber1 * opNumber2; if (searchResult(n - 1)) return true; if (opNumber2 != 0) { expression[i] = "(" + exp1 + " / " + exp2 + ")"; // 看看除法能否算 number[i] = opNumber1 / opNumber2; if (searchResult(n - 1)) return true; } if (opNumber1 != 0) { expression[i] = "(" + exp2 + " / " + exp1 + ")"; number[i] = opNumber2 / opNumber1; if (searchResult(n - 1)) return true; } number[i] = opNumber1; // 恢复 number[j] = opNumber2; expression[i] = exp1; expression[j] = exp2; } } return false; } public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String oneLine = reader.readLine(); String[] nums = oneLine.split(" "); // 仅仅是演示,确保输入4个不为0的正整数 for (int i = 0; i < COUNT_OF_NUMBER; i++) { number[i] = Integer.parseInt(nums[i]); expression[i] = nums[i]; } searchResult(COUNT_OF_NUMBER); System.out.println(expression[0]); } }注意:main方法中的代码并未对输入异常等进行处理,仅仅是演示。
发表评论
-
基础数据结构和算法十四:Directed Graphs
2013-12-15 22:40 1749In directed graphs, edges a ... -
基础数据结构和算法十三:Undirected Graphs (2)
2013-12-13 22:51 1009Design pattern for graph p ... -
基础数据结构和算法十三:Undirected Graphs
2013-12-13 20:15 1153A graph is a set of vertices ... -
基础数据结构和算法十二:Hash table
2013-12-02 22:06 977Search algorithms that use ... -
基础数据结构和算法十一:Red-black binary search tree
2013-12-01 12:12 1474The insertion algorithm fo ... -
基础数据结构和算法十:2-3 search tree
2013-11-30 11:07 1169Binary search tree works w ... -
基础数据结构和算法九:Binary Search Tree
2013-11-28 22:39 1612A binary search tree (BST) ... -
基础数据结构和算法八:Binary search
2013-11-28 21:21 1083Binary search needs an ordere ... -
基础数据结构和算法七:Priority queue & Heap sort
2013-11-27 19:47 2655Some important applications o ... -
基础算法七: Priority queue & Heap sort
2013-11-26 21:46 0Some important applications ... -
基础数据结构和算法六:Quick sort
2013-11-21 19:33 1182Quick sort is probably used m ... -
Inversions of an array
2013-11-20 22:28 0TODO -
基础数据结构和算法五:Merge sort
2013-11-20 21:44 1935One of mergesort’s most at ... -
基础数据结构和算法四:Shell sort
2013-11-20 19:11 1129Shellsort is a simple exte ... -
Comparing two sorting algorithms
2013-11-19 21:16 765Generally we compare algorith ... -
基础数据结构和算法三:Insertion Sort
2013-11-19 21:06 940As in selection sort, the ite ... -
基础数据结构和算法二:Selection sort
2013-11-19 20:57 1120One of the simplest sortin ... -
基础数据结构和算法一:UnionFind
2013-11-19 20:47 1229The problem that we consid ... -
Three-sum with linear time complexity
2013-09-14 10:08 0TODO package org.george.algor ... -
Blooming Filter in Hadoop
2013-07-27 22:49 0TODO
相关推荐
24点算法的实现.24点算法的实现.24点算法的实现.
给定4个整数,其中每个数字只能使用一次;任意使用 + - * / ( ) ,构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏。这方面的程序很多,一般都是穷举求解。本程序通过递归算法实现实现24点计算,
实现了24点游戏的算法,只需输入4个数字就可以打印有多少种算出24点的方法
算24点 算法经典 回溯法 简单实现,简单改一下格式,就要成为自己的了!
C++ 递归实现24点算法, 输入数组,返回所有可以组成24点的结果,并且自动去重 结果为算式 如: (2+10)*2*1=24
3.请编写程序,利用冒泡算法实现对数组{25,24,12,76,101,96,28} 的排序。
明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1)分组后的明文组和56位的密钥按位替代或交换的方法形成密文组的加密方法。
实验1:实现红黑树的基本算法, 对n的取值分别为 12、24、36、48、60,随机生成n 个互异的正整数(K1, K2, K3, ……, Kn)作为节点的关键字,向一棵初始空的红黑树中依次插入这n 个节点,统计算法运行所需时间 ,画...
在移动端需要安全算法时,直接使用开源库可能不合适(开源库都比较大,也可以自己抽取需要的代码),本Demo是根据AES的原理来实现算法,采用ECB/PKCS5Padding,实现短小精悍!! 注意:本算法在生成加密key时,使用...
3.5 粒子群算法实现智能组卷的关键技术 22 3.5.1 惯性权重的设计 22 3.5.2 加速因子的确定 22 3.5.3 粒子群数量的选择 23 3.5.4 迭代中止的判定 24 4. 智能组卷系统的实现 26 4.1 开发环境和开发工具 26 4.2 智能组...
范例1-11 三角矩阵建立 24 ∷相关函数:Store函数 1.1.12 对称矩阵的建立 25 范例1-12 对称矩阵的建立 25 ∷相关函数:store函数 1.1.13 字符串长度的计算 28 范例1-13 字符串长度的计算 28 ∷相关函数:strlen函数 ...
基于C语言的图像去噪算法设计与实现
在一幅图像中,选取一个种子点,以一定的生长规则进行生长,最终使具有相似性质的像元合并在一起,实现图像分割
输入四个随意的数字,运算出结果等于24,列出多种算法
网上找了些java实现24点小游戏的算法,看了一下,头都晕了! 自己写了一个类,各位可以看一下思路,如果需要的话,只要实例化PointGame类并在构造方法里传递参与计算的四个数字和需要的结果就好了,然后调用get...
代码里所用的例子是算法导论第三版第24章讲dijkstra时所用的例题
快算24,即为随机几个数字(1-9)通过一些加减乘除符号使计算的结果等于24,每个数字不得重复,通过该程序可以实现指定的四个数字所有解法,为解题教学提供解答思路,仅供参考。 在线访问网站:...
给4个整数,只用加减乘除,得出所有能得到24的算法 //基本思想是用3个运算符和4个数的排列组合进行穷举 //为了实现循环,自定义了4个运算符,并放入函数数组中
算法大全第24章_时间序列模型.pdf 算法大全第25章__存贮论.pdf 算法大全第26章__经济与金融中的优化问题.pdf 算法大全第27章__生产与服务运作管理中的优化问题.pdf 算法大全第28章__灰色系统理论及其应用.pdf 算法...