算法-程序的靈魂課件

1、2022/7/28課件1第2章 程序的靈魂-算法2第2章 程序的靈魂-算法2-1 算法的概念（理解）2-2 簡單算法舉例（理解）2-3 算法的特性（理解）2-4 怎樣表示一個算法(熟練掌握)2-5 結(jié)構(gòu)化程序設(shè)計方法（了解）3第2章 程序的靈魂-算法 本章要點算法的概念 算法的表示結(jié)構(gòu)化程序設(shè)計方法 4一個程序應包括兩個方面的內(nèi)容:對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure)對操作的描述：算法(algorithm)著名計算機科學家沃思提出一個公式: 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序 數(shù)據(jù)結(jié)構(gòu)算法結(jié)構(gòu)化程序設(shè)計方法語言工具完整的程序設(shè)計應該是:2-1 算法52-1 算法定義：算法是指為解決

2、一個問題而采取的方法和步驟。分類：數(shù)值運算算法和非數(shù)值運算算法算法有優(yōu)劣 為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡單，運算步驟少。62-2 簡單算法舉例例1-1 計算任意長方形的面積例1-2 計算 1x2x3x4x5=？例1-3 計算1-1/2+1/3-.+1/99-1/100=？例1-4 判斷一個數(shù)是否素數(shù)算法描述7計算任意長方形的面積問題分析：輸入長和寬計算面積=長X寬輸出面積數(shù)據(jù)存放：長-len，寬-wid，面積-area設(shè)計算法：輸入len和wid的值；計算area =lenwid；輸出面積area的值；8求12345=？步驟1：先求12

3、，得到結(jié)果2步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6步驟3：將6再乘以4，得24步驟4：將24再乘以5，得120太繁瑣如果要求121000，則要寫999個步驟9 S1：使p=1 S2：使i=2 S3：使pi，乘積仍放在變量p中，可表示為：pi=p S4：使i的值加1，即i+1 = i。 S5：如果i5，返回步驟S3；否則，算法結(jié)束。最后得到p的值就是5!的值。可以設(shè)兩個變量：一個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果, 算法可改寫： 10S1：1 = pS2：3 = iS3：pi =

4、pS4：i+2 = iS5：若i1001，返回S3。否則，結(jié)束。 如果題目改為：求1351001算法只需作很少的改動：算法簡練111-1/2+1/3-.+1/99-1/100=？提示：首先考慮實現(xiàn)1+2+3+4+100其次考慮實現(xiàn)1/1+1/2+1/3+1/4+.+1/100最后考慮實現(xiàn)1/1-1/2+1/3-1/4+.+1/100思路：S1：SUM=0,I=1S2：SUM=SUM+ IS3： I=I+1S4：如果I=100則轉(zhuǎn) S2 ，否則轉(zhuǎn) S5S5：打印SUM的值1/ I,P=1P*1/I,P=-P;12判斷一個數(shù)是否素數(shù)分析：本題要點是先搞清楚什么是素數(shù)。思路：輸入一個大于3的正整數(shù)N

5、定義一個變量 I 從 2N-1 ，I 每取一個值做：如果N能被I整除則中斷循環(huán)，N不是素數(shù)；否則 I繼續(xù)取下一個值；若當I取完所有值都不能整除N，則N是素數(shù)一個正整數(shù)，若不能被除1和它本身以外的任何整數(shù)整除，則是素數(shù)。132.3 算法的特性有窮性 指一個算法經(jīng)過有限步驟后停止（或在合理范圍內(nèi)）確定性 算法的每一步都應當是確定的，無歧義的有效性 算法的每一步計算機都能有效執(zhí)行有0個或多個輸入 一個算法可以沒有輸入，即執(zhí)行時無需輸入信息有1個或多個輸出 一個算法必須有輸出，運算過程或運算結(jié)果142.4 怎樣表示一個算法常用的算法描述方法：帶序號的自然語言描述，易懂卻不直觀，不嚴格。流程圖：靈活、自

6、由、形象、直觀，可表示任何算法。15一、結(jié)構(gòu)化程序設(shè)計的三種基本結(jié)構(gòu) 三種基本結(jié)構(gòu)：順序、選擇、循環(huán)，用這三種基本結(jié)構(gòu)作為表示一種良好算法的基本單元。結(jié)構(gòu)化程序設(shè)計方法16二、相關(guān)術(shù)語 程序：使用語言給計算機的一組指令序列。 結(jié)構(gòu)化程序：用三種基本結(jié)構(gòu)組成的程序就是結(jié)構(gòu)化程序。 程序設(shè)計：為求解特定問題而編寫的正確有效的程序。 程序設(shè)計語言：編寫程序所用的語言。結(jié)構(gòu)化程序設(shè)計方法171、順序結(jié)構(gòu) 例如：a=3; b=4; c=a+b;操作的步驟按照書寫的順序執(zhí)行AB結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)182、選擇結(jié)構(gòu) 例如：if(x!=0) y=sin(x)/x; else y=1;PABYN結(jié)

7、構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)193、循環(huán)結(jié)構(gòu):根據(jù)條件P決定是否重復執(zhí)行循環(huán)體中的操作 例如：sum=0； i=1; while (i=100) sum+=i; i+; 先判斷后執(zhí)行NAPY結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)20循環(huán)結(jié)構(gòu)例如：sum=0； i=1; do sum+=i; i+; while (i=100)先執(zhí)行后判斷PNAY結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)21結(jié)構(gòu)化程序設(shè)計方法二、三種基本結(jié)構(gòu)特點：只有一個入口和一個出口；結(jié)構(gòu)內(nèi)每一部分都有機會執(zhí)行到；結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。注：以上三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)可以解決任何復雜的問題。22常用的算法描述方法：N-S圖（盒

8、圖）：特點是完全去掉了帶箭頭的流程線，算法的所有處理步驟都寫在一個大矩形框，表示簡單，符合結(jié)構(gòu)化思想。AT P F A B當P1成立 A A直到P2成立 處理 判斷 循環(huán)23N-S圖：ABAB順序結(jié)構(gòu)PABYNY P N A B選擇結(jié)構(gòu)24N-S圖：當型循環(huán)直到型循環(huán)當P1成立 AAP1Y A直到P2成立PYANN25常用的算法描述方法：偽代碼：用介于自然語言與計算機語言之間的文字及符號來描述算法，特點是方便、易懂、便于向計算機語言過渡。26學習建議：流程圖和N-S圖一定要熟練掌握，偽代碼表示法在學習完基本的流程控制語句后也經(jīng)常使用。27例題：計算s=n，寫出其算法 S=0,n=1n=100輸出SN開始結(jié)束S=S+nn=n+1Y100n=1流程圖描述：自然語言描述：1、0 S單元 2、1 n單元3、s+n s4、n+1 n5、判斷n100？是，轉(zhuǎn)3；否則轉(zhuǎn)66、 輸出 S的值 28例題：計算s=n，寫出其算法 100n=1偽代碼描述：NS圖描述：n100？s+n sn+1 n輸出S的值0 s1 nBegin s nwhile n 100s+n s n+1 n