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

chenhao392

这是生物信息学算法导论，第一章的例子嘛！！！

yinyuemi

觉得很有意思，写了个awk的，大家帮忙测试下

awk -v money=120 -f awk.script

1. BEGIN{
   
2. output(money)
   
3. }
   
4. function output(b)
   
5.         {
   
6.         list[0]=100;
   
7.         list[1]=50;
   
8.         list[2]=20;
   
9.         list[3]=20;
   
10.         list[4]=20;
    
11.         list[5]=5;
    
12.         list[6]=5;
    
13.         for(i=0;i<=6;i++)
    
14.                 if(b<list[i])
    
15.                 {}
    
16.                 else if (b==list[i])
    
17.                 {print b;break}
    
18.                 else {
    
19.                         print list[i]
    
20.                         b=b-list[i]
    
21.                         if (b<=0)
    
22.                         {break}
    
23.                         else
    
24.                         {print a[i]}
    
25.                 }
    
26.         }
    

复制代码

alabos

没有，老师从没说过一定要用递归，只是，没有用递归的人，在测试过老师给出的那几个例子的时候都多少出 ...
py 发表于 2011-03-25 21:18

   

我认为思路最重要。  思路决定 写法。

py

回复 31# chenhao392

恩，我估计这题也不会是那老师自己创造出来的。货币找钱问题应该是比较经典的问题了。

py

觉得很有意思，写了个awk的，大家帮忙测试下

awk -v money=120 -f awk.script
yinyuemi 发表于 2011-03-26 03:31

这个不对。当list[6]=4，找赎为160的时候，找出的钱是错误的。

py

我认为思路最重要。  思路决定 写法。
alabos 发表于 2011-03-26 10:55

思路肯定是最重要的，我当时只想到了多叉树遍历。

把找赎当作根节点，每次需要找钱都先找出最大面值的货币，生成下一个节点，如果出现无法找出的情况就退回一个节点继续寻找。如果有多种货币组合都能找出钱，那最优的组合肯定会先出现。

py

回复  py


    用递归写起来很短啊要是Perl能像C一样支持宏替换把and 换成 箭头之类的符号看起来就舒服 ...
ttcn_cu 发表于 2011-03-25 20:24

这个也是不对的。
例如：

1. my @cc=(
   
2.         [50=>1],
   
3.         [20=>3],
   
4.         [5=>1]
   
5. );
   
6. my $input=60;

复制代码

yinyuemi

回复 35# py

这样呢？只要list数组包含足够的零钱数

1. BEGIN{
   
2. output(money)
   
3. }
   
4. function output(b)
   
5.         {
   
6.         list[0]=100;
   
7.         list[1]=50;
   
8.         list[2]=20;
   
9.         list[3]=20;
   
10.         list[4]=20;
    
11.         list[5]=5;
    
12.         list[6]=5;
    
13.         list[7]=5;
    
14.         list[8]=4;
    
15.         for(i=0;i<=8;i++)
    
16.                 if(b<list[i])
    
17.                 {}
    
18.                 else if (b==list[i])
    
19.                 {print b;break}
    
20.                 else {
    
21.                         print list[i]
    
22.                         b=b-list[i]
    
23.                         if (b<=0)
    
24.                         {break}
    
25.                         else
    
26.                         {print a[i]}
    
27.                 }
    
28.         }
    

复制代码

py

回复 38# yinyuemi
这个题目其实就是在讨论零钱不充足的情况下的找钱过程的。零钱足够多的时候基本不会出错
还有，这样的设计也不好吧。把零钱数量就写死了，list数组中元素应该是有限的，可以设计个二维数组来保存每个币种的数量

yinyuemi

回复 39# py


   看了问题还挺麻烦，看高手们的吧