[数值计算] [出题挑战]数字的四则运算组合

hongrk

因为等级不够不能在[出题挑战]区发。

要求：输入一串数字，输出在此串数字中 插入四则运算 允许括号 所能得到的 自然数结果（可后跟对应的1个算式），结果按从小到大排列。

例：输入333，输出：

0=(3-3)*3
2=(3+3)/3
3=3+3-3
4=3/3+3
6=3*3-3
9=3+3+3
11=33/3
12=3*3+3
18=(3+3)*3
27=3*3*3
30=33-3
36=33+3
99=33*3
333=333
复制代码

若觉得比较麻烦，可以自行简化要求。比如只输出结果不带算式、运算数都只1位之类的。
另外，如5155算出24的情况……其实也算符合要求的吧。

老刘1号

先占个楼，感觉lz的要求（前10行）用逆波兰表达式比较好搞

523066680

回复 2# 老刘1号

    枚举全部结果还好，要是对每个值枚举不重复的全部公式就比较麻烦。比如 (1+2)*3 和 3*(1+2)，3*(2+1) 是完全一样的性质
10897 如何不重复地枚举 24 点算式？（上）
10897 如何不重复地枚举 24 点算式？（中）
10897 如何不重复地枚举 24 点算式？（下）

我们直接跳到最后一章

三、总结

　　本文解决了减法和除法中由「去括号」和「反转减号」造成的重复，修改主要体现在 actions 函数中。为了排除由「反转减号」造成的重复，我们定义了算式的极性。极性在运算中的传递规律非常复杂，造成 actions 函数冗长而不优雅，我也很无奈。
　　用最终版程序可以算出，由 n 个变量经四则运算可以组成的算式个数为：
[attach]11922[/attach]

这个数列也被 The Online Encyclopedia of Integer Sequences 收录

也就是二三四五六都可以用现成的模板套，这样可以省去大量冗余的试算过程。（这还没考虑数字相同的情况，数字相同的话减法和除法就不必要调换了，看需求严格程度吧）

两个参与数

a + b
a - b
b - a
a * b
a / b
b / a
复制代码

三个参与数

c - (a + b)
a + b - c
c * (a + b)
c / (a + b)
(a + b) / c
c * (a - b)
c / (a - b)
(a - b) / c
c * (b - a)
c / (b - a)
(b - a) / c
c + a * b
c - a * b
a * b - c
c / (a * b)
a * b / c
c + a / b
c - a / b
a / b - c
c + b / a
c - b / a
b / a - c
b - (a + c)
a + c - b
b * (a + c)
b / (a + c)
(a + c) / b
b * (a - c)
b / (a - c)
(a - c) / b
b * (c - a)
b / (c - a)
(c - a) / b
b + a * c
b - a * c
a * c - b
b / (a * c)
a * c / b
b + a / c
b - a / c
a / c - b
b + c / a
b - c / a
c / a - b
a + b + c
a - (b + c)
b + c - a
a * (b + c)
a / (b + c)
(b + c) / a
a * (b - c)
a / (b - c)
(b - c) / a
a * (c - b)
a / (c - b)
(c - b) / a
a + b * c
a - b * c
b * c - a
a * b * c
a / (b * c)
b * c / a
a + b / c
a - b / c
b / c - a
a + c / b
a - c / b
c / b - a
复制代码

4个和5个


至于5 5 5 1, 3 3 8 8, 3 3 7 7 之类求24的精度问题。转分数（有理化）处理。

523066680

5551，取非负整数部分

0=(((5-5)*5)*1)
1=(((5+5)/5)-1)
2=(((5+5)/5)*1)
3=(((5+5)/5)+1)
4=(((5+5)-5)-1)
5=(((5+5)-5)*1)
6=(((5+5)-5)+1)
7=(((5/5)+5)+1)
10=(((5/5)+1)*5)
11=(1/(5/55))
12=((55/5)+1)
14=(((5+5)+5)-1)
15=(((5+5)+5)*1)
16=(((5+5)+5)+1)
19=(((5*5)-5)-1)
20=(((5*5)-5)*1)
21=(((5*5)-5)+1)
24=((5-(1/5))*5)
25=(((5+1)*5)-5)
26=(((1/5)+5)*5)
29=(((5*5)+5)-1)
30=(((5*5)+5)*1)
31=(((5*5)+5)+1)
35=(((5+1)*5)+5)
40=((5-1)*(5+5))
41=(51-(5+5))
45=(((5+5)-1)*5)
49=(((5+5)*5)-1)
50=(((5+5)*5)*1)
51=(((5+5)*5)+1)
52=((5/5)+51)
55=(((5+5)+1)*5)
59=((5+55)-1)
60=((5+1)*(5+5))
61=((5+5)+51)
76=((5*5)+51)
100=((5-1)*(5*5))
106=(55+51)
120=(((5*5)-1)*5)
124=(((5*5)*5)-1)
125=(((5*5)*5)*1)
126=(((5*5)*5)+1)
130=(((5*5)+1)*5)
150=((5+1)*(5*5))
220=((5-1)*55)
230=((51-5)*5)
250=((5*51)-5)
260=((5*51)+5)
270=((55-1)*5)
274=((5*55)-1)
275=((5*55)*1)
276=((5*55)+1)
280=((5+51)*5)
330=((5+1)*55)
510=((5+5)*51)
546=(551-5)
554=(555-1)
555=(555*1)
556=(5+551)
1275=((5*5)*51)
2755=(5*551)
2805=(55*51)
5551=5551
复制代码

523066680

use Math::BigRat;
STDOUT->autoflush(1);
our %hash;
our @op = qw/+ - * \//;
my $num = "5551";
my @nums= split("", $num);
my @arr = split("", join(" ", @nums));
my @comb;
spliter(\@arr, $#nums, 0, 0, \@comb);
grep { gen_exp( $_, $#$_, 0 ) } @comb;

for my $k (sort {$a <=> $b} keys %hash) {
    printf "%s\n", $hash{$k};
}

sub gen_exp
{
    our @op, our %hash;
    my ($nums, $limit,  $lv ) = @_;

    if ($lv >= $limit) {
        my $res;
        my $exp = $nums->[0];
        $exp=~s/\d+/Math::BigRat->new(\"$&\/1\")/g;
        $exp=~s/\*/ * /g;
        eval("\$res = $exp");
        return if $res == inf or $res == -inf or $res eq NaN;
        my $val = $res->as_float();
        return unless int($val) == $val and $val >= 0;
        $hash{$val} = $res ."=". $nums->[0] unless ( exists $hash{$res} );
        return;
    }

    my $pick = enum($nums);
    for my $e ( @$pick ) {
        for my $op ( @op ) {
            my @tf = ($e->[0], $op, $e->[1]);
            gen_exp(["(". join("", @tf) .")", @{$e->[2]} ], $limit, $lv+1 );
        }
    }
}

sub enum
{
    my ( $nums ) = @_;
    my $last = $#$nums;
    my $res = [];
    for my $a ( 0 .. $last ) {
        for my $b ( 0 .. $last-1 ) {
            my @tmpr = @$nums;
            push @$res, [splice(@tmpr,$a,1), splice(@tmpr,$b,1), [@tmpr] ];
        }
    }
    return $res;
}

sub spliter
{
    my ($nums, $limit, $pos, $lv, $comb) = @_;
    if ( $lv >= $limit ) {
        push @$comb, [ split(" ", join("", @$nums)) ];
        return;
    }

    for my $id ( $pos+1 .. $#$nums  ) {
        if ( $nums->[$id] eq " " ) {
            spliter( [@$nums], $limit, $id, $lv+1, $comb );
            $nums->[$id] = "";
            spliter( [@$nums], $limit, $id, $lv+1, $comb );
        }
    }
}
复制代码