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

头像
523066680
Administrator
Administrator
帖子: 453
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 46 times
Been thanked: 77 times
联系:

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

帖子 #1 523066680 » 2019年03月10日 17:45

RT

zzz19760225
渐入佳境
渐入佳境
帖子: 51
注册时间: 2017年12月25日 11:12
拥有现金: 锁定
储蓄: 锁定
Has thanked: 62 times
Been thanked: 4 times
联系:

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

帖子 #2 zzz19760225 » 2019年03月17日 10:27

如果一堆时代电子元器件概念之物,问达成一个可行范围内的某个需求,有多少思路,方法方向,可组合选择。

头像
rubyish
初来炸道
初来炸道
帖子: 15
注册时间: 2018年04月23日 09:58
拥有现金: 锁定
Has thanked: 13 times
Been thanked: 9 times
联系:

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

帖子 #3 rubyish » 2019年03月19日 08:39

只會 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
帖子: 453
注册时间: 2016年07月19日 12:14
拥有现金: 锁定
储蓄: 锁定
Has thanked: 46 times
Been thanked: 77 times
联系:

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

帖子 #4 523066680 » 2019年03月19日 08:48

rubyish 写了: 3 種方法

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

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

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


回到 “算法和编码”

在线用户

用户浏览此论坛: 没有注册用户 和 1 访客