資源簡介

第4單元 計算與問題解決
4.l算法及其特征
1、算法的重要特征
有窮性。算法必須能在執行有限個步驟之后終止。
確切性。算法中的每一次運算都有明確的定義，具有無二義性，并且可以通過計算得到唯一的結果。
輸人項。一個算法有0個或多個輸人，以刻畫運算對象的初始情況，所謂0個輸人是指算法本身給出了初始條件。
輸出項。算法一定要有輸出。任何算法都不能“無功而返”可行性。算法中執行的任何計算都可以在有限時間內完成(也稱為有效性)。算法中的運算都必須是可以實現的。
從某種意義上說，算法也是一種數學模型。一般而言，問題求解的第一步是數學建模。用數學語言描述實際現象，將現實世界的問題抽象成數學模型，就可能發現問題的本質并判定其能否求解，繼而找到求解該問題的方法和算法。
2、枚舉
我們常利用計算機運算速度快、精確度高的特點解決實際問題。在設計算法時，最簡單的方法就是“直譯”我們的思維過程。有一種算法是把所有可能的答案一一列舉，合適就保留，不合適就丟棄。這種方法稱作“枚舉”或“窮舉”
4.2 數值計算
1、numpy模塊簡介
numpy是一個科學計算包，其中包含很多數學函數，如三角函數、矩陣計算方法等。通過該模塊中的arange函數可以創建一個等差數列。如在0~2π之間每隔0.01取個值，則可以用arange(0,2* numpy.pi,0.01)來表示，其中numpy.pi表示π。下列代碼可以產生sin(x)的若干個關鍵點
2、matplotlib模塊簡介
matplotlib模塊是Python中最出色的繪圖庫，功能很完善。調用 matplotlib.pyplot時，坐標系可以根據數值范圍自動生成。
matplotlib的繪圖原理很簡單，利用plot畫線函數就可以在直角平面 內輕松地將(x, y)坐標點對連接成平滑曲線。例如:在上述代碼的適當位置增加下列語句，就可以將剛才生成的關鍵點連接起來。
參考上述代碼，讓我們一起來完善以下Python程序，嘗試繪出“sin(x)”“sin(-x)”和“sin(2x)/2”的圖像。
斐波那契在《計算之書》中提出了一個有趣的兔子問題:假設一對兔子每個月可以生一對小兔子，一對兔子出生后第2個月就開始生 小兔子。則一對兔子一年內能繁殖成多少對 10年呢
第1個月和第2個月的兔子對數之和為第3個月的兔子對數，第2個月和第3個月的兔子對數之和為第4個月的兔子對數...，每個月的兔子對數是前兩個月的兔子對數之和，又同時作為下一個月兔子對數的加數。這種重復反饋的過程稱為迭代。
迭代法也稱輾轉法，是用計算機解決問題的一種基本方法。迭代通常是為了接近并到達所需的目標或結果。每一次對過程的重復被稱為一次“迭代”，而每一次迭代得到的結果會被用來作為下一次迭代的初始值。
由于在迭代系列中的每個月份兔子對數只跟前兩個月有關，因此在編寫程序時，只需兩個變量f1和f2分別記錄上上月和上月的數據。
“f1,f2=f2,f1+f2”中右邊的值全是這個式子計算以前的初始值，可折為下面代碼
利用迭代算法解決問題，有三個關鍵步驟: (1)確定迭代變量, 如上例中的的f1、f2; (2) 建立迭代關系式；(3)對迭代過程進行控制，這是編寫迭代程序必須考慮的問題，不能讓迭代過程無休止地重復執行下去。
現代自然科學和工程電子技術的研究過程中，都離不開大規模的數學計算問題。例如:數學類課程中的線性方程求解、微分方程求解、概率統計等，實用性和實驗性技術應用中的模擬核試驗、油田開發、飛機設計等。
4.3 非數值計算
1、分治策略
分治的設計思想，是將一個難以直接解決的大問題，分割成一些較小的同類問題，各個擊破，最終達到解決問題的目的。二分查找實際上就是分治策略的一種典型運用。
2、二分查找.
二分查找又叫折半查找，該方法主要將數列有序排列，采用跳躍式的方式查找數據。以遞增數列為例，先以中點位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。每一次比較后都可以將查找區間縮小一半。
二分查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。在一個有n個元素的有序序列中，利用二分查找大約需要次。但是，二分法查找的前提條件是被查找的數據必須是有序的。
例程：假設一本字典大約1000頁，目標信息在第328頁。翻頁過程，看誰翻的次數最少。
在翻頁過程中借助兩個書簽，劃定目標所屬范圍，然后翻到兩個書簽的中間位置。每次目標區域都更新為原來的“二分之一”，當數據范圍縮小到只有1個數的時候肯定能得到問題的解。1000以內的頁碼，最多翻10次肯定能找到解。
2、遞歸
遞歸是計算科學領域中一種重要的計算思維模式。它既是一種抽象表達的手段，也是一種問題求解的重要方法。
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。圖4.3.3所示就是遞歸的一種形象表示。
在數學與計算機領域中，遞歸函數是指用函數自身來定義該函數的方法。如著名的斐波那契數列“1，1, 2，3, 5，8，13, ..”，可以遞歸定義為
遞推關系是遞歸的重要組成，而邊界條件是遞歸的另一要素，它保證遞歸能在有限次的計算后得出結果，而不會產生無限循環的情況。
面對一個大規模復雜問題的求解，遞歸的基本思想是把規模較大的 問題層層轉化為規模較小的同類問題求解。對遞歸而言，遞推與回歸, 二者缺一不可。結合分治策略，遞歸也可用“分”“治”“合”三個字 概括。
(1)分:將原問題分解成k個子問題。
(2)治:對這k個子問題分別求解。如果子問題的規模仍然不夠小，則將其再分解為k個子問題，如此進行下去，直到問題足夠小時，就很容易求出子問題的解。
(3)合:將求出的小規模問題的解合并為一個更大規模問題的解自下而上涿步求出原問題的解，
移動3個木盤的方法是:根據木盤疊放規則，要使A桿上最大的木盤(記為x)移動到C桿上(子問題1，如圖4.3.2中的第4步)，必須先把 x上方的所有木盤移動到B桿上(子問題2,如圖4.3.2中的前3步)，然后再將B桿上所有的木盤移動到C桿上(子問題3,如圖4.3.2中的后3步)。
3個木盤的移動問題成功解決了，就可以解決更多木盤的移動問題了。
將n個木盤從A桿移動到C桿，需要借助中間的B桿。只要超過一個木盤，在移動過程中，總會存在起始桿、過渡桿及目標桿的問題。因此，定義函數時，用到了4個參數: hanoi(n,s,m,t), n表示需要移動的盤子數量，s表示盤子的起始桿，m表示中間過渡桿，t表示目標桿，如圖4.3.4所示。
用遞歸求斐波那契數列
將一個難以直接解決的大問題，分割成一些規模較小的同類問題，以便各個擊破，分而治之，此為分治。分治與遞歸就像一對孿生兄弟，經常同時應用在算法設計中，并由此產生了許多高效的算法。
4.4綜合問題的解決
在解決一個綜合問題時，我們通常先考慮總體，后考慮細節；先面向整體，再細化局部。面對軟件開發這類綜合問題時，需要立足對象間的相互聯系，強調便捷的人機交互模式，盡量向需求靠攏。
1、pygame模塊
pygame是一個專門用來開發游戲的模塊，可以包含圖像、聲音等。pygame相關內容如表4.4.1所示。
pygame是專為游戲設計的，自帶了一個監聽類循環，不斷檢查用戶的操作，比如用戶按鍵、移動鼠標或者關閉窗口等。這個循環會在程序運行運行期間持續工作。其代碼框架如下
需求分析之后、程序設計之前，需要對系統進行總體設計和詳細設計。總體設計就是在需求分析的基礎上對模型細化、分解任務，明確程序由哪些模塊組成。概括地說，就是系統應該如何實現。詳細設計主要指界面設計、過程設計等。

展開更多......

收起↑