本節書摘來自華章計算機《從問題到程式:用python學程式設計和計算》一書中的第3章,練習,作者 裘宗燕,更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
1. 複習下面概念:數值積分,區間分割法,舍入誤差,簡單重複,累積,累積變量,生成和篩選,遞推,遞推變量,素數(質數),因子和真因子,哥德巴赫猜想,輸入循環,輸入控制的循環,遞歸定義,遞歸函數,循環定義,無窮遞歸,循環和遞歸,斐波那契數列,二路遞歸,計時,循環不變式,計算複雜性,最大公約數,歐幾裡得算法(輾轉相除法),河内塔問題,自遞歸,互相遞歸,程式終止性,不可判定,collatz猜想,唯一定義原則,自下而上,自頂向下,逐漸求精,形式參數(形參),文檔串,實際參數(實參),類型錯誤,全函數,參數檢查,斷言語句,通用和專用的方法,枚舉和檢查,二分法,絕對誤差,相對誤差。
2. 請分析3.1.2節中定義的函數mysin的執行,為什麼它對越大的實參誤差越大?請考慮用python做一些試驗,分析并總結試驗中看到的情況。
3. 請證明如果一個自然數有真因子,一定有小于其平方的真因子。
4. 請分析3.2.2節改進的乘幂函數,設法弄清它對一般的自然數n計算power(x, n) 時要做多少次乘法和加法。
5. 請設法論證3.2.2節改進的乘幂函數對任何非負整數乘幂參數都能終止。
6. 請在你計算機上試驗遞歸的fib函數,看看算到第幾個斐波那契數時,計算的時間就超過了10秒鐘,半分鐘和一分鐘。
7. 請設法論證3.2.4節最後用for結構描述的fib函數的正确性。
8. 請設法說明3.2.5節中常用輾轉相除法定義的函數一定能求出最大公約數。
9. 請證明對河内塔問題,搬移n個圓盤時正好調用moveone函數2n - 1次。
10. 對一些n值試驗河内塔程式,給它們計時。據此估計你所用計算機搬完64個金盤需要的時間。再去掉程式執行中的輸出(例如把moveone的體改為一個return語句)後重新試驗。如果僧侶們1秒鐘搬金盤1次,搬完64個金盤需要多少時間?将這一時間與科學家對宇宙從大爆炸至今的估計壽命比較,據此評價僧侶們的說法。