题目入下:
计算21是流行的扑克游戏。其方法是任意取出4张牌,A J Q K 王牌 算 1,其它牌按点数计算,花色不计。目标是通过加、减、乘、除和括号最终算出24。设计一个程序,输入4个数字(1~10),则列出所有可能计算结果为24的方案。要求:
方案不能重复(加法乘法交换律等算不同方案)。
计算中局部可以为分数,结果为整数即可(如 3 3 7 7 算法: (3 + 3/7)*7)
如果没有找到方案输出:无解。请大家给个思路
计算21是流行的扑克游戏。其方法是任意取出4张牌,A J Q K 王牌 算 1,其它牌按点数计算,花色不计。目标是通过加、减、乘、除和括号最终算出24。设计一个程序,输入4个数字(1~10),则列出所有可能计算结果为24的方案。要求:
方案不能重复(加法乘法交换律等算不同方案)。
计算中局部可以为分数,结果为整数即可(如 3 3 7 7 算法: (3 + 3/7)*7)
如果没有找到方案输出:无解。请大家给个思路
解决方案 »
- 关于使用jdbc连接sqlserver2000数据库问题。
- 串口通读问题!(ID卡)
- 请教jstl的问题
- java swing的打印能够判断出当前打印机的状态?
- 配置文件采用xml格式,配置信息采用层次结构,如何根据层次读出这些配置信息?
- jb8有中文版吗?汉化包在那里下?
- 什么是JAVADOC?
- 请问哪里有Bas4.5(Or Bas5.0???)下载?谢谢了。
- java 收发email,如何作,很迷茫呀,java 初手!
- 对象,实例,reference有什么区别吗
- 不显示删除回复显示所有回复显示星级回复显示得分回复 跪求《Thinking in Java》教材的课后习题答案(附加小问题的)(一个大一菜鸟的发问)
- 看到一个面试题,大家来讨论下!
问题是出来很多计算机认为不重复,但是在人看来应该算是重复的可行解
基本思路就是用map存储所有解的表达式和结果值,最后判断输出可行解
import java.util.HashMap;/*
* 任意四个数 1~10 输出他们运算结果为24的所有结果
* 如:3 3 7 7 (3+3/7)*7 = 24
*/
public class Test24 {
//定义最终结果集,key为操作数字的字符串(去重),value为结果
private static HashMap<String, Double> result = new HashMap<String, Double>(); public static void main(String[] args) {
double[] nums = { 3, 9, 5, 10 };
/*
* 运算分为两种情况: (2个数运算)运算(2个数运算) 和(3个数运算)运算(最后一个数)
*
* 烦人的括号啊...大多数代码都是判断括号 很雷人=。=
*/
//第一种:任选两个数(3种情况)和剩下两个数操作
// 1: 12 对 34
HashMap<String, Double> res1 = result(nums[0], nums[1]);
HashMap<String, Double> res2 = result(nums[2], nums[3]);
result.putAll(result(res1, res2));
// 2: 13 对24
HashMap<String, Double> res3 = result(nums[0], nums[2]);
HashMap<String, Double> res4 = result(nums[1], nums[3]);
result.putAll(result(res3, res4));
// 3: 14 对23
HashMap<String, Double> res5 = result(nums[0], nums[3]);
HashMap<String, Double> res6 = result(nums[1], nums[2]);
result.putAll(result(res5, res6));
/*
* 第二种:任选1个数(4种情况)和剩下三个数操作
* 可以转化为:任选2个数,操作完和第三个数操作,然后再和第四个数操作
* 总共十二种情况(下面就简写了)
* 12——3——4
* 12——4——3
* 13——2——4
* 13——4——2
* 14——2——3
* 14——3——2
* 23——1——4
* 23——4——1
* 24——1——3
* 24——3——1
* 34——1——2
* 34——2——1
*/
result.putAll(result(result(result(nums[0], nums[1]), nums[2]), nums[3]));
result.putAll(result(result(result(nums[0], nums[1]), nums[3]), nums[2]));
result.putAll(result(result(result(nums[0], nums[2]), nums[1]), nums[3]));
result.putAll(result(result(result(nums[0], nums[2]), nums[3]), nums[1]));
result.putAll(result(result(result(nums[0], nums[3]), nums[1]), nums[2]));
result.putAll(result(result(result(nums[0], nums[3]), nums[2]), nums[1]));
result.putAll(result(result(result(nums[1], nums[2]), nums[0]), nums[3]));
result.putAll(result(result(result(nums[1], nums[2]), nums[3]), nums[0]));
result.putAll(result(result(result(nums[1], nums[3]), nums[0]), nums[2]));
result.putAll(result(result(result(nums[1], nums[3]), nums[2]), nums[0]));
result.putAll(result(result(result(nums[2], nums[3]), nums[0]), nums[1]));
result.putAll(result(result(result(nums[2], nums[3]), nums[1]), nums[0]));
boolean fail = true;
for (String str : result.keySet()) {
//一般来说浮点数计算可以得到24.0的,怕意外就......
if (Math.abs(result.get(str) - 24)<0.0001) {
//去掉所有烦人的 double值后面的".0"
System.out.println(str.replaceAll("\\.0", "") + "=" + 24);
fail=false;
}
}
if(fail){
System.out.println("无可行解哦~~");
}
}
//判断一个操作串是否是加法或减法
public static boolean isAddOrDel(String str){
if(str.contains("+")||str.contains("-")){
return true;
}
return false;
} // 任意两个数运算的结果集,对于任何两个数运算结果为六种(减法和除法有两种结果)
public static HashMap<String, Double> result(double num1, double num2) {
HashMap<String, Double> map = new HashMap<String, Double>();
map.put(num1 + "+" + num2, num1 + num2);
map.put(num1 + "-" + num2, num1 - num2);
map.put(num2 + "-" + num1, num2 - num1);
map.put(num1 + "*" + num2, num1 * num2);
map.put(num1 + "/" + num2, num1 / num2);
map.put(num2 + "/" + num1, num2 / num1);
return map;
} // 对一个结果集和一个数操作得到新的结果集
public static HashMap<String, Double> result(HashMap<String, Double> map1,
double num2) {
HashMap<String, Double> map = new HashMap<String, Double>();
for (String str1 : map1.keySet()) {
//如果上一次做的是+或者-操作,那么仅有*和/需要加括号
if(isAddOrDel(str1)){
map.put( str1 + "+" + num2, map1.get(str1) + num2);
map.put( str1 + "-" + num2, map1.get(str1) - num2);
map.put(num2 + "-" + "(" + str1 + ")", num2 - map1.get(str1));
map.put("(" + str1 + ")" + "*" + num2, map1.get(str1) * num2);
map.put("(" + str1 + ")" + "/" + num2, map1.get(str1) / num2);
map.put(num2 + "/" + "(" + str1 + ")", num2 / map1.get(str1));
}else{ //上一次是乘除操作那么仅有作为被除数需要加括号
map.put( str1 + "+" + num2, map1.get(str1) + num2);
map.put( str1 + "-" + num2, map1.get(str1) - num2);
map.put(num2 + "-" + str1 , num2 - map1.get(str1));
map.put( str1 + "*" + num2, map1.get(str1) * num2);
map.put( str1 + "/" + num2, map1.get(str1) / num2);
map.put(num2 + "/" + "(" + str1 + ")", num2 / map1.get(str1));
}
}
return map;
} // 对两个结果集操作得到新的结果集
public static HashMap<String, Double> result(HashMap<String, Double> map1,
HashMap<String, Double> map2) {
HashMap<String, Double> map = new HashMap<String, Double>();
for (String str1 : map1.keySet()) {
for (String str2 : map2.keySet()) {
if(isAddOrDel(str1)&&isAddOrDel(str2)){
//两个都是加、减
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + "(" + str2 + ")", map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + "(" + str1 + ")", map2.get(str2) - map1.get(str1));
map.put("(" + str1 + ")" + "*" + "(" + str2 + ")", map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}else if(isAddOrDel(str1)&&!isAddOrDel(str2)){
//第一个是加、减
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + str2 , map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + "(" + str1 + ")", map2.get(str2) - map1.get(str1));
map.put("(" + str1 + ")" + "*" + str2, map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}else if(!isAddOrDel(str1)&&isAddOrDel(str2)){
//第二个是加、减
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + "(" + str2 + ")", map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + str1 , map2.get(str2) - map1.get(str1));
map.put(str1 + "*" + "(" + str2 + ")", map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}else{
//两个都是乘、除
map.put(str1 + "+" + str2 , map1.get(str1) + map2.get(str2));
map.put(str1 + "-" + str2 , map1.get(str1) - map2.get(str2));
map.put(str2 + "-" + str1 , map2.get(str2) - map1.get(str1));
map.put(str1 + "*" + "(" + str2 + ")", map1.get(str1) * map2.get(str2));
map.put("(" + str1 + ")" + "/" + "(" + str2 + ")", map1.get(str1) / map2.get(str2));
map.put("(" + str2 + ")" + "/" + "(" + str1 + ")", map2.get(str2) / map1.get(str1));
}
}
}
return map;
}
}输出:
(3+9)*10/5=24
(10-5)*3+9=24
10/(5/(3+9))=24
((3+9)/5)*10=24
9-((5-10)*3)=24
(3+9)/(5/10)=24
((3+9)*10)/5=24
public static boolean isAddOrDel(String str){
char sign1 = str.charAt(str.length()-4);//一般操作字符串的操作符
char sign2 = str.charAt(str.length()-5);//最后一位是10.0的操作符
if(sign1=='+'||sign2=='+'||sign1=='-'||sign2=='-'){
return true;
}
return false;
}可以去掉一些重复的,剩下的继续想。。也等高人指点
package hr.test;import java.util.*;public class game24 {
//记录结算的中间过程
public ArrayList<String> queue=new ArrayList<String>();
//24点计算
public void compute(int[] data){
if(data.length==1){
if(data[0]==24){
print(); //打印正确结果
}
return ;
}
sort(data); //逆序排序,为了使得运算中总是大数减去或除以小数
//枚举数据组中的任何两个数,进行加减乘除计算
for(int i=0;i<data.length-1;i++)
for(int j=i+1;j<data.length;j++){
//进行加法计算,将计算结果构成一个新的数据组
int[] newData=new int[data.length-1];
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]+data[j];
queue.add(data[i]+"+"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);
//进行减法计算,将计算结果构成一个新的数据组
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]-data[j];
queue.add(data[i]+"-"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);
//进行乘法计算,将计算结果构成一个新的数据组
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]*data[j];
queue.add(data[i]+"*"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);
//进行除法计算(条件,除的尽且不除以0),将计算结果构成一个新的数据组
if(data[i]%data[j]==0&&data[j]!=0){
for(int idx=1,k=0;k<data.length;k++){
if(k!=i&&k!=j) newData[idx++]=data[k];
}
newData[0]=data[i]/data[j];
queue.add(data[i]+"/"+data[j]+"="+newData[0]);
compute(newData);
queue.remove(queue.size()-1);
}
}
}
//所有数据逆序排序
public void sort(int[] data){
for(int i=1;i<data.length;i++){
int temp=data[i];
int j=i-1;
for(;j>=0;j--){
if(temp>data[j])data[j+1]=data[j];
else break;
}
data[j+1]=temp;
}
}
//打印中间过程
private void print(){
for(String q:queue)
System.out.print(q+"\t");
System.out.println();
}
//测试
public static void main(String[] args) {
game24 g=new game24();
int[] data={5,6,7,8};
g.compute(data);
}
}