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

py

回复 15# guap514

恩，我就知道论坛上一定有高人。下班了，你的方法我还没仔细看，但非常简洁。
我基本上试了一下，没有问题。这代码太完美了。

我当时还写成了模块，80多行的代码，总觉得这事情被我搞复杂了，可又想不出更好的办法来。

我的办法是把找钱的过程想成一个树的遍历，先走大节点再走小节点。实现起来比你的这个要复杂多了。

昭襄王

这种问题还真不能仔细想，越想越麻烦，如果所有硬币都充足，按照取大不取小原则160美分的分配会是100+50+5*2，如果5美分硬币可能不充足，就要倒回去。。。
不想了，纠结

py

回复  guap514


    好,递归好!
miniqq 发表于 2011-03-25 14:46

这个好像必须用递归，当时老师检查作业，他也没时间一个个的看了可能，就是粗略一看，没用递归就先减一分。因为不用递归的情况下，结果很大可能是错的。

miniqq

回复 23# py


    我承认我写复杂了,但思路应该没问题.递归我看不是必须的吧!

alabos

1. 
   
2. #!/usr/bin/perl
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. my %store = qw{50 2  20 2 10 20 5 7 1  1000};
   
7. 
   
8. my $need_change = 160;
   
9. 
   
10. my $changed = &change($need_change);
    
11. 
    
12. foreach  (reverse keys %$changed)
    
13. {
    
14.         print "$_: -->$changed->{$_}\n";
    
15. }
    
16. 
    
17. 
    
18. sub change ($)
    
19. {
    
20.         my $n_chage = shift;
    
21.         my %changed;
    
22.         my @units =reverse sort {$a <=> $b}  keys %store;
    
23. 
    
24.         foreach  my $unit (@units)
    
25.         {
    
26.                 while ($store{$unit} > 0 && $n_chage - $unit >= 0)
    
27.                 {
    
28.                         $changed{$unit}++;
    
29.                         $store{$unit}--;
    
30.                         $n_chage -= $unit;
    
31.                 }
    
32.         }
    
33.         return \%changed;
    
34. }
    
35. 
    
36. =head
    
37. 在这里有个前提条件，就是，有足够的零钱去找。
    
38. 如果不够的话，就需要加校验了。
    
39. %store 生成一个钱的 hash 面值做为key ，
    
40. key 的定义为系统处理的最小单位
    
41. 处理办法， 通过排序，从大到小依次处理。
    
42. =cut

复制代码

alabos

如果题目指定了用递归，那没办法，必须得用!

不然，为啥不用简单的办法呢？

像这样，用个 while 不是一样简单

ttcn_cu

回复 1# py


    用递归写起来很短啊

1. 
   
2. #!perl
   
3. use strict;
   
4. my @cc=(
   
5.         [50=>99999],
   
6.         [20=>99999],
   
7.         [5=>99999]
   
8. );
   
9. my $input=1111830;
   
10. my $count=0;
    
11. my %re;
    
12. sub change{
    
13.         my @c=@{$_[0]};
    
14.         my $t=$_[1];
    
15.         while(1){
    
16.                 $count++;
    
17.                 $#c < 0 and return 0;
    
18.                 $#c >=0 and do {
    
19.                         my $h=$c[0]->[0];
    
20.                         $c[0]->[1]--;
    
21.                         shift @c if ($c[0]->[1] <= 0);
    
22.                         $t>$h and do {
    
23.                                 my $r=change(\@c,($t-$h));
    
24.                                 $r == 1 and do {
    
25.                                         $re{$h}++;
    
26.                                         return 1;
    
27.                                 };
    
28.                                 $r == 0 and do {
    
29.                                         shift @c;
    
30.                                         next;
    
31.                                 };
    
32.                         };
    
33.                         $h==$t and do {
    
34.                                 $re{$h}++;
    
35.                                 return 1;
    
36.                         };
    
37.                         return 0;
    
38.                 };
    
39.         }
    
40. }
    
41. print "$input=\n";
    
42. change(\@cc,$input) or print "not found";
    
43. print "$_=>$re{$_}\n" for keys %re;
    
44. print "\nloop count=$count\n";
    
45. 
    
46. 
    

复制代码

要是Perl能像C一样支持宏替换把and 换成 箭头之类的符号看起来就舒服
貌似和15楼原理一样，展开了一下

py

如果题目指定了用递归，那没办法，必须得用!

不然，为啥不用简单的办法呢？

像这样，用个 while 不是 ...
alabos 发表于 2011-03-25 16:41

没有，老师从没说过一定要用递归，只是，没有用递归的人，在测试过老师给出的那几个例子的时候都多少出了问题。

我觉得肯定还是可以不用递归成功做出来的，只是递归写起来很清楚简介

py

回复 27# ttcn_cu

对，递归就是效率低，写起来短。不过也要注意，当时很多人都用递归，但是很多人程序都有错误。等周一上班了我再试试大家的程序。

ttcn_cu

回复 29# py


    不递归

1. 
   
2. #!perl -w
   
3. use strict;
   
4. my @original=(
   
5.     [100=>11111111111],
   
6.     [20=>11111111111],
   
7.     [5=>11111]
   
8. ); #原始存的货币数目
   
9. my $input=2175;
   
10. my $count=0;
    
11. my @backup=map {
    
12.     [
    
13.         $_->[0],
    
14.         $a=int($input/$_->[0])<$_->[1]?int($input/$_->[0]):$_->[1],
    
15.         $_->[0]*$a
    
16.     ]
    
17. } @original;  #优化备份
    
18. my @worker = map { [$_->[0],$_->[1]]} @backup;
    
19. $_->[2]=$_->[0]*$_->[1] for @worker;
    
20. BIG:
    
21. while (1){
    
22.     $count++;
    
23.     my $sum=0;
    
24.     for (0..$#worker-1){
    
25.         $sum+=$worker[$_]->[2];
    
26.     }
    
27.     $sum+=$worker[$#worker]->[0]*$worker[$#worker]->[1];
    
28.     my $delta=$sum-$input;
    
29.     if ($delta==0){
    
30.         print "$sum = ";
    
31.         print join " + ", map { "$_->[0] * $_->[1]" } grep {$_->[1] } @worker;
    
32.         last BIG;
    
33.     }
    
34.     for my $idx (reverse 0..$#worker){
    
35.         next if $worker[$idx]->[1]==0;
    
36.         if ($idx!=$#worker){
    
37.             $worker[$idx]->[1]--;
    
38.         }
    
39.         else{ #最小面额使用贪婪
    
40.             $worker[$idx]->[1] =
    
41.                 ($delta <= $worker[$idx]->[0]||int($delta/$worker[$idx]->[0])>$worker[$idx]->[1])
    
42.                 ?
    
43.                     0
    
44.                 :
    
45.                     $worker[$idx]->[1] - int($delta/$worker[$idx]->[0]);
    
46.         }
    
47.         $worker[$idx]->[2] = $worker[$idx]->[0] * $worker[$idx]->[1];
    
48.         @worker[($idx+1)..$#worker] = map { [$_->[0],$_->[1],$_->[2]] } @backup[($idx+1)..$#worker];
    
49.         next BIG;
    
50.     }
    
51.     print "not found";
    
52.     last BIG;
    
53. }
    
54. print "\nloop count=$count";
    
55. 
    

复制代码