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

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周的时间，开卷完成。

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

hitsubunnu

此题是澳大利亚研究生课程中.NET Programming课的结课作业，老师给了2周的时间，开卷完成。
记得那个时候我觉得C#用着很别扭，周围同学都做不出正确的程序，我一着急就用Perl写了一个然后发给了大家，最后一大帮中国人就是照着我写的Perl的程序硬是转化成了C#代码。

这一段是想暗示我们 你很吊？你在澳大利亚？你是研究生？ 你鄙视在澳大利亚的同学？

其实你不用这么麻烦你直接把硕士论文发出来让我等瞻仰一下

lkk2003rty

背包么？

py

这一段是想暗示我们 你很吊？你在澳大利亚？你是研究生？ 你鄙视在澳大利亚的同学？

其实你不用这么 ...
hitsubunnu 发表于 2011-03-25 08:10

抱歉让你有了如此奇怪的感觉。
既然帖子发在技术论坛，那就只说技术。
我多写了那段话，是因为收拾屋子，看到多年前的作业，找到了以往很多回忆。
没成想，误导别人。我已经把多余的话删了，以免有更多人“误解”。

PS.澳洲的MASTER DEGREE是没有所谓的“硕士论文”的，至少by coursework是没有的。

bernana

回复 4# py


    这样行不行？

1. my $num=$ARGV[0];
   
2. my @list=(100,50,20,10);
   
3. my %hash;
   
4. $hash{10}=1;
   
5. $hash{20}=3;
   
6. $hash{50}=1;
   
7. $hash{100}=1;
   
8. my %result;
   
9. foreach my $key(@list){
   
10.     if(exists $hash{$key} and $hash{$key}>0 and $key<=$num){
    
11.         $result{$key}=int($num/$key);
    
12.         $num=$num-$key*$result{$key};
    
13.         $hash{$key}=$hash{$key}-$result{$key};
    
14.     }
    
15. }
    
16. #获得找钱的结果
    
17. foreach my $find (keys %result){
    
18.     print "$find\t$result{$find}\n";
    
19. }
    
20. #获得剩余钱的结果
    
21. foreach my $find (keys %hash){
    
22.     print "$find\t$hash{$find}\n";
    
23. }

复制代码

py

回复 5# bernana

这样的确是可以找160c出来，但如果机器中有5c=>1, 20c=>3, 50c=>1, 100c => 1，需要找160c的时候就有问题了

py

背包么？
lkk2003rty 发表于 2011-03-25 09:44

什么意思？能不能用模块？
可以不用的
留这个作业的老师是一个白人鬼子，20年的C++程序员，这人挺古怪的，喜欢给学生出些动脑子的作业，总喜欢强调算法和数据结构。他要求不能使用附加的任何接口和现成的函数。

昭襄王

感觉题目少了条件：用户给了多少钱，什么面值的各多少。

py

回复 8# 昭襄王

是的，原本描述的是很详细的，包括有多少种钱币，各多少个，票的面值是多少。还包括图形界面设计的要求。
我简化了这个问题。

这个程序主要的部分是“找钱”，用户具体放了几个什么面值的硬币进去并不是重点。
重点是1：售票机中目前有多少种硬币各多少枚。2：要找的钱是多少。

有了这两个条件就可以决定是否能找出钱来，该怎么找。

这个作业老师在检查的时候是这样，找些特殊的例子。比如：初始化售票机，让其中10c面值的有1枚，20c的有3枚，50c的有1枚。找赎是60c。

lkk2003rty

回复 7# py


   感觉有点像 背包问题 如果把条件改成 找钱的个数最小的话 应该就是个背包了
   但是这个题 没这要求 一个贪心应该就行了