資源簡介

算法及其描述
學習目標
1.理解和概述算法的概念與特征;
2.運用恰當的描述方法和控制結構表示簡單算法。
學習內容
算法
算法是指在有限步驟內求解某一問題所使用的一 組定義明確的規則。通俗地說,算法就是用計算機求解某一問題的方法,是能被機械地執行的動作或指令的有窮集合。
例如,若要求方程6x+ 5y+ 4z= 50的正整數解的個數,則解決問題的算法步驟如下:
①t=0 ;
②x=1;
③y=1;
④z=1;
⑤如果滿足式子6x +5y+4z= 50 ,則解的個數加1(即t=t+1 ,示右邊式子的值賦值給左邊式子),并輸出這個解(即輸出t , x, y , z的值) ;
⑥z=Z+1 ;
⑦如果z≤12則轉步驟⑤,否則繼續步驟⑧;
⑧y=y+1 ;
⑨如果y≤10則轉步驟④,否則繼續步驟四;
◎x=x+1;
如果x≤8則轉步驟③,則繼續步驟;結束。
算法的特征
算法作為能確實解決某個問題的策略,具有五個方面的重要特征:
(1)有窮性。一個算法在執行有窮步之后必須結束,即一個算法所包含的計算步驟是有限的。例如，在上面的算法中, x的值從1開始窮舉,重復執行語句,直到x> 8時終止執行。
(2)確定性。算法執行的每一個步驟必須有 確切的定義,不能出現模棱兩可的情況。例如，上面算法步驟⑤就明確規定:當滿足式子6x+ 5y+4z= 50時,則解的個數加1(即t=t+1) ,并輸出這個解。
(3)數據輸入。一個算法必須有零個或多個數據輸入,以刻畫運算對象的初始情況。例如,在上面的算法中,就沒有數據輸入。
(4)數據輸出。一個算法有 一個或多個數據輸出,以反映對輸入數據加工后的結果,沒有輸出的算法是毫無意義的。例如，在上面的算法中,有兩個輸出,即步驟⑤的個數t和具體解(x, y , z的值)。
(5)可行性。算法中執行的任何計算步驟都可以被分解為基本的可執行的操作步驟,即每個計算步驟都可以在有限時間內完成。例如，上面的算法中每一步都是可以在有限時間內完成的。
算法的描述
算法是對解題過程的精確描述,且需要使用某種方法將其表示出來。
1.描述算法的常用方法
描述算法的常用方法有自然語言描述算法、流程圖描述算法和偽代碼描述算法。
(1)用自然語言描述算法。
用自然語言描述算法,就是用人們日常所用的語言, 如漢語、英語等來描述算法。例如,從A市
到B市耗時最少的旅行路線問題的算法描述,即使用了自然語言。
使用自然語言描述算法比較容易掌握,但也存在明顯的缺點。例如，當算法中含有多分支或循環操作較多時,使用自然語言很難將其清晰地表示出來;且由于自然語言的歧義性,也容易導致算法執行的不確定性。
(2)用流程圖描述算法
用流程圖捕述算法是用程序框圖來描述算法的一種表示方法。使用流程描述算法，可使算法的流程描述得清晰、簡潔。
例如,用流程圖描述求方程6x+ 5y+4z= 50的正整數解的算法。
(3)用偽代碼描述算法。
用偽代碼描述算法就是用介于自然語言和計算機語言之間的文字和符號來描述算法。它不圖形符號,瀉方便,格式緊湊,易于理解,便于向計算機程序設計語言過渡。
例如,用偽代碼描述求解方程6x+5y+4z= 50的算法如下:
在《幾何原本》一書中,歐幾里得闡述了關于求兩個正整數的最大公約數的過程,這就是著名的歐幾里得算法
輾轉相除法,具體過程如下:
設給定的兩個正整數為m和n ,求它們的最大公約數的步驟為:
①以m除以n ,令所得的余數為R。
②若R=0 ,則輸出結果n ,算法結束;否則,繼續步驟③。
③令m=n , n=R ,并返回步驟①繼續進行。
用流程圖將上述算法表示出來,試探索歐幾里得算法在現實生活中有哪些應用,舉出兩個應用實例。
2.三種基本控制結構
前面的算法描述中, 我們用到了順序結構,選擇結構和循環結構這三種基本控制結構,而任何復雜的算法都可以用這三種基本控制結構組合來表示。
這三種基本控制結構的主要作用是:
(1)順序結構表示程序中的各步操作按出現的先后順序執行。
(2)選擇結構表示程序的處理步驟出現了分支,需要根據某一特定的條件選擇其中的一個分支執行。選擇結構有單選擇、雙選擇和多選擇三種。
(3)循環結構表示程序反復執行某個或某些操作，直到判斷條件為假(或為真)時才可終止循環。使用三種基本控制結構的組合來描述算法,可以改善算法的清晰度,提高算法的可讀性,原因如
(1)以控制結構為單位,只有一一個入口和一個出口,各單位之間接口簡單,比較容易獨立地理解每一單位。
(2)縮小了算法的靜態描述與動態執行過程之間的差異,使得兩者容易對應,易于理解。
課內任務:將最大公約數代碼輸入,運行,觀察是否達到預期效果。

展開更多......

收起↑