Count the coins: Difference between revisions
added recursive caching implementation in Perl 5
(Updated third D entry) |
(added recursive caching implementation in Perl 5) |
||
Line 1,033:
<pre>%1 = 242
%2 = 13398445413854501</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
use 5.01;
use Memoize;
sub cc {
my ( $amount, @coins ) = @_;
return 0 if !@coins || $amount < 0;
return 1 if $amount == 0;
my $first = shift @coins;
cc( $amount, @coins ) + cc( $amount - $first, $first, @coins );
}
memoize 'cc';
# Make recursive algorithm run faster by sorting coins descending by value:
sub cc_optimized {
my ( $amount, @coins ) = @_;
cc( $amount, sort { $b <=> $a } @coins );
}
say 'Ways to change $ 1 with common coins: ',
cc_optimized( 100, 1, 5, 10, 25 );
say 'Ways to change $ 1000 with addition of less common coins: ',
cc_optimized( 1000 * 100, 1, 5, 10, 25, 50, 100 );</lang>
=={{header|Perl 6}}==
{{works with|niecza|2012-06}}
| |||