This reduces the 8316 loops your code requires to 197 which is almost 2 orders of magnitude faster tahn your original and 3.5x faster than grinders example that needs 686 loops. Only 4:1 wastage on the test is pretty good as semi brute force goes and certainly beats the original 166:1. All it does different is to limit the looping to the limited subset of possible cases....
my ( $loops, $cnt );
printf "%4d %4d %4d %4d %4d\n", 100,50,20,10,5;
for (my $e5=0; $e5<=100; $e5+=10 ) {
for (my $e10=0; $e10<=100-$e5; $e10+=10 ) {
for (my $e20=0; $e20<=100-$e10-$e5; $e20+=20 ) {
for (my $e50=0; $e50<=100-$e20-$e10-$e5; $e50+=50 ) {
for (my $e100=0; $e100<=100-$e50-$e20-$e10-$e5; $e100+=100 ) {
$loops++;
if ( $e5+$e10+$e20+$e50+$e100 == 100 ) {
printf "%4d %4d %4d %4d %4d\n",$e100/100,$e50/50,$e20/20,$
+e10/10,$e5/5;
$cnt++;
}
}
}
}
}
}
print "\n$cnt possibilities in $loops loops\n";
__DATA__
100 50 20 10 5
1 0 0 0 0
0 2 0 0 0
0 0 5 0 0
0 1 2 1 0
0 0 4 2 0
0 1 1 3 0
0 0 3 4 0
0 1 0 5 0
0 0 2 6 0
0 0 1 8 0
0 0 0 10 0
0 1 2 0 2
0 0 4 1 2
0 1 1 2 2
0 0 3 3 2
0 1 0 4 2
0 0 2 5 2
0 0 1 7 2
0 0 0 9 2
0 0 4 0 4
0 1 1 1 4
0 0 3 2 4
0 1 0 3 4
0 0 2 4 4
0 0 1 6 4
0 0 0 8 4
0 1 1 0 6
0 0 3 1 6
0 1 0 2 6
0 0 2 3 6
0 0 1 5 6
0 0 0 7 6
0 0 3 0 8
0 1 0 1 8
0 0 2 2 8
0 0 1 4 8
0 0 0 6 8
0 1 0 0 10
0 0 2 1 10
0 0 1 3 10
0 0 0 5 10
0 0 2 0 12
0 0 1 2 12
0 0 0 4 12
0 0 1 1 14
0 0 0 3 14
0 0 1 0 16
0 0 0 2 16
0 0 0 1 18
0 0 0 0 20
50 possibilities in 197 loops
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|