题目：投币自动售票程序
要求: 找钱原则“有大面值的货币就不找小面试的货币”
例如：当售票机中有10c=>1,20c=>3,50c=>1。需要找60c，这个时候就要找1个50c的和1个10c的硬币，而不是3个20c的硬币。
再比如，当售票机中有5c=>1,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,?50c=>1,?100c($1)?=>?1，需要找160c，这个时候也需要能正确找钱。 ?
- ?
- #说的简单点，就是有个函数，你提供要找的钱当参数，返回值就是找出来的钱（例如：一个数组）。 ?
- ?
- #所有的币值列表 ?
- ?
- @coins=(?100,50,20,10,5,2,1); ?
- #每个币值对应的个数 ?
- ?
- @coinnums=(?1,?1,?2,?0,3,0); ?
- ?
- #每个币值对应的个数 ?
- ?
- @paybackCoins=(); ?
- $paybackTotal=160; ?
- if(payback($paybackTotal)==0){ ?
-
????print?join(",",@paybackCoins)."n"; ?
-
}else{ ?
-
????print?"payback?$paybackTotal?failn"; ?
- } ?
- ?
- @coins=(?100,1); ?
- @coinnums=(?0,?3,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; ?
- }?
