假如有這么一個(gè)問(wèn)題，1瓶汽水1塊錢(qián)，2個(gè)空瓶可以?xún)稉Q一瓶汽水舷蒲，問(wèn)n塊錢(qián)可以?xún)稉Q多少瓶汽水？
考慮整個(gè)過(guò)程就是用空瓶不斷兌換汽水的過(guò)程捌归。又因?yàn)榭掌啃∮?個(gè)的時(shí)候就不能兌換汽水了，考慮將當(dāng)前瓶數(shù)n可以分為n-1和1，同樣將n-1分為n-2和1，依次類(lèi)推诈豌。因此要想求得瓶數(shù)為n的時(shí)候可以?xún)稉Q的汽水?dāng)?shù)，我們只需求得1個(gè)空瓶?jī)稉Q的基本情況抒和，再依次回溯，最終求得瓶數(shù)為n時(shí)的情況彤蔽。所以采用遞歸的解法摧莽，
在每一個(gè)棧幀中，都是求當(dāng)前空瓶數(shù)能兌換的汽水?dāng)?shù)顿痪，傳入的參數(shù)為空瓶數(shù)镊辕，則可以?xún)稉Q的汽水?dāng)?shù)為空瓶數(shù)對(duì)2求商，而遞推傳入下一個(gè)棧幀的參數(shù)值為兌換的汽水?dāng)?shù)（即空瓶數(shù)）加上余數(shù)（不能兌換的數(shù)量）蚁袭。在遞推到基礎(chǔ)問(wèn)題時(shí)征懈，回溯返回給上一層調(diào)用函數(shù)。
其python實(shí)現(xiàn)代碼為
def bottlechange(n):
??? drinknum=n//2??????????? ?????????#空瓶?jī)稉Q汽水?dāng)?shù)揩悄，同時(shí)也是當(dāng)下對(duì)應(yīng)的空瓶數(shù)
???totalemptybottle=drinknum+n%2?????#空瓶總數(shù)
???
??? if totalemptybottle<2:???? ????????#基礎(chǔ)條件
??????? return drinknum
???
return drinknum+bottlechange(totalemptybottle)???????????????????????????
?
def buy(money):
??? num =money+bottlechange(money)? ???????#遞歸空瓶可以?xún)稉Q的汽水瓶數(shù)卖哎，初始空瓶數(shù)為money個(gè)
??? return num
或
def bottlechange(n):
??? if n<2:???????????? #基礎(chǔ)條件
??????? return 0
??? drinknum=n//2???????????????????? #空瓶?jī)稉Q汽水?dāng)?shù)，同時(shí)也是當(dāng)下對(duì)應(yīng)的空瓶數(shù)
???totalemptybottle=drinknum+n%2?????#空瓶總數(shù)
???
??? returndrinknum+bottlechange(totalemptybottle)
用空瓶個(gè)數(shù)作為參數(shù)進(jìn)行遞歸時(shí)删性，當(dāng)空瓶小于2個(gè)的時(shí)候亏娜，就應(yīng)該停止迭代了，直接返回此時(shí)的兌換數(shù)蹬挺。
測(cè)試用例
>>> buy(15)
29
>>> buy(2)
3
>>> buy(1)
1
再比如買(mǎi)汽水的規(guī)則维贺，1塊錢(qián)可以買(mǎi)1瓶汽水，2個(gè)空瓶可以換一瓶汽水巴帮，3個(gè)瓶蓋可以換一瓶汽水溯泣，問(wèn)：20塊可以買(mǎi)到多少瓶汽水？
分析：該問(wèn)題的一個(gè)求解過(guò)程實(shí)際上就是用空瓶和瓶蓋不斷去兌換汽水的過(guò)程榕茧。這個(gè)過(guò)程有明顯的遞歸性垃沦，可以使用遞歸的方法求解。它的出口條件是空瓶總數(shù)小于2且瓶蓋總數(shù)小于3雪猪，因?yàn)檫@個(gè)條件下是無(wú)法兌換汽水的栏尚。
def bottlecapchange(bottle=0,cap=0):
??? drinknum=bottle // 2+cap // 3 #空瓶和瓶蓋兌換汽水瓶數(shù)
???totalemptybottle=drinknum+bottle % 2?????#空瓶總數(shù)
??? totalcap=drinknum+cap % 3????????????? #瓶蓋總數(shù)
???
??? if totalemptybottle < 2 andtotalcap <3 :
??????? return drinknum
??? else:
??????? return drinknum+bottlecapchange(bottle=totalemptybottle,cap=totalcap)
???????
def buy(money):
??? num =money+bottlecapchange(money,money)? #遞歸空瓶、瓶蓋可以?xún)稉Q的汽水瓶數(shù)
??? return num
每次迭代過(guò)程中需要先算出當(dāng)前可用的瓶蓋和空瓶數(shù)。
測(cè)試用例
>>> buy(2)
5
>>> buy(1)
1
