难题来了！四色球算24

bikkuri

有红绿蓝黄四种颜色的球，分别代表1，2，4，8。

1. R=1;G=2;B=4;Y=8

复制代码

现在要求从装满这四种颜色的球的箱子里，随机抽取7次，然后用7个球代表的数字运用加减乘除和括号算出24。
要求的输出有：
抽出的7个球的颜色，例如：BYYGRBG
算出24的方法，例如：Y*(B+G+G)-Y*(B+R)=8*(4+2+2)-8*(4+1)=24

请各位高手赐教！

cclxpp123

用c++解决应该好一些，加上括号，排列组合的情况很复杂，不知道有无什么优化的算法

rubyish

g [ 1, 1, 1, 1, 1, 1, 2 ];    # 1.6x s
h [ 1, 1, 1, 1, 1, 1, 2 ];    # 11.x s


ru ? wan 24 dian ?

try:

1. my $THAT = 24;
   
2. my @BOX  = ( 1 .. 13 );
   
3. my $PICK = 4;

复制代码

rubyish

v3:

1. try [ 3, 3, 8, 8 ];             # 0.025 s
   
2. try [ 2, 1, 1, 1, 1, 1, 1 ];    # 0.19 s
   
3. try [ 1, 1, 1, 1, 1, 1, 1 ];    # 0.075 s
   

复制代码

1. #!/usr/bin/perl
   
2. 
   
3. my $SCOR = 24;
   
4. my @BALL = ( 1, 2, 4, 8 );
   
5. my $PICK = 7;
   
6. my %UNIQ;
   
7. 
   
8. sub _ { $a->[0] <=> $b->[0] }
   
9. 
   
10. sub fun {
    
11.     my ( $A, $B ) = @_;
    
12. 
    
13.     if ( !@$A and @$B == 1 ) {
    
14.         return if $B->[0][0] ne $SCOR;
    
15.         my $answer = substr $B->[0][1], 2, -2;
    
16.         print "$answer = $SCOR\n\n" and die;
    
17.     }
    
18. 
    
19.     if ( @$B == 2 ) {
    
20.         return if $UNIQ{ join $", map $_->[0], @$A, @$B }++;
    
21.         my ( $i, $x, $j, $y ) = map @$_, @$B;
    
22. 
    
23.         fun( [ sort { _ }[ $i + $j, "( $x + $y )" ], @$A ], [] );
    
24.         fun( [ sort { _ }[ $i - $j, "( $x - $y )" ], @$A ], [] );
    
25.         fun( [ sort { _ }[ $i * $j, "( $x * $y )" ], @$A ], [] );
    
26.         fun( [ sort { _ }[ $i / $j, "( $x / $y )" ], @$A ], [] ) if $j;
    
27.     }
    
28. 
    
29.     for my $i ( 0 .. $#$A ) {
    
30.         next if $i and $A->[$i][0] == $A->[ $i - 1 ][0];
    
31.         fun( [ @$A[ 0 .. $i - 1, $i + 1 .. $#$A ] ], [ @$B, $A->[$i] ] );
    
32.     }
    
33. }
    
34. 
    
35. sub try {
    
36.     my ( $roll, $fail ) = ( @_, 0, undef %UNIQ, undef $@ );
    
37.     print "\n[ ", join( ', ', @$roll ), " ]\n\n";
    
38.     print "NO ANSWER\n\n" and return if $fail;
    
39.     $roll = [ map [ $_, $_ ], sort { $a <=> $b } @$roll ];
    
40.     eval { fun $roll, [] };
    
41.     print "NO ANSWER\n\n" if !$@;
    
42. }
    
43. 
    
44. sub run {
    
45.     print "\n\n[ q: EXIT, enter: roll ]\n\n";
    
46.     my ( $Ok, %Polar ) = \$@;
    
47. 
    
48.     while (<>) {
    
49.         print "\n[ EXIT ]\n" and return if /q/;
    
50.         my $the = [ @BALL[ map { rand @BALL } 1 .. $PICK ] ];
    
51.         my $Express = join $", sort { $a <=> $b } @$the;
    
52.         try $the, $Polar{$Express};
    
53.         $Polar{$Express} = 2 if not $Ok;
    
54.     }
    
55. }
    
56. 
    
57. run;
    

复制代码

v3.1

1. #!/usr/bin/perl
   
2. use Tk;
   
3. my @BALL = ( 1, 2, 4, 8 );
   
4. my $PICK = 7;
   
5. my $SCOR = 24;
   
6. my %UNIQ;
   
7. my $ANS;
   
8. my @color = qw/coral limegreen skyblue gold
   
9.   hotpink purple snow4 bisque3
   
10.   tan orchid gray khaki plum/;
    
11.   
    
12. sub _ { $a->[0] <=> $b->[0] }
    
13. 
    
14. sub fun {
    
15.     my ( $A, $B ) = @_;
    
16.     if ( !@$A and @$B == 1 ) {
    
17.         return if $B->[0][0] ne $SCOR;
    
18.         my $answer = substr $B->[0][1], 2, -2;
    
19.         $ANS = "$answer  =  $SCOR\n";
    
20.         die;
    
21.     }
    
22.     if ( @$B == 2 ) {
    
23.         return if $UNIQ{ join $", map $_->[0], @$A, @$B }++;
    
24.         my ( $i, $x, $j, $y ) = map @$_, @$B;
    
25. 
    
26.         fun( [ sort { _ }[ $i + $j, "( $x + $y )" ], @$A ], [] );
    
27.         fun( [ sort { _ }[ $i - $j, "( $x - $y )" ], @$A ], [] );
    
28.         fun( [ sort { _ }[ $i * $j, "( $x * $y )" ], @$A ], [] );
    
29.         fun( [ sort { _ }[ $i / $j, "( $x / $y )" ], @$A ], [] ) if $j;
    
30.     }
    
31. 
    
32.     for my $i ( 0 .. $#$A ) {
    
33.         next if $i and $A->[$i][0] == $A->[ $i - 1 ][0];
    
34.         fun( [ @$A[ 0 .. $i - 1, $i + 1 .. $#$A ] ], [ @$B, $A->[$i] ] );
    
35.     }
    
36. }
    
37. 
    
38. sub draw {
    
39.     my ( $canvas, $b ) = @_;
    
40.     for my $i ( 1 .. $PICK ) {
    
41.         my $x  = 50 * $i - 25;
    
42.         my $bi = $b->[ $i - 1 ];
    
43.         my $r  = $BALL[$bi];
    
44.         $canvas->createOval(
    
45.             $x, 25, $x + 50, 75,
    
46.             -fill  => $color[$bi],
    
47.             -width => 6
    
48.         );
    
49.         $canvas->createText(
    
50.             $x + 25, 48,
    
51.             -text   => $r,
    
52.             -anchor => 'center',
    
53.             -font   => 'Helvetica -36 bold'
    
54.         );
    
55.     }
    
56. }
    
57. 
    
58. sub try {
    
59.     my ( $canvas, $e ) = @_;
    
60.     undef %UNIQ;
    
61.     $ANS = "NO ANSWER\n";
    
62.     my $roll = [ map { rand @BALL } 1 .. $PICK ];
    
63.     draw $canvas, $roll;
    
64.     my @roll = map [ $_, $_ ], sort { $a <=> $b } @BALL[@$roll];
    
65.     eval { fun \@roll, [] };
    
66.     $e->configure( -text => $ANS );
    
67. }
    
68. 
    
69. sub show {
    
70.     my $win = MainWindow->new;
    
71.     $win->title('24');
    
72.     $win->Label( -text => 'press any key to continue' )->pack;
    
73. 
    
74.     my $canvas =
    
75.       $win->Canvas( -width => ( $PICK + 1 ) * 50, -height => 100, )->pack;
    
76. 
    
77.     my $lab = $win->Label(
    
78.         -width => $PICK * 6,
    
79.         -font  => 'Helvetica -16 bold',
    
80.         -text  => 'input solution',
    
81.     )->pack();
    
82. 
    
83.     my $ok = $win->Button(
    
84.         -text    => '     next     ',
    
85.         -default => 'active',
    
86.         -command => sub { try $canvas, $lab }
    
87.     )->pack( -side => 'right', -padx => 55 );
    
88. 
    
89.     $win->Button( -text => '     quit     ', -command => sub { exit } )
    
90.       ->pack( -side => 'right', -padx => 55 );
    
91.     $win->bind( '<Any-KeyPress>' => sub { try $canvas, $lab } );
    
92.     try $canvas, $lab;
    
93.     MainLoop;
    
94. }
    
95. 
    
96. show;
    
97. 
    

复制代码

mswsg

正常情况下，第一次以及最后一次没有（+ - * /）,但是可以有括号？

mswsg

我们来算算有多少种组合：四个球，取7次，那么共有4的7次方（4^7）中组合，
'+ - ) x / ( ' 共六种符号，将这两种符号放在7个数字中间以及旁侧，共有6^8中组合，
_1_2_3_4_5_6_7_,
_表示可以放运算符的地方，那么综合两者共有4^7*6^8中组合（即约275亿）
很明显，很多算术表达式是不合法的。
我的想法就是构造出所有的可能，然后选择出计算结果为24的组合，
可惜运行起来很慢，上面的用perl写的东西，也没有给出到底有多少种组合为24。
本人perl白痴，哪位大侠能否翻译成python贴上来，好好学习下。
另外，谁有好的思路也可交流下。
我的代码如下，直接运行即可 python test.py
运行半小时的只出来几条结果：
(1-1+8+8*4/1/2)
(1*1*8+8+4*1*2)
(1/1*8+8+4/1*2)
(1-1-8+8*4-1/2)
(1+1*8+8+4+1+2)
(1-1+8+8+4/1*2)
(1+1+8+8+4/1+2)
(1*1*8+8*4*1/2)
(1+1-8+8*4/1-2)
(1*1*8+8+4/1*2)
(1-1*8+8*4+1-2)
(1+1-8+8*4*1-2)

1. #!/usr/bin/env python
   
2. # -*- coding: utf-8 -*-
   
3. __author__ = 'shengwei ma'
   
4. import random
   
5. 
   
6. R = 1
   
7. G = 2
   
8. B = 4
   
9. Y = 8
   
10. seq = [R, G, B, Y]
    
11. cal = ['+', '-', '*', '/', '(', ')']
    
12. choose =[]
    
13. 
    
14. all_choose =[]
    
15. while len(choose) < 16384:
    
16.     ele = [random.choice(seq), random.choice(seq), random.choice(seq), random.choice(seq), \
    
17.            random.choice(seq), random.choice(seq), random.choice(seq)]
    
18.     if ele not in choose:
    
19.         choose.append(ele)
    
20. for i in range(len(choose)):
    
21.     while len(all_choose) < 1679616:
    
22.         total = random.choice(cal) + str(choose[i][0]) + random.choice(cal) + str(choose[i][1]) + random.choice(cal) + \
    
23.     str(choose[i][2]) + random.choice(cal) + str(choose[i][3]) + random.choice(cal) + str(choose[i][4]) + \
    
24.             random.choice(cal) + str(choose[i][5]) + random.choice(cal) + str(choose[i][6]) + random.choice(cal)
    
25.         if total not in all_choose:
    
26.             all_choose.append(total)
    
27.             try:
    
28.                 value = eval(total)
    
29.             except:
    
30.                 pass
    
31.             else:
    
32.                 if value == 24:
    
33.                     print total

复制代码