Java利用递归算法实现24点游戏
24点游戏
经典的纸牌益智游戏，常见游戏规则：
从扑克中每次取出4张牌。使用加减乘除，第一个能得出24者为赢。（其中，J代表11，Q代表12，K代表13，A代表1），按照要求编程解决24点游戏。
基本要求： 随机生成4个代表扑克牌牌面的数字字母，程序自动列出所有可能算出24的表达式，用擅长的语言（C/C++/Java或其他均可）实现程序解决问题。
1.程序风格良好(使用自定义注释模板)
2.列出表达式无重复。
提高要求：用户初始生命值为一给定值（比如3），初始分数为0。随机生成4个代表扑克牌牌面的数字或字母，由用户输入包含这4个数字或字母的运算表达式（可包含括号），如果表达式计算结果为24则代表用户赢了此局。
1. 程序风格良好(使用自定义注释模板)
2.使用计时器要求用户在规定时间内输入表达式，如果规定时间内运算正确则加分，超时或运算错误则进入下一题并减少生命值（不扣分）。
3.所有成绩均可记录在TopList.txt文件中。
一. 算法思路
输入四个数n1,n2,n3,n4，求解目标数T=24，以及一组计算操作符"+" "-" "*" "/" ，求所有由该组数字及操作符组成的多项式表达式集合，其值等于目标数T ，即T = 24。
算法思路如下：
1.在集合{n1,n2,n3，n4}中，首先取两个数字,如n1,n2,与操作符集合进行组合，分别得到一组表达式：n1*n2,n1+n2,n1-n2,n1/n2,n2-n1,n2/n1.(其中由于"-"和"/"操作符，左右互换会导致计算结果不同，所以在该组合中，包含"-"和"/"操作符的表达式各有两个，操作数先后顺序不同)；
2.对于新得到的每个表达式，都可以和原集合中剩下的元素，组合成新的集合组，同时，我将每次得到的表达式，都用"()"包住，以保证计算先后顺序：
{(n1*n2),n3,n4}，{(n1+n2),n3,n4}，{(n1-n2),n3,n4}，{(n1/n2),n3,n4}，{(n2-n1),n3,n4}，{(n2/n1),n3,n4}；
3.基于以上方法，对集合中所有元素进行两两组合，并与剩余元素形成新的集合。由此，我们得到了一组元素为k-1个的集合组
4.对新集合组中的每一个集合，重复以上1-3步，可得到一组包含k-2个元素的集合组...以此类推，最后会得到一组集合，其中每个集合都只包含一个元素，这个就是我们合成的最终表达式
5.对第四步得到的表达式集合进行求解，判断其是否等于目标数24，将符合条件的过滤出来，即得到所有满足条件的表达式。
package TwentyfourGame;
import java.util.ArrayList;
import java.util.Scanner;
public class TfGame {
public static void main(String[] args) {
//输入提示
System.out.println("—————————欢迎进入24点游戏———————————");
System.out.println("请随机输入四个1-13之间的整数（以空格隔开）：");
ArrayList<Integer> list = inputNum(); //调用输入函数
tfCal(list, new ArrayList<String>()); //计算24点方法, 实参list为输入的数据, new ArrayList<String>()用来 表示计算过程
System.out.println("——————————————end———————————————");
}
//输入方法，将输入的四个数存入数组队列list中，并返回
private static ArrayList<Integer> inputNum() {
ArrayList<Integer> alist = new ArrayList<Integer>(); //ArrayList<Integer>表示只能接收整型数据
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < 4; i++) { //将四个数添加到数组队列中
alist.add(scanner.nextInt());
}
return alist; //返回值为数组队列中的四个数
}
//计算24点游戏的方法
public static boolean tfCal(ArrayList<Integer> list, ArrayList<String> str) {
int length = list.size();
if (length > 1) {
/**利用双重循环取出两个数的计算所有情况
* 若list的长度为4，那么第一个数的下标和第二个数的下标分别为
* 0 1
* 1 2
* 2 3
*/
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j < length; j++) {
//加法运算
int b = list.remove(j); //移除list中的下标为j的元素，并将此数赋值给b
int a = list.remove(i); //同上，将值赋给a
list.add(0, a + b); //将两数的计算结果添加到原队列
str.add(a + "+" + b + "=" + (a + b));//此处是保存计算的过程
tfCal(list, str); //递归调动
//下面四句话是为了还原list队列，特别强调进栈和出栈的顺序
list.remove(0);
list.add(i, a);
list.add(j, b);
str.remove(str.size() - 1);
//减运算(a-b)，原理与上面加法计算相同
b = list.remove(j);
a = list.remove(i);
list.add(0, a - b);
str.add(a + "-" + b + "=" + (a - b));
tfCal(list, str);
list.remove(0);
list.add(i, a);
list.add(j, b);
str.remove(str.size() - 1);
//减运算(b-a)
b = list.remove(j);
a = list.remove(i);
list.add(0, b - a);
str.add(b + "-" + a + "=" + (b - a));
tfCal(list, str);
list.remove(0);
list.add(i, a);
list.add(j, b);
str.remove(str.size() - 1);
//乘运算
b = list.remove(j);
a = list.remove(i);
list.add(0, a * b);
str.add(a + "*" + b + "=" + (a * b));
tfCal(list, str);
list.remove(0);
list.add(i, a);
list.add(j, b);
str.remove(str.size() - 1);
//除运算(a/b)
b = list.remove(j);
a = list.remove(i);
if (b != 0 && a % b == 0) {
list.add(0, a / b);
str.add(a + "/" + b + "=" + (a / b));
tfCal(list, str);
list.remove(0);
list.add(i, a);
list.add(j, b);
str.remove(str.size() - 1);
} else {
list.add(i, a);
list.add(j, b);
}
//除运算(b/a)
b = list.remove(j);
a = list.remove(i);
if (a != 0 && b % a == 0) {
list.add(0, b / a);
str.add(b + "/" + a + "=" + (b / a));
tfCal(list, str);
list.remove(0);
list.add(i, a);
list.add(j, b);
str.remove(str.size() - 1);
} else {
list.add(i, a);
list.add(j, b);
}
}
}
} else {
if (str.get(str.size() - 1).endsWith("=24")) { //endsWith()方法用于测试字符串是否以指定后缀结束
for (String temp : str) {
System.out.print(temp + " ");
}
System.out.println();
}
}
}
}二.运行结果
三.学习心得
自己的算法学习有待提高，需要不断锻炼逻辑思维能力。