use strict; use warnings; sub greedy_change { my \$change = shift; my @coins = @_; my @result; for my \$i (0..\$#coins) { my \$val = int(\$change/\$coins[\$i]); \$change -= \$val*\$coins[\$i]; push @result,\$val; } return @result; } sub pearson_counterexample { my \$i = shift; my \$j = shift; my @coins = @_; # Let position \$i be the highest coin used, # Let positon \$j be the lowest. Then the # potential counterexample will be: # 1) Compute the greedy change for the # next highest coins value - 1. # # 2) Copy all coin counts from 0 to \$j-1 # # 3) Add one to the coin count at position \$j. # # If this combination is more efficient than # the greedy value, we have a counterexample. my \$value = \$coins[\$i-1] - 1; my @greedy = greedy_change(\$value, @coins); my @example = (0) x @coins; \$example[\$_] = \$greedy[\$_] for (0..\$j-1); \$example[\$j] = \$greedy[\$j]+1; # Compute the numeric value and see if it # represents the amount more efficiently # than the greedy way. my \$example_value = 0; \$example_value += \$coins[\$_]*\$example[\$_] for (0..\$#example); @greedy = greedy_change(\$example_value, @coins); my (\$example_count, \$greedy_count); \$example_count += \$example[\$_] for (0..\$#example); \$greedy_count += \$greedy[\$_] for (0..\$#greedy); # This candidate case did not work. return if \$example_count >= \$greedy_count; return @example; } # Read the coin system from the command line, in # decreasing order of size. my @coins = @ARGV; if (@coins < 3) { print "Must have a least three coins\n"; exit(1); } my (\$i,\$j); my \$found = 0; EXAMPLES: for (\$i = 1; \$i < @coins; ++\$i) { for (\$j = \$i; \$j < @coins; ++\$j) { my @example = pearson_counterexample(\$i, \$j, @coins); if (@example) { print "Counterexample: ",join(" ",@example),"\n"; \$found = 1; last EXAMPLES; } } } print "No counterexamples found. Good coin system\n" unless \$found;