假如有这么一个问题，1瓶汽水1块钱，2个空瓶可以兑换一瓶汽水，问n块钱可以兑换多少瓶汽水？
考虑整个过程就是用空瓶不断兑换汽水的过程。又因为空瓶小于2个的时候就不能兑换汽水了，考虑将当前瓶数n可以分为n-1和1，同样将n-1分为n-2和1，依次类推。因此要想求得瓶数为n的时候可以兑换的汽水数，我们只需求得1个空瓶兑换的基本情况，再依次回溯，最终求得瓶数为n时的情况。所以采用递归的解法，
在每一个栈帧中，都是求当前空瓶数能兑换的汽水数，传入的参数为空瓶数，则可以兑换的汽水数为空瓶数对2求商，而递推传入下一个栈帧的参数值为兑换的汽水数（即空瓶数）加上余数（不能兑换的数量）。在递推到基础问题时，回溯返回给上一层调用函数。
其python实现代码为
def bottlechange(n):
drinknum=n//2 #空瓶兑换汽水数，同时也是当下对应的空瓶数
totalemptybottle=drinknum+n%2 #空瓶总数
if totalemptybottle<2: #基础条件
return drinknum
return drinknum+bottlechange(totalemptybottle)
def buy(money):
num =money+bottlechange(money) #递归空瓶可以兑换的汽水瓶数，初始空瓶数为money个
return num
或
def bottlechange(n):
if n<2: #基础条件
return 0
drinknum=n//2 #空瓶兑换汽水数，同时也是当下对应的空瓶数
totalemptybottle=drinknum+n%2 #空瓶总数
returndrinknum+bottlechange(totalemptybottle)
用空瓶个数作为参数进行递归时，当空瓶小于2个的时候，就应该停止迭代了，直接返回此时的兑换数。
测试用例
>>> buy(15)
29
>>> buy(2)
3
>>> buy(1)
1
再比如买汽水的规则，1块钱可以买1瓶汽水，2个空瓶可以换一瓶汽水，3个瓶盖可以换一瓶汽水，问：20块可以买到多少瓶汽水？
分析：该问题的一个求解过程实际上就是用空瓶和瓶盖不断去兑换汽水的过程。这个过程有明显的递归性，可以使用递归的方法求解。它的出口条件是空瓶总数小于2且瓶盖总数小于3，因为这个条件下是无法兑换汽水的。
def bottlecapchange(bottle=0,cap=0):
drinknum=bottle // 2+cap // 3 #空瓶和瓶盖兑换汽水瓶数
totalemptybottle=drinknum+bottle % 2 #空瓶总数
totalcap=drinknum+cap % 3 #瓶盖总数
if totalemptybottle < 2 andtotalcap <3 :
return drinknum
else:
return drinknum+bottlecapchange(bottle=totalemptybottle,cap=totalcap)
def buy(money):
num =money+bottlecapchange(money,money) #递归空瓶、瓶盖可以兑换的汽水瓶数
return num
每次迭代过程中需要先算出当前可用的瓶盖和空瓶数。
测试用例
>>> buy(2)
5
>>> buy(1)
1
网友评论