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

py

题目：投币自动售票程序
要求: 找钱原则“有大面值的货币就不找小面试的货币”

例如：当售票机中有10c=>1, 20c=>3, 50c=>1。需要找60c，这个时候就要找1个50c的和1个10c的硬币，而不是3个20c的硬币。
再比如，当售票机中有5c=>1, 20c=>3, 50c=>1, 100c($1) => 1，需要找160c，这个时候也需要能正确找钱。
说的简单点，就是有个函数，你提供要找的钱当参数，返回值就是找出来的钱（例如：一个数组）。

此题是澳大利亚研究生课程中.NET Programming课的结课作业，老师给了2周的时间，开卷完成。

最近收拾屋子的时候又看到了这个作业，发出来，看看大家有没有什么精妙的办法。

bhpang2

就是以下的算式吧:
m=100x+50y+20z+10a+5b
m是余额,按面额从大到小顺序
第一步    x=m /100 , x是需要100面值的张数.在和钱箱中的该面值的钱的数量比较,根据结果得到x的值(x大于等于零),
第二步    m1=m-100x , 同样的用m1处理其它面额的,递归算法.

py

.NET Programming？这个不用两周吧？
2gua 发表于 2011-04-17 11:10

这门课是学一个学期的，一周一节课，一共学半年。
这个作业最后老师给了1个半月。结果还是绝大多数人做不出。
那门课其实是学习C#的基础课，很多选那门课的人接触编程并不多，再加上到期末了，还有其他课需要忙，所以老师一般会给比较宽裕的时间。

py

回复 50# vgra
可以看看15楼的回复。。。。。。个人感觉是最好的答案
或是use Ticketmaster;我把它写成模块了

2gua

.NET Programming？这个不用两周吧？

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;
                }
        }
}

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. }
    

复制代码

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";
    

复制代码

py

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

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

ge_yong_linux