投币自动售票程序

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

例如：当售票机中有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课的结课作业

解题原理：

使用了递归
1.若是要找160的话
2.有100的话，先找100
3.这时需要找的就剩下60了，这时调用递归
4.递归第一次先找回50，剩下10，再找回5，发现最后还剩下5，找钱失败，这时回滚。
5.递归第二次先找回20，剩下40,再找回20，剩下20,再找回20,剩下0，返回成功
6.输出

 

 

#例如：当售票机中有10c=>1, 20c=>3, 50c=>1。需要找60c，这个时候就要找1个50c的和1个10c的硬币，而不是3个20c的硬币。

#再比如，当售票机中有5c=>1, 20c=>3, 50c=>1, 100c($1) => 1，需要找160c，这个时候也需要能正确找钱。

#说的简单点，就是有个函数，你提供要找的钱当参数，返回值就是找出来的钱（例如：一个数组）。

#所有的币值列表

@coins=( 100,50,20,10,5,2,1);
#每个币值对应的个数

@coinnums=( 1, 1, 2, 0,3,5,0);

#每个币值对应的个数

@paybackCoins=();
$paybackTotal=160;
if(payback($paybackTotal)==0){
    print join(",",@paybackCoins)."\n";
}else{
    print "payback $paybackTotal fail\n";
}

@coins=( 100,50,20,10,5,2,1);
@coinnums=( 0, 1, 3, 1,0,0,0);
@paybackCoins=();
$paybackTotal=60;
if(payback($paybackTotal)==0){
    print join(",",@paybackCoins)."\n";
}else{
    print "payback $paybackTotal fail\n";
}

@paybackCoins=();
$paybackTotal=55;
if(payback($paybackTotal)==0){
    print join(",",@paybackCoins)."\n";
}else{
    print "payback $paybackTotal fail\n";
}

sub payback{
    my $payback=shift;
    $coinslen=scalar(@coins);
    my $i=0;
    for($i=0;$i<$coinslen;$i++){
            if($coinnums[$i]>0){
                my $coin=$coins[$i];

#                每次都从最大币值开始循环

                if($payback >= $coin){
                    push(@paybackCoins,$coin);
                    $payback-=$coin;
                    $coinnums[$i]--;
                    if($payback<=0){
#                        剩下0时返回

                        return 0;
                    }
#                    继续找剩下的钱

                    if(payback($payback)!=0){
#                        剩下的钱找不完时，回滚

                        $rollbackCoin=pop(@paybackCoins);
                        $coinnums[$i]++;
                        $payback+=$rollbackCoin;
                    }else{
#                        剩下的钱找完时，返回

                        return 0;
                    }
                }
            }
        }
    return 1;
}