[課後作業] 第023、024講：遞歸：這幫小兔崽子、漢諾塔|課後測試題及答案

[課後作業] 第023、024講：遞歸：這幫小兔崽子、漢諾塔|課後測試題及答案

《零基礎入門學習Python》視頻下載地址：傳送門

動動手：

0.使用遞歸編寫一個十進制轉換為二進制的函數（要求採用“取2取餘”的方式，結果與調用bin()一樣返回字符串形式）。


1.寫一個函數get_digits(n)，將參數n分解出每個位的數字並按順序存放到列表中。舉例：get_digits(12345) ==> [1, 2, 3, 4, 5]


2.還記得求回文字符串那道題嗎？現在讓你使用遞歸的方式來求解，親還能驕傲的說我可以嗎？


3.使用遞歸編程求解以下問題：

有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最後問第一個人，他說是10歲。請問第五個人多大？

4.請寫下這一節課你學習到的內容：格式不限，回憶並複述是加強記憶的好方式！

回复您的答案即可查看參考答案！

      
動動手答案：

本帖隱藏的內容

0.使用遞歸編寫一個十進制轉換為二進制的函數（要求採用“取2取餘”的方式，結果與調用bin()一樣返回字符串形式）。

參考代碼：

1. def Dec2Bin(dec):
2.     result = ''
3.    
4.     if dec:
5.         result = Dec2Bin(dec//2)
6.         return result + str(dec%2)
7.     else:
8.         return result
9. 
   
10. print(Dec2Bin(62))

複製代碼

1.寫一個函數get_digits(n)，將參數n分解出每個位的數字並按順序存放到列表中。                          舉例：get_digits(12345) ==> [1, 2, 3, 4, 5]

解題思路：利用除以10取餘數的方式，每次調用get_digits(n//10)，並將餘數存放到列表中即可。要注意的是結束條件設置正確。
   
參考代碼：

1. result = []
2. def get_digits(n):
3.         if n > 0:
4.                 result.insert(0, n%10)
5.                 get_digits(n//10)
6. 
   
7. get_digits(12345)
8. print(result)

複製代碼

2.還記得求回文字符串那道題嗎？現在讓你使用遞歸的方式來求解，親還能傲嬌的說我可以嗎？

解題思路：有好多種方法，不過綜合效率來說，小甲魚的實現方式比較樸素，利用遞歸每次索引前後兩個字符進行對比，當start > end的時候，也正是首尾下標“碰面”的時候，即作為結束遞歸的條件。

參考代碼：

1. def is_palindrome(n, start, end):
2.         if start > end:
3.                 return 1     
4.         else:
5.                 return is_palindrome(n, start+1, end-1) if n[start] == n[end] else 0
6.         
7. string = input('請輸入一串字符串：')
8. length = len(string)-1
9. 
   
10. if is_palindrome(string, 0, length):
11.         print('"%s"是回文字符串!' % string)
12. else:
13.         print('"%s"不是回文字符串!' % string)

複製代碼

3. 使用遞歸編程求解以下問題：

有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最後問第一個人，他說是10歲。請問第五個人多大？

解題思路：利用遞歸的方法，遞歸分為回推和遞推兩個階段。要想知道第五個人歲數，需知道第四人的歲數，依次類推，推到第一人（10歲），再往回推。

參考代碼：

1. def age(n):
2.     if n == 1:
3.         return 10
4.     else:
5.         return age(n-1) + 2
6.         
7. print('哈哈，我知道了，第五個人的年齡是%d 歲，啵啵脆！' % age(5))

複製代碼

4.請寫下這一節課你學習到的內容：格式不限，回憶並複述是加強記憶的好方式！

小甲魚希望你認真對待作業就像你希望小甲魚推出高質量視頻一樣渴望^_^

（1）斐波那契數列的遞歸實現：

1，1，2，3，5，8，13，21.....

我們可以用數學函數來定義：

分別用迭代和遞歸實現：

迭代

def fab(n):








 n1 = 1








 n2 = 1








 n3 = 1








 if n < 1:








  print("输入错误！")








  return -1








 while (n-2) > 0:








  n3 = n2 + n1








  n1 = n2








  n2 =n3








  n -= 1








 return n3

遞歸：

def fab(n):








    if n < 1:








        print('输入有误！')








        return -1








    elif n == 1 or n == 2:








        return 1








    else:








        return ferber(n-1)+ferber(n-2)

遞歸算法稱為分治思想。

（2）遞歸實現漢諾塔

對於遊戲的玩法，我們可以簡單分解為三個步驟：

• 將前63個盤子從a移到b上
• 將最底下的第64個盤子從a移到c
• 將b上的63個盤子移到c

問題1：將a上的63個盤子借助c移到b

問題2：將b上的63個盤子借助a移到c

然後：

問題1拆解為：

•         將前62個盤子從a移到c上
•         將最底下的第63個盤子從a移到b
•         將c上的62個盤子移到b

問題2拆解為：

•         將前62個盤子從b移到a上
•         將最底下的第63個盤子從b移到c
•         將a上的62個盤子移到b