[puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?
- 523066680
- Administrator
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
-
- 一代宗师
- 帖子: 930
- 注册时间: 2017年12月25日 11:12
- 联系:
Re: [puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?
如果一堆时代电子元器件概念之物,问达成一个可行范围内的某个需求,有多少思路,方法方向,可组合选择。
- rubyish
- 渐入佳境
- 帖子: 52
- 注册时间: 2018年04月23日 09:58
- 联系:
Re: [puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?
只會 3 種方法
1: 古典
2: 優雅的窮舉法
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];
}
代码: 全选
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];
}
}
代码: 全选
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
- 帖子: 573
- 注册时间: 2016年07月19日 12:14
- 联系:
Re: [puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?
你解决问题的速度好快(经验丰富),才刚上线就 Post 了三个答案!rubyish 写了: 3 種方法
而且穷举法的方案也比我自己写的快 下班后消化一下
我在知乎看到这个问题的
https://www.zhihu.com/question/315108379
stackoverflow 有个 C++的版本非常优雅,和你第一个方案应该是相同的思路。
https://stackoverflow.com/questions/110 ... 3#19595523
在线用户
正浏览此版面之用户: 没有注册用户 和 4 访客