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

昭襄王

回复  昭襄王

是的，原本描述的是很详细的，包括有多少种钱币，各多少个，票的面值是多少。还包括图形界 ...
py 发表于 2011-03-25 12:13

    我觉得这个条件非常重要，如果没有这个条件将没法正确处理如下流程：
用户消费了40美分，但是蛋疼的给了3个1美元（或1个1美元1个2美元，或几个50美分等等），如果没有分捡入库操作，原金库只有1个1美元，加上其他零钱还是不足所需金额，而事实上加上用户多给的2美元，零钱是足够的。

考虑到自动售货机是需要循环作业的，这个条件就更不可或缺了。

miniqq

回复 1# py

Hi, 我给出一个:
首先,我对题目的理解是: 给定一个数A, 从数组 B中找出几个数,使其和等于A,并且大数优先. 通常A比B中最大的数大.

说明,我省略了两个步骤: 把数组变为hash, 从大到小排列不重复的数组 @list.

脚本:

1. 
   
2. #!/usr/bin/perl -w
   
3. #
   
4. 
   
5. use strict;
   
6. 
   
7. my %hash = ();
   
8. 
   
9. $hash{5} = 1;
   
10. $hash{20} = 3;
    
11. $hash{50} = 1;
    
12. $hash{100} = 1;
    
13. 
    
14. my $osum = 160;
    
15. my $sum = $osum;
    
16. my @list = (100,50,20,5);
    
17. my %result;
    
18. my @give;
    
19. my $trys = scalar(@list);
    
20. 
    
21. retry:
    
22. foreach my $c (@list) {
    
23.         if ($sum >= $c and $sum > 0) {
    
24.                 if ($hash{$c} == 1) {
    
25.                         $sum = $sum - $c;
    
26.                         $result{$c} = 1;
    
27.                         push @give, $c;
    
28.                         next;
    
29.                 }
    
30.                 elsif ($hash{$c} > 1) {
    
31.                         my $i = 0;
    
32.                         for($i=0, $i < $hash{$c}, ++$i) {
    
33.                                 if ($sum >= $c and $sum > 0) {
    
34.                                         $sum = $sum - $c;
    
35.                                         $result{$c}++;
    
36.                                         if ($result{$c} > $hash{$c}) {
    
37.                                                 print "not found\n";
    
38.                                                 exit 1;
    
39.                                         }
    
40.                                         push @give, $c;
    
41.                                         next;
    
42.                                 }
    
43.                         }
    
44.                 }
    
45.         }
    
46.         else {
    
47.                 next;
    
48.         }
    
49. }
    
50. 
    
51. if ($sum > 0) {
    
52.         $sum = $osum;
    
53.         %result = ();
    
54.         my $last;
    
55.         if(scalar(@give) >=2) {
    
56.                 pop @give;
    
57.                 $last = pop @give;
    
58.         }
    
59.         else {
    
60.                 $last = pop @give;
    
61.         }
    
62.         $trys--;
    
63.         if ($trys < 1 or !$last) {
    
64.                 print "not found\n";
    
65.                 exit 1;
    
66.         }
    
67.         @give = ();
    
68.         @list = grep (!/$last/, @list);
    
69.         goto retry;
    
70. }
    
71. 
    
72. if ($sum == 0) {
    
73. foreach my $find (keys %result) {
    
74.         print "$find\t$result{$find}\n";
    
75. }
    
76. 
    
77. }
    
78. else {
    
79.         print "not found\n";
    
80. }
    
81. 
    

复制代码

觉得还不完善.不知哪里要改一下.

py

我觉得这个条件非常重要，如果没有这个条件将没法正确处理如下流程：
用户消费了40美分，但是蛋 ...
昭襄王 发表于 2011-03-25 12:51

呵呵，看来你是好好想过这个问题了。当初做这个作业的时候，因为这个问题我还找老师争论过。
我问他“找钱的来源是不是要把用户扔进去的钱也算在内？”
他说“whatever”。他说算在内和不算在内，在代码层面上只会有很小的改动。
后来想想也是，如果算在一起找钱，那在计算找赎的时候就把用户扔的钱加在一起算就是了，代码改动很小。

为这个事我还去看了那个自动售票机，晚上会有警察把那个机器打开，我仔细观察了一下，实际情况是，那里面有不记期数的硬币，不太可能出现“需要把当前用户放进去的那几个硬币也算作找赎才可以的情况”。
而且，在买票的时候，当你放入的钱，达到或超过了当前票面值的时候，这个时候机器会吐出一张票，并吐出找赎。然后你会听到“哗啦”一声，你刚才放入的钱才真正掉入售票机里面。
所以，很有可能真实的售票机只是从机器里面找钱的，并没有算你放进去的硬币。

PS.其实这样也是简化工业设计，钱从两个地方出来，你说你那出钱的口做在哪好啊。。。

py

回复  py

Hi, 我给出一个:
首先,我对题目的理解是: 给定一个数A, 从数组 B中找出几个数,使其和等于A,并 ...
miniqq 发表于 2011-03-25 13:16

我试了一下，你可能漏掉了一些可能性，比如，按照你现在脚本上写的样子，如果找赎是80的时候，结果应该提示无法找出。但程序会死循环。

另外，如果售票机初始库存是

1. $hash{5} = 1;
   
2. $hash{20} = 2;
   
3. $hash{50} = 1;
   
4. 
   
5. my $osum = 60;
   
6. my $sum = $osum;
   
7. my @list = (50,20,5);
   

复制代码

找赎是60的时候，也有错误，会找出三个20来。

guap514

1. sub get {
   
2.     my $need    = shift;
   
3.     my $hash    = shift;
   
4.     my @array   = @_;
   
5.     my @arr = sort { $b <=> $a } grep { $_ <= $need and $hash->{ $_ } } keys %$hash;
   
6.     foreach ( @arr ){
   
7.         return join ',', @array, $_ if $_ == $need;
   
8.         my %hash = %$hash;
   
9.         $hash{ $_ }--;
   
10.         my $ret = get( $need - $_, \%hash, @array, $_ );
    
11.         return $ret if $ret;
    
12.     }
    
13. }
    
14. 
    
15. while(<DATA>){
    
16.     chomp;
    
17.     print "$_ => ";
    
18.     print get $_, {
    
19.         1   => 4,
    
20.             5        => 1,
    
21.             20        => 3,
    
22.             50        => 1,
    
23.             100        => 1
    
24.     };
    
25.     print "\n";
    
26. }
    
27. 
    
28. __DATA__
    
29. 160
    
30. 150
    
31. 111

复制代码

回复 1# py

miniqq

回复 14# py


    改了一下,你再试试.

bernana

回复 14# py

1. #!/usr/bin/perl -w
   
2. use warnings;
   
3. use strict;
   
4. use Data::Dumper;
   
5. my %hash = ();
   
6. $hash{$ARGV[1]} = $ARGV[2];
   
7. $hash{$ARGV[3]} = $ARGV[4];
   
8. $hash{$ARGV[5]} = $ARGV[6];
   
9. $hash{$ARGV[7]} =$ARGV[8];
   
10. my $osum = $ARGV[0];
    
11. my $sum = $osum;
    
12. my @list = (100,50,20,5);
    
13. my %result;
    
14. my @give;
    
15. retry:
    
16. foreach my $c (@list) {
    
17.         if ($sum >= $c and $sum > 0) {
    
18.                 if ($hash{$c} == 1) {
    
19.                         $sum = $sum - $c;
    
20.                         $result{$c} = 1;
    
21.                         push @give, $c;
    
22.                         next;
    
23.                 }
    
24.                 if ($hash{$c} > 1) {
    
25.                         for(my $i=0; $i < $hash{$c}; $i++) {
    
26.                                 if ($sum >= $c and $sum > 0) {
    
27.                                         $sum = $sum - $c;
    
28.                                         $result{$c}++;
    
29.                                         push @give, $c;
    
30.                                         next;
    
31.                                 }
    
32.                         }
    
33.                 }
    
34.         }
    
35.         else {
    
36.                 next;
    
37.         }
    
38. }
    
39. if ($sum != 0) {
    
40.         $sum = $osum;
    
41.         %result = ();
    
42.                 if ($#give == 0) {
    
43.                         print "error\n";
    
44.                         exit;
    
45.                 }
    
46.         pop @give;
    
47.         my $last = pop @give;
    
48.         @give = ();
    
49.         @list = grep (!/$last/, @list);
    
50.         goto retry;
    
51. }
    
52. foreach my $find (sort {$b<=>$a} keys %result) {
    
53.         print "$find\t$result{$find}\n";
    
54. }

复制代码

miniqq

回复 15# guap514


    好,递归好!

昭襄王

回复 13# py


    whaterer...就是说不考虑缺少任何一种面额的硬币了？那何必规定目前每种有几枚呢？假设和目的是矛盾的。

昭襄王

perl有goto真是方便啊