[puzzle]有面值1,5,10,20,50,100的人民币,问10000有多少种组成方法?
发表于 : 2019年03月10日 17:45
RT
Programming for fun
https://funicode.net/
代码: 全选
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];
}
你解决问题的速度好快(经验丰富),才刚上线就 Post 了三个答案!rubyish 写了: 3 種方法