[puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?

回复
zzz19760225
一代宗师
一代宗师
帖子: 930
注册时间: 2017年12月25日 11:12
联系:

Re: [puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?

帖子 zzz19760225 »

如果一堆时代电子元器件概念之物,问达成一个可行范围内的某个需求,有多少思路,方法方向,可组合选择。
头像
rubyish
渐入佳境
渐入佳境
帖子: 52
注册时间: 2018年04月23日 09:58
联系:

Re: [puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?

帖子 rubyish »

只會 3 種方法
1: 古典

代码: 全选

my $val = 10000;
my @test = ( [ 1, 5, 10, 20, 50, 100 ], [ 2, 8, 16, 60, 120 ] );
for my $coin (@test) {
    my $count = classic( $coin, $val );
    say $count;
}

# ____________________SUB____________________

sub classic {
    my ( $coin, $sum ) = @_;
    my @memo = 1;
    $memo[$sum] = 0;

    for my $i ( 1 .. $sum ) {
        $memo[$i] = $i % $coin->[0] == 0;
    }

    for my $i ( 1 .. $#$coin ) {
        for my $j ( $coin->[$i] .. $sum ) {
            $memo[$j] =
                $memo[$j] && $memo[ $j - $coin->[$i] ]
              ? $memo[$j] + $memo[ $j - $coin->[$i] ]
              : 0;
        }
    }
    return $memo[$sum];
}
2: 優雅的窮舉法

代码: 全选

my @test = ( [ 1, 5, 10, 20, 50, 100 ], [ 2, 8, 16, 60, 120 ] );
my $money = 1000;       # 10000 => SLOW
my $COUNT;
for my $bee (@test) {
    $COUNT = 0;
    count( $bee, $#$bee, $money );
    say $COUNT;
}
# ____________________SUB____________________

sub count {
    my ( $bee, $indes, $money ) = @_;
    if ( $indes == 0 ) {
        $COUNT++ if $money % $bee->[0] == 0;
        return;
    }
    my $num  = int( $money / $bee->[$indes] );
    my $toto = $money;
    for my $i ( 0 .. $num ) {
        count( $bee, $indes - 1, $toto );
        $toto -= $bee->[$indes];
    }
}
3: 窮舉法的加速

代码: 全选

use 5.028;
sub How;
sub God;
my @test = ( [ 1, 5, 10, 20, 50, 100 ], [ 2, 8, 16, 60, 120 ] );
my $composition = 10000;
my @God;    # God bless you.

for my $many (@test) {
    undef @God;
    my $methods = How $many, $composition;
    say "methods = $methods";
}

# ____________________SUB____________________

sub How {
    my ( $many, $coposi ) = @_;
    my @Gcd = $many->[0];
    for ( 1 .. $#$many - 1 ) {
        my $bless = $many->[$_];
        my $you   = $Gcd[ $_ - 1 ];
        $Gcd[$_] = God $bless, $you;
    }
    return how( $many, \@Gcd, $#$many, $coposi );
}

sub how {
    my ( $many, $Gcd, $indes, $coposi ) = @_;
    my $numba   = int( $coposi / $many->[$indes] );
    my $bless   = $coposi;
    my $methods = 0;
    if ( $indes == 1 ) {
        my $you  = $many->[0];
        my $that = $many->[1];
        return $God[$indes][$coposi] if $God[$indes][$coposi];
        for ( 0 .. $numba ) {
            $methods++ if $bless % $you == 0;
            $bless -= $that;
        }
        return $God[$indes][$coposi] = $methods;
    }

    my $next = $indes - 1;
    my $you  = $Gcd->[$next];
    for ( 0 .. $numba ) {
        my $god = $bless % $you == 0;
        if ($god) {
            $methods += $God[$next][$bless]
              // how( $many, $Gcd, $next, $bless );
        }
        $bless -= $many->[$indes];
    }
    return $God[$indes][$coposi] = $methods;
}

sub God {
    $_[1] ? God( $_[1], $_[0] % $_[1] ) : $_[0];
}
$_
头像
523066680
Administrator
Administrator
帖子: 573
注册时间: 2016年07月19日 12:14
联系:

Re: [puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?

帖子 523066680 »

rubyish 写了: 3 種方法
你解决问题的速度好快(经验丰富),才刚上线就 Post 了三个答案!
而且穷举法的方案也比我自己写的快 下班后消化一下 :applaud3

我在知乎看到这个问题的
https://www.zhihu.com/question/315108379

stackoverflow 有个 C++的版本非常优雅,和你第一个方案应该是相同的思路。
https://stackoverflow.com/questions/110 ... 3#19595523
回复

在线用户

正浏览此版面之用户: 没有注册用户 和 1 访客