|
锁定老帖子 主题：趣味编程：24点算法实现
精华帖 (0) :: 良好帖 (2) :: 新手帖 (2) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-01-16
最后修改：2009-01-16
for (z = 0; z < 3; z++) {
for (y = z + 1; y < 4; y++) {
b[0] = a[z] + a[y];
str1[0] = "( " + i[z] + " + " + i[y] + " )";
b[1] = a[z] - a[y];
str1[1] = "( " + i[z] + " - " + i[y] + " )";
if (b[1] < 0) {
b[1] = -b[1];
str1[1] = "( " + i[y] + " - " + i[z] + " )";
}
b[2] = a[z] * a[y];
str1[2] = "( " + i[z] + " * " + i[y] + " )";
b[3] = a[z] / a[y];
str1[3] = "( " + i[z] + " / " + i[y] + " )";
b[4] = a[y] / a[z];
str1[4] = "( " + i[y] + " / " + i[z] + " )";
w = 0;
for (x = 0; x < 4; x++) {
if (x != z && x != y) {
c[w] = x;
w++;
}
}
u = c[0];
q = c[1];
for (x = 0; x < 5; x++) {
g[0] = a[u];
str4[0] = "" + i[u] + "";
g[1] = a[q];
str4[1] = "" + i[q] + "";
g[2] = b[x];
str4[2] = "" + str1[x] + "";
for (t = 0; t < 2; t++) {
for (s = t + 1; s < 3; s++) {
f[0] = g[t] + g[s];
str2[0] = "( " + str4[t] + " + " + str4[s] + " )";
f[1] = g[t] - g[s];
str2[1] = "( " + str4[t] + " - " + str4[s] + " )";
if (f[1] < 0) {
f[1] = -f[1];
str2[1] = "( " + str4[s] + " - " + str4[t] + " )";
}
f[2] = g[t] * g[s];
str2[2] = "( " + str4[t] + " * " + str4[s] + " )";
if (g[s] != 0) {
f[3] = g[t] / g[s];
str2[3] = "( " + str4[t] + " / " + str4[s] + " )";
}
if (g[t] != 0) {
f[4] = g[s] / g[t];
str2[4] = "( " + str4[s] + " / " + str4[t] + " )";
}
for (r = 0; r < 3; r++) {
if (r != t && r != s) {
n = r;
}
}
for (p = 0; p < 5; p++) {
h[0] = f[p] + g[n];
str3[0] = " " + str2[p] + " + " + str4[n] + " = 24\n\r";
if (Math.round(h[0]*1000000)== 24000000) {
System.out.println(str3[0]);
}
h[1] = f[p] - g[n];
str3[1] = " " + str2[p] + " - " + str4[n] + " = 24\n\r";
if (h[1] < 0) {
h[1] = -h[1];
str3[1] = " " + str4[n] + " - " + str2[p] + " = 24\n\r";
}
if (Math.round(h[1]*1000000)== 24000000) {
System.out.println(str3[1]);
}
h[2] = f[p] * g[n];
str3[2] = " " + str2[p] + " * " + str4[n] + " = 24\n\r";
if (Math.round(h[2]*1000000)== 24000000) {
System.out.println(str3[2]);
}
if (g[n] != 0) {
h[3] = f[p] / g[n];
str3[3] = " " + str2[p] + " / " + str4[n] + " = 24\n\r";
if (Math.round(h[3]*1000000)== 24000000) {
System.out.println(str3[3]);
}
}
if (f[p] != 0) {
h[4] = g[n] / f[p];
str3[4] = " " + str4[n] + " / " + str2[p] + " = 24\n\r";
if (Math.round(h[4]*1000000)== 24000000) {
System.out.println(str3[4]);
}
}
}
}
}
}
}
}
|
| 返回顶楼 | |
|
发表时间：2009-01-16
很早之前的穷举法，没有考虑重复
|
| 返回顶楼 | |
|
发表时间：2009-01-16
http://andyjojo.iteye.com/upload/picture/pic/29827/ef25018e-f28c-3dda-a306-65ea3d1fd3e6.bmp
|
| 返回顶楼 | |
|
发表时间：2009-01-16
有趣， 如果有空我上一个Drools的实现
|
| 返回顶楼 | |
|
发表时间：2009-01-17
andyjojo 写道 http://andyjojo.iteye.com/upload/picture/pic/29827/ef25018e-f28c-3dda-a306-65ea3d1fd3e6.bmp
I 'm in linux without input method ,your result has duplicate at line 2 and last line ! |
| 返回顶楼 | |
|
发表时间：2009-01-20
我的思路：
穷举所有数字的组合，穷举所有运算的组合，穷举运算符与数字的组合方式，求出表达式的值，过滤出值为24的表达式。 不同运算符有优先级问题，但是我可以避免这个问题。方法就是用“逆波兰式”。 给定4个数字和3个运算符，可以试图找到所有合法的逆波兰式。逆波兰式合法的定义就是不会使得遇到操作符时，堆栈里却没有足够的操作数。只要在生成逆波兰式的时候小心一点，记得判断就可以了。 我的实现：
module Main where
import List
import Ratio
main = putStr $ unlines $ map show $ work
work = filter (\x -> eval x == 24) $
concat [applyAll nums ops | nums <- numPerms, ops<-opPerms]
numRange = [1..9]
numPerms = [[a,b,c,d] | a<-numRange, b<-numRange, c<-numRange, d<-numRange]
opList = ['+','-','*','/']
opPerms = [[x,y,z] | x<-opList, y<-opList, z<-opList]
opMap '+' = (+)
opMap '-' = (-)
opMap '*' = (*)
opMap '/' = (/)
type NumType = Double
data Elem = Num NumType | Op Char deriving (Show)
-- Given 4 numbers and 3 operators, generate all valid RPNs
applyAll :: [NumType] -> [Char] -> [[Elem]]
applyAll nums ops = applyAll' nums ops [] 0
applyAll' :: [NumType] -> [Char] -> [Elem] -> Int -> [[Elem]]
applyAll' [] [] sofar 1 = [reverse sofar]
applyAll' [] (op:ops) sofar sz = applyAll' [] ops ((Op op):sofar) (sz-1)
applyAll' (n:ns) (op:ops) sofar sz | sz>=2 =
applyAll' (n:ns) ops ((Op op):sofar) (sz-1) ++
applyAll' ns (op:ops) ((Num n):sofar) (sz+1)
applyAll' (n:ns) ops sofar sz | otherwise =
applyAll' ns ops ((Num n):sofar) (sz+1)
applyAll' _ _ _ _ = []
-- Evaluate RPN
eval :: [Elem] -> NumType
eval es = head (foldl step [] es) where
step stack (Num n) = (n:stack)
step (n1:n2:ns) (Op op) = ((opMap op) n2 n1):ns
|
| 返回顶楼 | |
|
发表时间：2009-01-21
package com.onezero;
/**
* <b>计算24游戏</b>
* <br/>
* 给出四张1到13之间的整数，通过+、-、*、/、()组合成合法表达式并使结果等于24；
* 如给出1、3、4、6，可以组合乘6/(1-(3/4))
* <br/>
* 算法仍然是穷举法，不过删除了一些重复的式子。
* 为了精确表示除法结果，这里实现<code>有理数</code>类。
* 基本思想：先在四张牌中选出两张，有6种，再计算这两张牌的值，有5种；
* 剩下两张牌及刚才计算的值可看作三张牌。在选择两张，有3种；
* 再计算，又有5种，最后剩下两张，在计算，又是5种；最后比较这些值是否等于24即可。
* 共有6*5*3*5*5=2250
* <br/>
* <b>没有除去连乘和连加的重复</b>
* <br/>
* <b>使用方法：</b><code>com.onezero.算24.计算二十四(new int[]{1,3,4,6})</code>
* @see com.onezero.有理数
* @version 1.0, 2009年1月18日
* @author Anguo Wen
*
*/
public final class 算24 {
private static int[] 四选二 = { 0, 1, 2, 3, 0, 2, 1, 3, 0, 3, 1, 2,
1, 2, 0, 3, 1, 3, 0, 2, 2, 3, 0, 1 };
private static int[] 三选二 = { 0, 1, 2, 0, 2, 1, 1, 2, 0 };
private static StringBuilder 表达式;
/**
* 计算二十四，如果有解，打印出所有的解(删除部分重复解)
*
* @param 四张牌 输入的四张1到13之间的牌
* @return 是否可以算的24
* @throws ArithmeticException 如果参数 <code>四张牌</code> 少于四个数.
*/
public static boolean 计算二十四(final int[] 四张牌) {
if(四张牌.length<4)throw new ArithmeticException("必须为四张牌");
有理数[] 纸牌 = new 有理数[4];
for(int h=0;h<4;h++)纸牌[h] = new 有理数(四张牌[h]);
boolean 成功 = false;
有理数[] 临时 = new 有理数[4];
String[] 输出 = new String[4];
有理数 结果;
四张: for (int i = 0; i < 四选二.length; i += 4) {
for (int t = 0; t < i; t += 4) {
if (重复(纸牌[四选二[i]], 纸牌[四选二[i + 1]], 纸牌[四选二[t]], 纸牌[四选二[t + 1]]))
continue 四张;
}
for (int j = 0; j < 5; j++) {
if (继续(纸牌[四选二[i]], 纸牌[四选二[i + 1]], j))
continue;
临时[0] = 计算(纸牌[四选二[i]], 纸牌[四选二[i + 1]], j,
纸牌[四选二[i]].toString(), 纸牌[四选二[i + 1]].toString());
输出[0] = 表达式.toString();
临时[1] = 纸牌[四选二[i + 2]];
输出[1] = 临时[1].toString();
临时[2] = 纸牌[四选二[i + 3]];
输出[2] = 临时[2].toString();
三张: for (int k = 0; k < 三选二.length; k += 3) {
for (int s = 0; s < k; s += 3) {
if (重复(临时[三选二[k]], 临时[三选二[k + 1]], 临时[三选二[s]],
临时[三选二[s + 1]]))
continue 三张;
}
if (k >= 6)
for (int r = 0; r < i; r += 4) {
if (重复(临时[三选二[k]], 临时[三选二[k + 1]], 纸牌[四选二[r]],
纸牌[四选二[r + 1]]))
continue 三张;
}
for (int l = 0; l < 5; l++) {
if (继续(临时[三选二[k]], 临时[三选二[k + 1]], l))
continue;
临时[3] = 计算(临时[三选二[k]], 临时[三选二[k + 1]], l, 输出[三选二[k]],
输出[三选二[k + 1]]);
输出[3] = 表达式.toString();
for (int m = 0; m < 5; m++) {
if (继续(临时[三选二[k + 2]], 临时[3], m))
continue;
结果 = 计算(临时[三选二[k + 2]], 临时[3], m, 输出[三选二[k + 2]],
输出[3]);
if (结果.等于(24)) {
System.out.print(表达式.substring(1,
表达式.length() - 1) + "\t");
成功 = true;
}
}
}
}
}
}
return 成功;
}
private static boolean 重复(有理数 数一, 有理数 数二, 有理数 数三, 有理数 数四) {
return (数一.equals(数三) && 数二.equals(数四))
|| (数一.equals(数四) && 数二.equals(数三));
}
private static boolean 继续(有理数 数一, 有理数 数二, int 运算符) {
switch (运算符) {
case 1:
return 数一.equals(数二);
case 2:
return 数一.等于(2) && 数二.等于(2);
case 3:
return 数二.等于(1);
case 4:
return 数一.等于(1) || 数一.equals(数二);
default:
return false;
}
}
private static 有理数 计算(有理数 分数一, 有理数 分数二, int 运算符, String 式一, String 式二) {
表达式 = new StringBuilder("(");
switch (运算符) {
case 0:// 分数一+分数二
表达式.append(式一).append("+").append(式二).append(")");
return 分数一.加(分数二);
case 1:// |分数一-分数二|
有理数 结果 = 分数一.减(分数二);
if (结果.小于零()) {
结果.负();
表达式.append(式二).append("-").append(式一).append(")");
} else
表达式.append(式一).append("-").append(式二).append(")");
return 结果;
case 2:// 分数一*分数二
表达式.append(式一).append("*").append(式二).append(")");
return 分数一.乘(分数二);
case 3:// 分数一/分数二
表达式.append(式一).append("/").append(式二).append(")");
return 分数一.除(分数二);
default:// 分数二/分数一
表达式.append(式二).append("/").append(式一).append(")");
return 分数二.除(分数一);
}
}
/**
* 主函数 测试用
* 打印出所有的可能组合的解及有解组合的总数
* 输入命令java -cp 24点游戏.jar com.onezero.算24
* @param args
*/
public static void main(String[] args) {
int 有解 = 0;
for (int i = 1; i < 14; i++)
for (int j = i; j < 14; j++)
for (int k = j; k < 14; k++)
for (int l = k; l < 14; l++)
if (计算二十四(new int[] { i, j, k, l })) {
System.out.println();
有解++;
}
System.out.println(有解);
}
}
class 有理数 {
private int 分子;
private int 分母 = 1;
有理数(int 分子) {
this.分子 = 分子;
}
有理数(int 分子, int 分母) {
if (分母 <= 0)
throw new ArithmeticException("分母不可小于等于零！");
int 公约数 = 最大公约数(分子 < 0 ? -分子 : 分子, 分母);
this.分子 = 分子 / 公约数;
this.分母 = 分母 / 公约数;
}
public boolean 等于(int 整数) {
return 整数 == this.分子 && 1 == this.分母;
}
private int 最大公约数(int 数一, int 数二) {
if (数一 == 数二) {
if (数一 == 0)
throw new ArithmeticException("求最大公约数不可同时为零！");
return 数一;
}
if (数一 == 0)
return 数二;
if (数二 == 0)
return 数一;
else if (数一 > 数二)
return 最大公约数(数二, 数一 % 数二);
else
return 最大公约数(数一, 数二 % 数一);
}
public 有理数 加(有理数 分数二) {
return new 有理数(this.分子 * 分数二.分母 + this.分母 * 分数二.分子, this.分母 * 分数二.分母);
}
public 有理数 减(有理数 分数二) {
return new 有理数(this.分子 * 分数二.分母 - this.分母 * 分数二.分子, this.分母 * 分数二.分母);
}
public 有理数 乘(有理数 分数二) {
return new 有理数(this.分子 * 分数二.分子, this.分母 * 分数二.分母);
}
public 有理数 除(有理数 分数二) {
if (分数二.分子 == 0)
throw new ArithmeticException("不可除零！");
return new 有理数(this.分子 * 分数二.分母, this.分母 * 分数二.分子);
}
public boolean 小于零() {
return this.分子 < 0;
}
public void 负() {
this.分子 = -this.分子;
}
public String toString() {
if (this.分母 == 1)
return Integer.toString(this.分子);
return this.分子 + "/" + this.分母;
}
public boolean equals(Object 数) {
if (!(数 instanceof 有理数))
return false;
有理数 数二 = (有理数) 数;
return this.分子 == 数二.分子 && this.分母 == 数二.分母;
}
}
|
| 返回顶楼 | |
|
发表时间：2009-01-21
cloverprince 写道 我的思路：
穷举所有数字的组合，穷举所有运算的组合，穷举运算符与数字的组合方式，求出表达式的值，过滤出值为24的表达式。 不同运算符有优先级问题，但是我可以避免这个问题。方法就是用“逆波兰式”。 给定4个数字和3个运算符，可以试图找到所有合法的逆波兰式。逆波兰式合法的定义就是不会使得遇到操作符时，堆栈里却没有足够的操作数。只要在生成逆波兰式的时候小心一点，记得判断就可以了。 我的实现：
module Main where
import List
import Ratio
main = putStr $ unlines $ map show $ work
work = filter (\x -> eval x == 24) $
concat [applyAll nums ops | nums <- numPerms, ops<-opPerms]
numRange = [1..9]
numPerms = [[a,b,c,d] | a<-numRange, b<-numRange, c<-numRange, d<-numRange]
opList = ['+','-','*','/']
opPerms = [[x,y,z] | x<-opList, y<-opList, z<-opList]
opMap '+' = (+)
opMap '-' = (-)
opMap '*' = (*)
opMap '/' = (/)
type NumType = Double
data Elem = Num NumType | Op Char deriving (Show)
-- Given 4 numbers and 3 operators, generate all valid RPNs
applyAll :: [NumType] -> [Char] -> [[Elem]]
applyAll nums ops = applyAll' nums ops [] 0
applyAll' :: [NumType] -> [Char] -> [Elem] -> Int -> [[Elem]]
applyAll' [] [] sofar 1 = [reverse sofar]
applyAll' [] (op:ops) sofar sz = applyAll' [] ops ((Op op):sofar) (sz-1)
applyAll' (n:ns) (op:ops) sofar sz | sz>=2 =
applyAll' (n:ns) ops ((Op op):sofar) (sz-1) ++
applyAll' ns (op:ops) ((Num n):sofar) (sz+1)
applyAll' (n:ns) ops sofar sz | otherwise =
applyAll' ns ops ((Num n):sofar) (sz+1)
applyAll' _ _ _ _ = []
-- Evaluate RPN
eval :: [Elem] -> NumType
eval es = head (foldl step [] es) where
step stack (Num n) = (n:stack)
step (n1:n2:ns) (Op op) = ((opMap op) n2 n1):ns
好,我正好和这位同志到想法一致,这样可以不用考虑运算符优先级问题了,我到算法就是这么搞的,有空验证一下完整性! |
| 返回顶楼 | |
|
发表时间：2009-02-17
早些时候写过一个，可以去掉重复的如 1118 1181之类只能算一个
http://shenkun-918.iteye.com/admin/blogs/254770 # public static void main(String[] args){ # # int a=0,b=0,c=0,d=0; # //将a,b,c,d取由1到13的数字 # for(int i=1;i<=13;i++){ # a = i; # for(int j=1;j<=13;j++){ # b = j; # for(int k=1;k<=13;k++){ # c = k; # for(int l=1;l<=13;l++){ # d = l; # outs(a,b,c,d); # } # } # } # } # } # # //将四个数带入计算,判断是否可以组成24,可以则输出 # @SuppressWarnings("unused") # public static void outs(int a,int b,int c,int d){ # int count = 0; # //两个数计算的结果是ab，三个数计算的结果是abc，最终结果是abcd # double ab=0, abc=0, abcd=0; # boolean todo = false; # String[] s = new String[]{"+","-","*","/"}; # int[] content; # for(int i=0;i<s.length;i++){ # ab = account(a,b,s[i]); # for(int j=0;j<s.length;j++){ # abc = account(ab,c,s[j]); # for(int k=0;k<s.length;k++){ # abcd = account(abc,d,s[k]); # if(abcd == 24){ # content = new int[]{a,b,c,d}; # //排序，这样利于比较 # Arrays.sort(content); # count++; # Iterator iter = lists.iterator(); # while(iter.hasNext()){ # int[] list = (int[])iter.next(); # if(list[0]==content[0]&list[1]==content[1]&list[2]==content[2]&list[3]==content[3]){ # todo = true; # } # } # if(!todo){ # lists.add(content); # System.out.println(lists.size()); # System.out.println(a + " "+ b +" " + c + " " + d + "经过四则混合运算可以组成24"); # } # } # } # } # } # } # # //具体的计算 # public static double account(double i, double j, String d){ # double k = 0; # if(d.compareTo("+")==0){ # k = i + j; # }else if(d.compareTo("-")==0){ # k = Math.abs(i - j); # }else if(d.compareTo("*")==0){ # k = i * j; # }else if(d.compareTo("/")==0){ # k = i / j; # } # return k; # } # } |
| 返回顶楼 | |
|
发表时间：2009-02-18
这算什么 啊 ！
有人用汇编吗？ |
| 返回顶楼 | |
