Python遞迴實現猴子吃桃問題及解析

Python遞迴實現猴子吃桃

猴子吃桃問題：猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以後每天早上都吃了前一天剩的一半零一個。到第10天早上想再吃時，見只剩下一個桃子了，求第一天共摘了多少桃子？

對於此性質的問題適合用遞迴的思想去解決，即當前問題可以轉化為性質相同的子問題去解決：

要想知道第一天的桃子數量，需要知道第二天的桃子數量，然後將第二天的桃子數量加1乘以2就可以得到第一天的桃子數量。按照此法進行倒推，我已知道第十天的桃子數量為1個，則第九天的桃子數量為第10天的桃子數量加1乘以2,第八天的桃子數量等於第九天的數量加1再乘以2,...

則可以定義函數去實現：n代表天數，如果輸入的n不合理，則直接退出函數，如果n等於10，則返回1，否則返回其後面天數桃子數量加1再乘以2

程式碼如下：

def monkey_tao(n):
    if n>10 or n<1:
        return
    elif n==10:
        return 1
    else:
        return (monkey_tao(n+1)+1)*2
print (monkey_tao(1))

Python函數（閏年&猴子偷桃)問題

函數

1. 函數簡介

• 函數也是一個物件
• 函數用來儲存一些可執行的程式碼，並且可以在需要時，對這些語句進行多次呼叫
• 語法：

def 函數名([形參1,形參2,形參3....]):
    程式碼塊

注意：

• 函數名必須符合識別符號的規範(可以包含字母、數位、下劃線但是不能以數位開頭)

print是函數物件 print()是呼叫函數

函數的引數

形參和實參

• 形參(形式引數) 定義形參就相當於在函數內部宣告了變數，但是並不是賦值
• 實參(實際引數)指定了形參，那麼在呼叫函數時必須傳遞實參，實參將會賦值給對應的形參，簡單來說有幾個形參就要有幾個實參

函數的傳遞方式

• 定義形參時,可以為形參指定預設值。指定了預設值以後，如果使用者傳遞了引數則預設值不會生效。如果使用者沒有傳遞，則預設值就會生效
• 位置引數：位置引數就是將對應位置的實參賦值給對應位置的形參
• 關鍵字引數 : 關鍵字引數可以不按照形參定義的順序去傳遞，而根據引數名進行傳遞
• 混合使用位置引數和關鍵字引數的時候必須將位置引數寫到關鍵字引數前面去

不定長引數

• 定義函數時，可以在形參前面加一個*,這樣這個形參可以獲取到所有的實參，它會將所有的實參儲存到一個元組中
• 帶*號的形參只能有一個，可以和其他引數配合使用
• *形參只能接受位置引數，不能接受關鍵字引數
• **形參可以接收其他的關鍵字引數,它會將這些引數統一儲存到字典當中。字典的key就是引數的名字,字典的value就是引數的值
• **形參只有一個，並且必須寫在所有引數的後面

引數的解包

• 傳遞實參時，也可以在序列型別的引數前新增星號，這樣它會自動的將序列中元素依次作為引數傳遞
• 要求序列中的元素的個數必須和形參的個數一致 函數中

1.函數的返回值

• 返回值就是函數執行以後返回的結果
• 通過return來指定函數的返回值
• return後面可以跟任意物件，返回值甚至可以是一個函數

2.檔案字串

• help()是Python中內建函數，通過help()函數可以查詢Python中函數的用法
• 在定義函數時，可以在函數內部編寫檔案字串，檔案字串就是對函數的說明

函數的作用域

• 作用域(scope)
• 作用域指的是變數生效的區域
• 在Python中一共有兩種作用域
• 全域性作用域

全域性作用域在程式執行時建立，在程式執行結束時銷燬

所有函數以外的區域都是全域性作用域

在全域性作用域中定義的變數，都是全域性變數，全域性變數可以在程式的任意位置進行存取

函數作用域

• 函數作用域在函數呼叫時建立，在呼叫結束時銷燬
• 函數每呼叫一次就會產生一個新的函數作用域
• 在函數作用域中定義的變數，都是區域性變數，它只能在函數內部被存取

名稱空間

• 名稱空間實際上就是一個字典，是一個專門用來儲存變數的字典
• locals()用來獲取當前作用域的名稱空間
• 如果在全域性作用域中呼叫locals()則獲取全域性名稱空間，如果在函數作用域中呼叫locals()則獲取函數名稱空間
• 返回值是一個字典

遞迴函數

• 遞迴是解決問題的一種方式，它的整體思想，是將一個大問題分解為一個個的小問題，直到問題無法分解時，在去解決問題
• 遞迴式函數有2個條件

基線條件 問題可以被分解為最小問題，當滿足基線條件時，遞迴就不執行了

遞迴條件 可以將問題繼續分解的條件

作業

閏年

用函數實現一個判斷使用者輸入的年份是否是閏年的程式

• 能被400整除的年份
• 能被4整除，但是不能被100整除的年份

以上2種方法滿足一種即為閏年

def leap_year():
    i = int(input('請輸入一個年份：'))
    if i%400 == 0 or (i%4 == 0 and i%100 != 0):
        print('此年分是閏年')
    else:
        print('次年分不是閏年')
leap_year()

執行結果：

猴子吃桃問題（遞迴）

猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以後每天早上都吃了前一天剩的一半零一個。到第10天早上想再吃時，見只剩下一個桃子了，求第一天共摘了多少桃子？

def hou_tao(i, x):       # i為天數  x為剩餘桃子數
    if i == 1:
        return x
    else:
        return (hou_tao(i-1, x) + 1)*2
print(f'第一天共摘{hou_tao(10, 1)}個桃子')

執行結果：

以上為個人經驗，希望能給大家一個參考，也希望大家多多支援it145.com。