我用C寫的一個(gè)算24點(diǎn)代碼。

emacsnw

主要是使用逆波蘭表達(dá)式的求值。歡迎測(cè)試和指正！

1. 
   
2. /* cal24.c
   
3. * given N integer numbers
   
4. * find one expression which produces value T using all
   
5. * the N numbers and {+,-,*,/} operators
   
6. */
   
7. #include <stdio.h>
   
8. #include <stdlib.h>
   
9. #include <string.h>
   
10. 
    
11. #define N 4  /* number of cards    */
    
12. #define T 24 /* target solution    */
    
13. #define M 13 /* maximum card value */
    
14. #define STACK_SIZE (N+N-1)
    
15. #define EPS 1e-6
    
16. #define ADD M+1
    
17. #define SUB M+2
    
18. #define MUL M+3
    
19. #define DIV M+4
    
20. 
    
21. /* evaluate an expression in reverse Polish notation (RPN) */
    
22. double eval(int expr[])
    
23. {
    
24.     double oprnds[N],oprnd1,oprnd2;
    
25.     int top = -1,i,op;
    
26.     for(i = 0;i<STACK_SIZE;++i){
    
27.         op = expr[i];
    
28.         if(op<=M){
    
29.             oprnds[++top] = (double)op;
    
30.             continue;
    
31.         }
    
32.         oprnd1 = oprnds[top--];
    
33.         oprnd2 = oprnds[top--];
    
34.         switch(op){
    
35.         case ADD: oprnd1 += oprnd2; break;
    
36.         case SUB: oprnd1 -= oprnd2; break;
    
37.         case MUL: oprnd1 *= oprnd2; break;
    
38.         case DIV:
    
39.             if(oprnd2<EPS && oprnd2>-EPS) return 0.0;
    
40.             oprnd1 /= oprnd2;
    
41.         }
    
42.         oprnds[++top] = oprnd1;
    
43.     }
    
44.     return oprnds[top];
    
45. }
    
46. 
    
47. int succ(int expr[])
    
48. {
    
49.     double x = eval(expr);
    
50.     if(x>T-EPS && x<T+EPS) return 1;
    
51.     return 0;
    
52. }
    
53. 
    
54. /* just to make the expression more readable by human */
    
55. void printsolution(int expr[])
    
56. {
    
57.     double oprnds[N],oprnd1,oprnd2,result;
    
58.     int top = -1,i,op;
    
59.     char c;
    
60.     for(i = 0;i<STACK_SIZE;++i){
    
61.         op = expr[i];
    
62.         if(op<=M){
    
63.             oprnds[++top] = (double)op;
    
64.             continue;
    
65.         }
    
66.         oprnd1 = oprnds[top--];
    
67.         oprnd2 = oprnds[top--];
    
68.         switch(op){
    
69.         case ADD:
    
70.             c = '+';
    
71.             result = oprnd1 + oprnd2;
    
72.             break;
    
73.         case SUB:
    
74.             c = '-';
    
75.             result = oprnd1 - oprnd2;
    
76.             break;
    
77.         case MUL:
    
78.             c = '*';
    
79.             result = oprnd1 * oprnd2;
    
80.             break;
    
81.         case DIV:
    
82.             c = '/';
    
83.             result = oprnd1 / oprnd2;
    
84.         }
    
85.         printf("%.2f %c %.2f => %.2f\n",oprnd1,c,oprnd2,result);
    
86.         oprnds[++top] = result;
    
87.     }
    
88. }
    
89. 
    
90. /* update ret[] with next possible permutation of N cards */
    
91. int permute(int ret[])
    
92. {
    
93.     int orig[N],i,j = 1;
    
94.     for(i = 0;i<N-1;++i)
    
95.         if(ret[i]<ret[i+1]){
    
96.             j = 0;
    
97.             break;
    
98.         }
    
99.     if(j) return 0;
    
100.     for(i = 0;i<N;++i) orig[i] = ret[i];
     
101.     for(i = N-2;i>=0;--i)
     
102.         if(orig[i]<orig[i+1]) break;
     
103.     for(j = N-1;j>i;--j)
     
104.         if(orig[j]>orig[i]) break;
     
105.     ret[i] = orig[j];
     
106.     orig[j] = orig[i];
     
107.     for(j = i+1;j<N;++j)
     
108.         ret[j] = orig[N-j+i];
     
109.     return 1;
     
110. }
     
111. 
     
112. /* update ops[] with next possible operators */
     
113. int operators(int ops[])
     
114. {
     
115.     int i,j;
     
116.     for(i = N-1;i>=0;--i){
     
117.         if(ops[i]<DIV){
     
118.             ++ops[i];
     
119.             for(j = i+1;j<N-1;++j) ops[j] = ADD;
     
120.             return 1;
     
121.         }
     
122.     }
     
123.     return 0;
     
124. }
     
125. 
     
126. /* update expr[] with next possible expression in RPN */
     
127. int expressions(int expr[])
     
128. {
     
129.     if(expr[3]>M && expr[4]>M) return 0;
     
130.     if(expr[2]>M && expr[4]>M) expr[2]^=expr[3]^=expr[2]^=expr[3];
     
131.     else if(expr[2]>M) expr[4]^=expr[5]^=expr[4]^=expr[5];
     
132.     else if(expr[3]>M) expr[2]^=expr[3]^=expr[2]^=expr[3];
     
133.     else expr[3]^=expr[4]^=expr[3]^=expr[4];
     
134.     return 1;
     
135. }
     
136. 
     
137. int main(int argc,char *argv[])
     
138. {
     
139.     int opd[N],pmt[N],ops[N-1],expr[STACK_SIZE],i,succeed = 1;
     
140.     if(argc<N+1) exit(printf("Not enough arguments!\n"));
     
141.     for(i = 0;i<N;++i) opd[i] = atoi(argv[i+1]);
     
142.     for(i = 0;i<N;++i) pmt[i] = i;
     
143.     for(i = 0;i<N-1;++i) ops[i] = ADD;
     
144.     while(1){
     
145.         for(i = 0;i<N;++i) expr[i] = opd[pmt[i]];
     
146.         for(i = 0;i<N-1;++i) expr[N+i] = ops[i];
     
147.         if(succ(expr)) break;
     
148.         while(expressions(expr))
     
149.             if(succ(expr)) break;
     
150.         if(succ(expr)) break;
     
151.         if(!operators(ops)){
     
152.             if(!permute(pmt)){
     
153.                 succeed = 0;
     
154.                 break;
     
155.             }
     
156.             for(i = 0;i<N-1;++i) ops[i] = ADD;
     
157.         }
     
158.     }
     
159.     if(!succeed) exit(printf("Find no solutions!\n"));
     
160.     printsolution(expr);
     
161. }
     
162. 
     

復(fù)制代碼

emacsnw

幾個(gè)比較“經(jīng)典”的數(shù)字組合測(cè)試：

1. 
   
2. [bohnanza:misc]$ ./cal24 3 3 8 8
   
3. 8.00 / 3.00 => 2.67
   
4. 3.00 - 2.67 => 0.33
   
5. 8.00 / 0.33 => 24.00
   
6. [bohnanza:misc]$ ./cal24 5 5 1 5
   
7. 1.00 / 5.00 => 0.20
   
8. 5.00 - 0.20 => 4.80
   
9. 4.80 * 5.00 => 24.00
   
10. [bohnanza:misc]$ ./cal24 4 4 10 10
    
11. 10.00 * 10.00 => 100.00
    
12. 100.00 - 4.00 => 96.00
    
13. 96.00 / 4.00 => 24.00
    
14. [bohnanza:misc]$ ./cal24 3 7 3 7
    
15. 3.00 / 7.00 => 0.43
    
16. 0.43 + 3.00 => 3.43
    
17. 7.00 * 3.43 => 24.00
    
18. [bohnanza:misc]$ ./cal24 1 2 3 4
    
19. 2.00 + 1.00 => 3.00
    
20. 3.00 + 3.00 => 6.00
    
21. 4.00 * 6.00 => 24.00
    
22. [bohnanza:misc]$ ./cal24 7 7 7 7
    
23. Find no solutions!
    
24. 
    

復(fù)制代碼

原帖由 emacsnw 于 2006-3-23 19:16 發(fā)表
主要是使用逆波蘭表達(dá)式的求值。歡迎測(cè)試和指正！

1. 
   
2. /* cal24.c
   
3. * given N integer numbers
   
4. * find one expression which produces value T using all
   
5. * the N numbers and {+,-,*,/} operators
   
6. ...
   

復(fù)制代碼

converse

1. [bohnanza:misc]$ ./cal24 3 3 8 8
   
2. 8.00 / 3.00 => 2.67
   
3. 3.00 - 2.67 => 0.33
   
4. 8.00 / 0.33 => 24.00

復(fù)制代碼

這個(gè)涉及到精度的這樣子表示好像不太妥當(dāng).
我覺得最后表達(dá)出來(lái)的時(shí)候?qū)懗梢贿B串的數(shù)字和運(yùn)算符組合可能好點(diǎn),比如上面的那個(gè):
8/ (3 - 8 /3)...

回頭我也研究一下24點(diǎn)的算法

emacsnw

原帖由 converse 于 2006-3-23 19:32 發(fā)表

1. [bohnanza:misc]$ ./cal24 3 3 8 8
   
2. 8.00 / 3.00 => 2.67
   
3. 3.00 - 2.67 => 0.33
   
4. 8.00 / 0.33 => 24.00

復(fù)制代碼

這個(gè)涉及到精度的這樣子表示好像不太妥當(dāng).
我覺得最后表達(dá)出來(lái)的時(shí)候?qū)懗梢贿B串 ...

計(jì)算的時(shí)候是使用double精度的，這個(gè)只是打印的時(shí)候不想在數(shù)字后面打太多位的小數(shù)。
打印表達(dá)式確實(shí)你說(shuō)的那樣更好一些。但是我自己在玩這個(gè)游戲的時(shí)候卻是這樣的一個(gè)
過程，而且逆波蘭表達(dá)式轉(zhuǎn)換成這種打印形式方便一些，偷懶了。

yuxh

很久很久以前,也寫過一個(gè)很垃圾的
http://72891.cn/viewthr ... &highlight=yuxh

ArXoR

用分?jǐn)?shù)吧,反正全是有理數(shù)