论坛 › Perl › 初学perl，写了一个算24点的小程序，请前辈高手指点一下

smilefoxzhu 发表于 2010-07-12 03:41

初学perl，写了一个算24点的小程序，请前辈高手指点一下

练习的作业，大家不要笑，总觉得写的还是C的那个套路，所以想请前辈高手指点一下

我算法大概是这样的，perm是排列生成器，输入一个数组，给出全排列。
rec_cala是取出前两个元素，加上运算符生产一个新的表达式作为第一个元素放入数组中，这样递归调用，当数组只有一个元素时对表达式求值，如果表达式的值是24，则打印。my @test_arr=(10,4,7,6);
my @oprator_arr=('+', '-','*','/');
rec_cala(\@test_arr);

sub rec_cala
{
    my ($arr_ref) = @_;
    my @input_arr = ();
    push @input_arr,@$arr_ref;

    if (scalar(@input_arr) <= 1)
    {
      $result = eval $input_arr;
      if ($result > 23.9 && $result < 24.1)
      {
            print $input_arr;
            print "= 24\n";
      }
    }
    else
    {
      my @perm_arr = perm(\@input_arr);

      foreach(@perm_arr)
      {
            my @next_arr = @$_;
            my $op1 = pop @next_arr;
            my $op2 = pop @next_arr;      
                        
            foreach(@oprator_arr)
            {
                @op_expr_arr = @next_arr;
                push @op_expr_arr, "($op1 $_ $op2)";
                rec_cala(\@op_expr_arr);   
            }   
            
      }
    }
}

sub perm
{
    my ($arr_ref)=@_;
    my @arr=@$arr_ref;
    my @result = [];
   
    while(scalar(@arr))
    {
      my $curr_element = pop @arr;
      my @next_step = ();
      foreach $curr_array (@result)
      {
            $curr_len = scalar(@$curr_array);
            for($i=0; $i<= $curr_len;$i++)
            {
                my @tmp = @$curr_array;            
                my @tail_arr = splice(@tmp,$i,$curr_len -$i);
                push @tmp,$curr_element;
                push @tmp,@tail_arr;
                push @next_step,[@tmp];
            }
      }
      @result =@next_step;
    }
    return @result;
}

leigh111 发表于 2010-07-12 12:16

第26行， my @next_arr = @$_;
是什么意思。

smilefoxzhu 发表于 2010-07-12 12:46

本帖最后由 smilefoxzhu 于 2010-07-12 12:59 编辑

第26行， my @next_arr = @$_;
是什么意思。
leigh111 发表于 2010-07-12 12:16 http://bbs.chinaunix.net/images/common/back.gif

呃，这句就是把@perm_arr里的一个个数组取出来啊，因为@perm_arr里放的是数组的引用，所以写@next_arr = @$_。
其实直接操作@$_也可以吧，不过要传到第二个foreach里面去，因为让调试方便，省得两个$_掺和所以这么写来着。

smilefoxzhu 发表于 2010-07-16 14:06

sub perm
{
    my ($arr_ref)=@_;
    my @arr=@$arr_ref;
    my @result = [];
   
    while(scalar(@arr))
    {
      my $curr_element = pop @arr;
      my @next_step = ();
      foreach $curr_array (@result)
      {
            $curr_len = scalar(@$curr_array);
            for($i=0; $i<= $curr_len;$i++)
            {
                push @next_step,[ ( @$curr_array, $curr_element,@$curr_array[$i+1..$curr_len ])];
            }
      }
      @result =@next_step;
    }
    return @result;
}发现其实排列部分可以稍微改一下，也比较清楚一些，其它的慢慢改吧

iamlimeng 发表于 2010-07-16 16:23

生成的结果重复率非常高，不知道能不能过滤。

sy5tem 发表于 2010-07-16 22:31

非常感谢楼主，能够把自己的学习所得写出来

给个小小建议，如果能够加上注释，对于初学者的阅读更方便些

smilefoxzhu 发表于 2010-07-20 16:03

回复 6# sy5tem my @test_arr=(10,5,2,2);
my @oprator_arr=('+', '-','*','/');

perm(\@test_arr);
rec_cala(\@test_arr);

sub rec_cala
{
    my ($arr_ref) = @_;
    my @input_arr = ();
    push @input_arr,@$arr_ref;

    if (scalar(@input_arr) <= 1)
    {
           #如果数组只有一个元素则计算表达式的值，等于24则显示
      $result = eval $input_arr;
      if ($result > 23.9 && $result < 24.1)
      {
            print $input_arr;
            print "= 24\n";
      }
    }
    else
    {
           #生成全排列
      my @perm_arr = perm(\@input_arr);
       
      foreach(@perm_arr)
      {
            my @next_arr = @$_;
            my $op1 = pop @next_arr;
            my $op2 = pop @next_arr;      
            #取出2个元素，与符号生成一个表达式，然后递归   
            foreach(@oprator_arr)
            {
                @op_expr_arr = @next_arr;
                push @op_expr_arr, "($op1 $_ $op2)";
                rec_cala(\@op_expr_arr);   
            }   
            
      }
    }
}

#排列生成器
#方法是: "先选一个数 1, 然后第二个数 2 可以放在 1 的前面或是后面. 而每一个放法都会产生一个 2 位数, 对於每一个这样的两位数, 第三个数 3, 都可以放在它的前面, 中间, 或是最后; 如此产生一个 3 位数; 而每一个 3 位数, 第 4 位数都可以插入到这 3 个数的任何一个空位中, 如此类推.
sub perm
{
    my ($arr_ref)=@_;
    my @arr=@$arr_ref; #变成数组，引用会直接修改传入参数，而且用起来很麻烦
    my @result = [];    #初始化一个空的数组的引用
   
    #每循环一次数组都会缩短，到0退出
    while(scalar(@arr))
    {
      my $curr_element = pop @arr;   #拿出一个元素，前后无所谓咯，这个是用来插入的元素
      my @next_step = ();        #每次用一个空的数组放结果
      foreach $curr_array (@result) #遍历要插入的数组，第一次这里有一个空的数组的引用，所以会进去
      {
            $curr_len = scalar(@$curr_array);
            for($i=0; $i<= $curr_len;$i++)
            {
               # 插入到数组的各个位置，每插入一次就加到@next_step去
                push @next_step,[ ( @$curr_array, $curr_element,@$curr_array[$i+1..$curr_len ])];
            }
      }
      #插入完成后，把结果作为下一步要插入的数组
      @result =@next_step;
    }
    return @result;
}
加了些注释，应该容易看一点了吧
呵呵

sy5tem 发表于 2010-07-21 11:16

感谢楼主啊，让我们初学者更容易理解啦

bakerwm 发表于 2013-06-24 18:55

请教下lz，自己有试过程序吗？
（a+b）*（c+d）=24这样的算式恐怕不适用？！

rubyish 发表于 2013-06-25 14:34

非常感谢 LZ :#!/usr/bin/perl
my @o = qw[ + - * / ];
my @O = map { $a = $_; map { $b = $_; map [ $a, $b, $_ ], @o } @o } @o;
my @F = (
    '( ( %d %s %d ) %s %d ) %s %d',
    '( %d %s ( %d %s %d ) ) %s %d',
    '( %d %s %d ) %s ( %d %s %d )',
    '%d %s ( ( %d %s %d ) %s %d )',
    '%d %s ( %d %s ( %d %s %d ) )' );
sub P {
    @_ ? map { my $i = $_; map [ $_[$i], @$_ ],
      &P( @_[ 0 .. $i - 1, $i + 1 .. $#_ ] ) } 0 .. $#_ : [] }


while (1) { print " input: ";

my $i = <>;
$i =~ /^/ and last;
my @i = map /(\d+)/g, $i;
@i == 4 or next;
my ( @N, $m, %m ) = P @i;

for my $f (@F) {
for my $n (@N) {
    for my $o (@O) {
       my $s = sprintf $f, map( { $n->[$_], $o->[$_] } 0, 1, 2 ), $n->;
       my $R = eval $s or next;
       print ++$m, "\t$s$/" if $R == 24 and !$m{$s}++ } } }
      
print "NOOO\n" unless %m }

查看完整版本: 初学perl，写了一个算24点的小程序，请前辈高手指点一下