给大家发一个澳大利亚研究生课程作业题

yifangyou

我的可以，
使用了递归
1.若是要找160的话
2.有100的话，先找100
3.这时需要找的就剩下60了，这时调用递归
4.递归第一次先找回50，剩下10，再找回5，发现最后还剩下5，找钱失败，这时回滚。
5.递归第二次先找回20，剩下40,再找回20，剩下20,再找回20,剩下0，返回成功
6.输出

1. #例如：当售票机中有10c=>1, 20c=>3, 50c=>1。需要找60c，这个时候就要找1个50c的和1个10c的硬币，而不是3个20c的硬币。
   
2. #再比如，当售票机中有5c=>1, 20c=>3, 50c=>1, 100c($1) => 1，需要找160c，这个时候也需要能正确找钱。
   
3. #说的简单点，就是有个函数，你提供要找的钱当参数，返回值就是找出来的钱（例如：一个数组）。
   
4. #所有的币值列表
   
5. @coins=(   100,50,20,10,5,2,1);
   
6. #每个币值对应的个数
   
7. @coinnums=(  1, 1, 3, 0,1,0,0);
   
8. 
   
9. #每个币值对应的个数
   
10. @paybackCoins=();
    
11. $paybackTotal=160;
    
12. if(payback($paybackTotal)==0){
    
13.         print join(",",@paybackCoins)."\n";
    
14. }else{
    
15.         print "payback $paybackTotal fail\n";
    
16. }
    
17. 
    
18. @coins=(   100,50,20,10,5,2,1);
    
19. @coinnums=(  0, 1, 3, 1,0,0,0);
    
20. @paybackCoins=();
    
21. $paybackTotal=60;
    
22. if(payback($paybackTotal)==0){
    
23.         print join(",",@paybackCoins)."\n";
    
24. }else{
    
25.         print "payback $paybackTotal fail\n";
    
26. }
    
27. 
    
28. @paybackCoins=();
    
29. $paybackTotal=55;
    
30. if(payback($paybackTotal)==0){
    
31.         print join(",",@paybackCoins)."\n";
    
32. }else{
    
33.         print "payback $paybackTotal fail\n";
    
34. }
    
35. 
    
36. sub payback{
    
37.         my $payback=shift;
    
38.         $coinslen=scalar(@coins);
    
39.         my $i=0;
    
40.         for($i=0;$i<$coinslen;$i++){
    
41.                         if($coinnums[$i]>0){
    
42.                                 my $coin=$coins[$i];
    
43.                                
    
44. #                                每次都从最大币值开始循环
    
45.                                 if($payback >= $coin){
    
46.                                         push(@paybackCoins,$coin);
    
47.                                         $payback-=$coin;
    
48.                                         $coinnums[$i]--;
    
49.                                         if($payback<=0){
    
50. #                                                剩下0时返回
    
51.                                                 return 0;
    
52.                                         }
    
53. #                                        继续找剩下的钱
    
54.                                         if(payback($payback)!=0){
    
55. #                                                剩下的钱找不完时，回滚
    
56.                                                 $rollbackCoin=pop(@paybackCoins);       
    
57.                                                 $coinnums[$i]++;
    
58.                                                 $payback+=$rollbackCoin;
    
59.                                         }else{
    
60. #                                                剩下的钱找完时，返回
    
61.                                                 return 0;       
    
62.                                         }
    
63.                                 }
    
64.                         }
    
65.                 }
    
66.         return 1;
    
67. }
    

复制代码

alabos

alabos 发表于 2011-03-25 16:34

   
这个代码不正确？

fdkwisk

进来看看题。

chenjintao_ii

c是澳大利亚钱币单位吗？看这个好费劲哦，直接写10块，20块这样好理解一些{:3_193:}

huangwei1024

这个需要在.net programming课程上做这样的题目嘛，这种题目应该放到算法或数据结构课上
“有大面值的货币就不找小面试的货币”
先对面值排序，贪心+递归枚举，不难，或者dp也可
其实就是个组合算法

ge_yong_linux

py

c是澳大利亚钱币单位吗？看这个好费劲哦，直接写10块，20块这样好理解一些
chenjintao_ii 发表于 2011-03-31 14:57

"c" for cent
我照着那要求抄的，就全写成c了。。。

mingxw

1. 
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. sub find_share {
   
6.         my ($target,$treasues)=@_;
   
7.         return [] if $target==0;
   
8.         return if $target<0 || @$treasues==0;
   
9.         my ($first,@rest)=@$treasues;
   
10.         my $solution = find_share($target-$first,\@rest);
    
11.         return [$first,@$solution] if $solution;
    
12.         return find_share($target,\@rest);
    
13. }
    
14. 
    
15. my @treasures=(100,50,20,20,20,10,5,5);
    
16. my $target=160;
    
17. my $solution = find_share($target,\@treasures);
    
18. 
    
19. print "@$solution\n";
    

复制代码

mingxw

改进一下：

1. 
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. use constant TREASUER_TYPES => 4;
   
6. my @trea_list=(100,50,20,5);
   
7. my $trea_num =[1,  2, 3,  1];
   
8. 
   
9. sub find_share {
   
10.         my ($target,$type,$nums)=@_;
    
11.         return ([],$nums) if $target==0;
    
12.         return (undef,$nums) if $type>=TREASUER_TYPES;
    
13.         return find_share($target,$type+1,$nums) if $$nums[$type]<=0;
    
14.        
    
15.         my $first = $trea_list[$type];
    
16.         return find_share($target,$type+1,$nums) if $target < $first;
    
17.         $$nums[$type]--;
    
18.         return ([$first],$nums) if $target == $first;
    
19.         my $solution;       
    
20.         ($solution,$nums) = find_share($target-$first,$type,$nums);
    
21.         return ([$first,@$solution],$nums) if $solution;
    
22.         $$nums[$type]++;
    
23.         return find_share($target,$type+1,$nums);
    
24. }
    
25. 
    
26. my $target=160;
    
27. my $solution;
    
28. my $i=0;
    
29. print "\nFind $target in ",join(", ",map {$trea_list[$i++]." x ".$_} @$trea_num),"\n";
    
30. ($solution,$trea_num) = find_share($target,0,$trea_num);
    
31. if($solution) {
    
32.         $i=0;
    
33.         print "\nFound : ",join(", ",@$solution);
    
34.         print "\nTreasures remain: ",join(", ",map {$trea_list[$i++]." x ".$_} @$trea_num),"\n";
    
35. }
    

复制代码

vgra

回复 1# py


#!/usr/bin/perl -w

use strict;
use warnings;

my $fh;
if (not open($fh, "< ./pocket_money")) {
        print "Failed to open file [pocket_money]\n";
        exit(-1);
}
my @raw_data;
while (<$fh>) {
        chomp;
        my @tmp = split(/\s/, $_);
        if (2 != @tmp || $tmp[0] !~ /[0-9]+/ || $tmp[1] !~ /[0-9]+/) {
                print "Invalid numer\n";
                next;
        } else {
                push(@raw_data, [ @tmp ]);
        }
}
close($fh);
sub by_face_value {
        return $a->[0] <=> $b->[0];
}
my @pocket_money = reverse sort by_face_value @raw_data;

my $money;
my $err_cnt = 0;
while(1) {
        print "Enter money:";
        $money = <>;
        if ($money !~ /[0-9]+/) {
                print "Invalid money number\n";
                ++$err_cnt;
                exit(-1) if (5 == $err_cnt);
        } else {
                last;
        }
}

my @ret;
my @balance_pocket_money;
my $ok_flag = 0;
my $old_money = $money;
while (!$ok_flag) {
        my $quotient;
        my $remainder = $money;

        my $cur_face_value = shift(@pocket_money);
        if ($money < $cur_face_value->[0]) {

                push(@balance_pocket_money, $cur_face_value);
        } else {
                $quotient = int($money / $cur_face_value->[0]);
                $quotient = ($quotient > $cur_face_value->[1]) ? $cur_face_value->[1] : $quotient;
                $remainder = $money - $cur_face_value->[0] * $quotient;

                push(@ret, [ $cur_face_value->[0], $quotient ]);
                $cur_face_value->[1] = $cur_face_value->[1] - $quotient;
                push(@balance_pocket_money, $cur_face_value) if (0 < $cur_face_value->[1]);

                $money = $remainder;
        }

        if (0 == $remainder) {
                $ok_flag = 1;
                @pocket_money = (@balance_pocket_money, @pocket_money);
                print "找零组合:\n";
                foreach (@ret) {
                        print "面值:".$_->[0]."数量:".$_->[1]."\n";
                }
                print "----------------------------------------\n";
                print "剩余零钱:\n";
                foreach (@pocket_money) {
                        print "面值:".$_->[0]."数量:".$_->[1]."\n";
                }
        } else {
                while (0 == @pocket_money && 0 != @ret) {
                        my $ready_recall = 0;
                        $cur_face_value = pop(@ret);

                        for (my $idx = 0; $idx < @balance_pocket_money; ++$idx) {
                                if ($cur_face_value->[0] < $balance_pocket_money[$idx]->[0]) {
                                        next;
                                } elsif ($cur_face_value->[0] == $balance_pocket_money[$idx]->[0]) {
                                        --$cur_face_value->[1];
                                        $money += $cur_face_value->[0];
                                        if (0 < $cur_face_value->[1]) {
                                                push(@ret, $cur_face_value);
                                        }

                                        ++$balance_pocket_money[$idx]->[1];
                                        @pocket_money = splice(@balance_pocket_money, $idx + 1);

                                        $ready_recall = 1;
                                        last;
                                } else {
                                        --$cur_face_value->[1];
                                        $money += $cur_face_value->[0];
                                        if (0 < $cur_face_value->[1]) {
                                                push(@ret, $cur_face_value);
                                        }

                                        @pocket_money = splice(@balance_pocket_money, $idx);
                                        push(@balance_pocket_money, [ $cur_face_value->[0], 1 ]);

                                        $ready_recall = 1;
                                        last;
                                }
                        }
                        if (!$ready_recall) {
                                $money += $cur_face_value->[0] * $cur_face_value->[1];
                                push(@balance_pocket_money, $cur_face_value);
                        }
                }
                if ($money == $old_money) {
                        print "现有的零钱组合无法对[$money]找零:\n";
                        foreach (@balance_pocket_money) {
                                print "面值:".$_->[0]."数量:".$_->[1]."\n";
                        }
                        foreach (@pocket_money) {
                                print "面值:".$_->[0]."数量:".$_->[1]."\n";
                        }
                        last;
                }
        }
}