花了一下午,搞定了24点的算法,看过代码的应该知道,其实还可以计算其他任意整数点(当然没严格测试过),当然这肯定不是最优算法,希望高手拍砖。下面直接上代码,注释比较详细
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* 用给定的4个整数通过加减乘除运算得到24点,如果有多种情况,则全部输出,如果不能得到24点,输出提示<br>
*
* @思路:将指定的4个数字进行全排列,将运算符‘+’、‘-’、‘*’、‘/’取3个进行所有情况排列,
* 然后将所有的数字排列与所有的运算符排列按顺序计算,
* 如果最后计算结果等于想要的结果值比如24,则为符合条件的运算,
* 将所有符合条件的数字排列和运算符排列存储起来,并在最后打印输出所有可能的情况
*
* @author chenjie
*
*/
public class TwentyFourPoint {
public static void main(String[] args) {
try {
Set<String> set = caculate(new int[] { 18, 18, 6, 12 }, 24);
printlnResultSet(set);
} catch (Exception e) {
// e.printStackTrace();开发期间方便查找错误,测试通过后就无需打印错误信息了
System.err.println(e.getMessage());
}
}
/**
* 打印结果集
*
* @param resultSet
* 结果集
*/
private static void printlnResultSet(Collection<String> resultSet) {
for (String str : resultSet) {
System.out.println(str);
}
}
/**
* 得到给定整形数组的全排列情况
*
* @param numbers
* 给定的整形数组
* @return 全排列数组
*/
private static int[][] arrangeAllNumbers(int[] numbers) {
List<int[]> list = new ArrayList<int[]>();
allSort(numbers, 0, numbers.length - 1, list);
int[][] resultSet = new int[list.size()][list.get(0).length];
resultSet = list.toArray(resultSet);
return resultSet;
}
/**
* 得到给定的操作中出现的所有操作符排列情况
*
* @param operators
* 出现的操作符数组
* @param number
* 每组操作符的数量
* @return 所有操作符排列数组
*/
private static char[][] arrangeAllOperators(char[] operators, int number) {
int setSize = (int) Math.pow(operators.length, number);
int index = 0;
char[][] resultSet = new char[setSize][number];
for (int i = 0; i < operators.length; i++) {
for (int j = 0; j < operators.length; j++) {
for (int k = 0; k < operators.length; k++) {
resultSet[index][0] = operators[i];
resultSet[index][1] = operators[j];
resultSet[index][2] = operators[k];
index++;
}
}
}
return resultSet;
}
/**
* 根据给定的一组整数,通过加减乘除运算,得到想要的结果,如果可以得到结果,则返回所有可能的结果的运算形式。
* 返回的运算形式,均按从左到右的顺序计算,并不是遵循四则运算法则,比如:<br>
* 输出的结果形式为:<br>
* 1 * 8 - 6 * 12 = 24 <br>
* 表示的运算顺序是:<br>
* 1:1 * 8 = 8,<br>
* 2:8 - 6 = 2,<br>
* 3:2 * 12 = 24<br>
* 而不是按照四则运算法则计算:<br>
* 1:1 * 8 = 8,<br>
* 2:6 * 12 = 72,<br>
* 3:8 * 72 = 576<br>
*
*
* @param numbers
* 给定进行运算的一组整数,4个数为一组
* @param targetNumber
* 想要得到的结果
* @return 所有可能得到想要的结果的所有运算形式的字符串形式集合
* @throws Exception
* 如果不能得到想要的结果,则抛出该异常,表明根据指定的一组数字通过一系列的加减乘除不能得到想要的结果
*/
public static Set<String> caculate(int[] numbers, int targetNumber)
throws Exception {
Set<String> resultSet = new HashSet<String>();// 这里用Set而不是用List,主要是因为当给定的一组数字中如果有重复数字的话,同一结果会被出现多次,如果用List存放的话,会将重复的结果都存放起来,而Set会自动消除重复值
char[][] operatorsArrangement = arrangeAllOperators(new char[] { '+',
'-', '*', '/' }, 3);
int[][] numbersArrangement = arrangeAllNumbers(numbers);
for (int[] nums : numbersArrangement)
for (char[] operators : operatorsArrangement) {
int result = 0;
try {
result = caculate(nums, operators);
} catch (Exception e) {// 出现非精确计算
continue;
}
if (result == targetNumber)
resultSet.add(buildString(nums, operators, targetNumber));// 如果计算后的结果等于想要的结果,就存放到集合中
}
if (resultSet.isEmpty())
throw new Exception("给定的数字:" + Arrays.toString(numbers)
+ "不能通过加减乘除运算得到结果:" + targetNumber);
return resultSet;
}
/**
* 将一组整型数字以给定的操作符按顺序拼接为一个完整的表达式字符串
*
* @param nums
* 一组整型数字
* @param operators
* 一组操作符
* @param target
* 目标值
* @return 拼接好的表达式字符串
*/
private static String buildString(int[] nums, char[] operators, int target) {
String str = String.valueOf(nums[0]);
for (int i = 0; i < operators.length; i++) {
str = str + ' ' + operators[i] + ' ' + nums[i + 1];
}
str = str + " = " + target;
return str;
}
/**
* 将给定的一组数字以给定的操作符按顺序进行运算,如:int result = caculate(new int[]{3,4,5,8}, new
* char[]{'+','-','*'});
*
* @param nums
* 一组数字
* @param operators
* 一组运算符,数量为数字的个数减1
* @return 最后的计算结果
* @throws Exception
* 当计算结果不精确时,抛出该异常,主要是针对除法运算,例如18 / 8 = 2,诸如这样不精确计算将抛出该异常
*/
private static int caculate(int[] nums, char[] operators) throws Exception {
int result = 0;
for (int i = 0; i < operators.length; i++) {
if (i == 0) {
result = caculate(nums[i], nums[i + 1], operators[i]);
} else {
result = caculate(result, nums[i + 1], operators[i]);
}
}
return result;
}
/**
* 根据指定操作符将两个给定的数字进行计算
*
* @param num1
* 数字1
* @param num2
* 数字2
* @param operator
* 操作符,只能从“+、-、*、/”4个操作符中取值
* @return 计算结果
* @throws Exception
* 当计算结果不精确时,抛出该异常,主要是针对除法运算,例如18 / 8 = 2,诸如这样不精确计算将抛出该异常
*/
private static int caculate(int num1, int num2, char operator)
throws Exception {
double result = 0;
switch (operator) {// 根据操作符做相应的计算操作
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = (double) num1 / (double) num2;
break;
}
if (!check(result))
throw new Exception("不精确的计算数字");
return (int) result;
}
/**
* 检查指定的浮点数是否可以直接转换为整型数字而不损失精度
*
* @param result
* 要检查的浮点数
* @return 如果可以进行无损转换,返回true,否则返回false
*/
private static boolean check(double result) {
String str = String.valueOf(result);
int pointIndex = str.indexOf(".");// 小数点的下标值
String fraction = str.substring(pointIndex + 1);
return fraction.equals("0") ? true : false;// 通过判断小数点后是否只有一个0来确定是否可以无损转换为整型数值
}
/**
* 对传入的整型数组buf进行全排列
*
* @param buf
* 要进行全排列的整型数组
* @param start
* 开始的下标值
* @param end
* 结束下标值
* @param list
* 保存最后全排列结果的集合
*/
private static void allSort(int[] buf, int start, int end, List<int[]> list) {
if (start == end) {// 当只要求对数组中一个字母进行全排列时,只要就按该数组输出即可
int[] a = new int[buf.length];
System.arraycopy(buf, 0, a, 0, a.length);
list.add(a);
} else {// 多个字母全排列
for (int i = start; i <= end; i++) {
int temp = buf[start];// 交换数组第一个元素与后续的元素
buf[start] = buf[i];
buf[i] = temp;
allSort(buf, start + 1, end, list);// 后续元素递归全排列
temp = buf[start];// 将交换后的数组还原
buf[start] = buf[i];
buf[i] = temp;
}
}
}
}
分享到:
相关推荐
java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法大全源码java算法...
遗传算法在Java排课系统中的应用涉及到以下几个关键知识点: 1. **遗传算法**:遗传算法是一种全局优化方法,通过模拟生物进化的遗传过程,包括选择、交叉和变异操作,来逐步改进解的质量。在排课问题中,每个解...
Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法...
一个java24点算法
在Java中实现祖冲之密码算法,你需要熟悉以下知识点: 1. **Java基本编程**:理解和掌握Java的基础语法,包括变量、条件语句、循环、数组和类等。 2. **位操作**:祖冲之算法涉及到大量的位操作,如位移、按位与、...
Java KMeans聚类算法是一种广泛应用的数据挖掘技术,用于将数据集分成不同的组或“簇”,使得同一簇内的数据点彼此相似,而不同簇之间的数据点差异较大。在本例中,描述提到了从Pascal语言转换到Java实现,这意味着...
本项目提供了一些推荐算法的Java实现,包括slopeone、SVD(奇异值分解)以及基于物品邻接的SVD(ItemNeighborSVD)。下面我们将详细探讨这些算法及其在Java中的实现。 1. **slopeone**: - Slope One是一种简单的...
在SM2.java和SM3.java文件中,你应该能找到对应算法的具体实现,包括加密、解密、签名和验签的函数。 为了在Java项目中使用这些国密算法,你需要引入支持国密的库,如Bouncy Castle或Chinese Cryptography ...
神经网络算法 java 源代码神经网络算法 java 源代码神经网络算法 java 源代码
网上找了些java实现24点小游戏的算法,看了一下,头都晕了! 自己写了一个类,各位可以看一下思路,如果需要的话,只要实例化PointGame类并在构造方法里传递参与计算的四个数字和需要的结果就好了,然后调用get...
JAVA实现扫描线算法的知识点总结 扫描线算法是计算机图形学中的一种常用算法,用于实现多边形的扫描线填充。下面是JAVA实现扫描线算法的知识点总结: 1. 扫描线算法的基本概念: 扫描线算法是从Ymin开始扫描,...
在这个Java实现的项目中,"Shamir密钥分享算法java.rar"包含了一个带有GUI图形界面的应用程序。用户可以输入要加密的字符串,设置共享值m(即总共生成的子密钥数量)和门限值n。这些参数决定了密钥的分散方式和重新...
背包算法 背包算法JAVA实现 背包算法JAVA实现
【数值算法——JAVA实现的插值算法.示例】
通过运行这个Java源代码,用户可以观察到人工鱼群算法如何逐步接近二元二次函数的极值点。对于初学者来说,这是一个很好的学习资源,可以帮助理解人工鱼群算法的工作原理,并为实际问题的优化提供基础。对于有经验的...
java版的DBSCAN聚类算法实现,是典型的算法思路实现,遍历未访问的所有点,如果是核心点,就新建一个簇,然后遍历其邻域内的所有点集A,不断扩展,如果簇内的点时核心点,就将其邻域所有点纳入点集A,并从点集移除已...
道格拉斯-普克抽稀算法,java 实现
在Java版的五子棋实现中,首先我们需要创建一个棋盘模型,通常使用二维数组来模拟棋盘,每个元素代表棋盘上的一个位置。数组的值可以表示棋子的颜色(例如,0表示空位,1表示黑棋,2表示白棋)。棋盘大小通常是15x15...
Description: Java经典算法java经典算法java经典算法java经典算法java经典算法java经典算法java经典算法java经典算法 Tags: Java经典算法 Java经典算法合集是Java编程语言中的一些经典算法的集合,这些算法涵盖了...