本文教大家用perl来实现一个投币自动售票程序，供大家学习参考。
题目：投币自动售票程序
要求: 找钱原则“有大面值的货币就不找小面试的货币”
例如：当售票机中有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 failn";
}
@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 failn";
}
@paybackCoins=();
$paybackTotal=55;
if(payback($paybackTotal)==0){
print join(",",@paybackCoins)."n";
}else{
print "payback $paybackTotal failn";
}
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;
}