算法—程序的靈魂

1、11/14/2021課件1第第2 2章章 程序的靈魂程序的靈魂-算法算法2第第2章章 程序的靈魂程序的靈魂-算法算法2-1 算法的概念算法的概念（理解）（理解）2-2 簡單算法舉例簡單算法舉例（理解）（理解）2-3 算法的特性算法的特性（理解）（理解）2-4 怎樣表示一個算法怎樣表示一個算法(熟練掌握熟練掌握)2-5 結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法（了解）（了解）3第第2章章 程序的靈魂程序的靈魂-算法算法l 本章要點本章要點4一個程序應(yīng)包括兩個方面的內(nèi)容: 對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure) 對操作的描述：算法(algorithm)著名計算機科學(xué)家沃思提出一個公式著

2、名計算機科學(xué)家沃思提出一個公式: 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法 = 程序程序數(shù)據(jù)結(jié)構(gòu)算法結(jié)構(gòu)化程序設(shè)計方法語言工具數(shù)據(jù)結(jié)構(gòu)算法結(jié)構(gòu)化程序設(shè)計方法語言工具完整的程序設(shè)計應(yīng)該是:2-1 算法算法52-1 算法算法 定義定義：算法是指為解決一個問題而采取的方法和步驟。：算法是指為解決一個問題而采取的方法和步驟。 分類：數(shù)值運算算法和非數(shù)值運算算法分類：數(shù)值運算算法和非數(shù)值運算算法 算法有優(yōu)劣算法有優(yōu)劣 為了有效地進行解題，不僅需要保證算法正確，為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡單，運算步驟少。單，運

3、算步驟少。62-2 簡單算法舉例簡單算法舉例 例例1-1 計算任意長方形的面積計算任意長方形的面積 例例1-2 計算計算 1x2x3x4x5=？ 例例1-3 計算計算1-1/2+1/3-.+1/99-1/100=？ 例例1-4 判斷一個數(shù)是否素數(shù)判斷一個數(shù)是否素數(shù)算法描述算法描述7計算任意長方形的面積計算任意長方形的面積 問題分析：問題分析：輸入長和寬輸入長和寬計算面積計算面積=長長x寬寬輸出面積輸出面積 數(shù)據(jù)存放：數(shù)據(jù)存放：長長-len，寬，寬-wid，面積，面積-area 設(shè)計算法：設(shè)計算法：輸入輸入len和和wid的值；的值；計算計算area =lenwid；輸出面積輸出面積area的值

4、；的值；8求求12345=？步驟步驟1 1：先求：先求1 12 2，得到結(jié)果，得到結(jié)果2 2步驟步驟2 2：將步驟：將步驟1 1得到的乘積得到的乘積2 2再乘以再乘以3 3，得到結(jié)果，得到結(jié)果6 6步驟步驟3 3：將：將6 6再乘以再乘以4 4，得，得2424步驟步驟4 4：將：將2424再乘以再乘以5 5，得，得120120如果要求如果要求1 12 210001000，則要寫，則要寫999999個步驟個步驟9 s1：使：使p=1 s2：使：使i=2 s3：使：使pi，乘積仍放在變量，乘積仍放在變量p中，可表示為：中，可表示為：pi=p s4：使：使i的值加的值加1，即，即i+1 = i。 s

5、5：如果：如果i5，返回步驟，返回步驟s3；否則，算法結(jié)束。；否則，算法結(jié)束。最后得到最后得到p的值就是的值就是5!的值。的值。可以設(shè)兩個變量：一個變量代表被乘數(shù)，一個變量代表乘一個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)積放在被乘數(shù)變量中。設(shè)p p為被乘數(shù)，為被乘數(shù)，i i為乘數(shù)。用循環(huán)為乘數(shù)。用循環(huán)算法來求結(jié)果算法來求結(jié)果, , 算法可改寫：算法可改寫： 10s1：1 = ps2：3 = is3：pi = ps4：i+2 = is5：若：若i1001，返回，返回s3。否則，結(jié)束。否則

6、，結(jié)束。 如果題目改為：求如果題目改為：求1 13 35 510011001算法只需作算法只需作很少的改動：很少的改動：111-1/2+1/3-.+1/99-1/100=？ 提示：提示：首先考慮實現(xiàn)首先考慮實現(xiàn)1+2+3+4+100其次考慮實現(xiàn)其次考慮實現(xiàn)1/1+1/2+1/3+1/4+.+1/100最后考慮實現(xiàn)最后考慮實現(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)則轉(zhuǎn) s2 ，否則轉(zhuǎn)，否則轉(zhuǎn) s5s5：打?。捍蛴um的值的值1/ i,p=1p*1/i,p=-p;12判斷一個數(shù)

7、是否素數(shù)判斷一個數(shù)是否素數(shù)分析：分析：本題要點是先搞清楚什么是素數(shù)。本題要點是先搞清楚什么是素數(shù)。思路：思路：輸入一個大于輸入一個大于3的正整數(shù)的正整數(shù)n定義一個變量定義一個變量 i 從從 2n-1 ，i 每取一個值做：每取一個值做：如果如果n能被能被i整除則中斷循環(huán)，整除則中斷循環(huán)，n不是素數(shù)；否則不是素數(shù)；否則 i繼續(xù)取下一個值；繼續(xù)取下一個值；若當若當i取完所有值都不能整除取完所有值都不能整除n，則，則n是素數(shù)是素數(shù)一個正整數(shù)，若不能被除一個正整數(shù)，若不能被除1和它本身以外的任何和它本身以外的任何整數(shù)整除，則是素數(shù)。整數(shù)整除，則是素數(shù)。132.3 算法的特性算法的特性142.4 怎樣表示

8、一個算法怎樣表示一個算法。15 結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法16 ：使用語言給計算機的一組指令序列。：使用語言給計算機的一組指令序列。 結(jié)構(gòu)化程序結(jié)構(gòu)化程序：用三種基本結(jié)構(gòu)組成的程序就是結(jié)構(gòu)化程序。：用三種基本結(jié)構(gòu)組成的程序就是結(jié)構(gòu)化程序。 ：為求解特定問題而編寫的正確有效的程序。：為求解特定問題而編寫的正確有效的程序。 ：編寫程序所用的語言。：編寫程序所用的語言。結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法171 1、順序結(jié)構(gòu)、順序結(jié)構(gòu) 例如：例如：a=3; b=4; c=a+b;操作的步驟按照書寫的順序執(zhí)行操作的步驟按照書寫的順序執(zhí)行ab結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)

9、三、三種基本結(jié)構(gòu)182 2、選擇結(jié)構(gòu)、選擇結(jié)構(gòu) 例如：例如：if(x!=0) y=sin(x)/x; else y=1;pabyn結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)三、三種基本結(jié)構(gòu)193、循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu): :根據(jù)條件根據(jù)條件p p決定是否重復(fù)執(zhí)行循環(huán)體中的操作決定是否重復(fù)執(zhí)行循環(huán)體中的操作 例如：例如：sum=0； i=1; while (i=100) sum+=i; i+; 先判斷后執(zhí)行先判斷后執(zhí)行napy結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)三、三種基本結(jié)構(gòu)20例如：例如：sum=0； i=1; do sum+=i; i+; while (i=100)pn

10、ay結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法三、三種基本結(jié)構(gòu)三、三種基本結(jié)構(gòu)21結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法22at p f a b當p1成立 a a直到直到p2成立成立 處理處理 判斷判斷 循環(huán)循環(huán)23n-s圖：圖：ababpabyny p n a b24n-s圖：圖：當p1成立 aap1y apyann252627例題：計算例題：計算s=n，寫出其算法寫出其算法 s=0,n=1n=100輸出輸出sn開始開始結(jié)束結(jié)束s=s+nn=n+1y100n=1流程圖描述：流程圖描述：自然語言描述：自然語言描述：1、0 s單元單元 2、1 n單元單元3、s+n s4、n+1 n5、判斷、判斷n100？是，轉(zhuǎn)是，轉(zhuǎn)3；否則轉(zhuǎn)；否則轉(zhuǎn)66、 輸出輸出 s的值的值 28例題：計算例題：計算s=n，寫出其算法寫出其算法 100n=1偽代碼描述：偽代碼描述：ns圖描述：圖描述：n100？s+n sn+1 n輸出s的值0 s1 nbegin 1 s2 nwhile n 100s+n s n+1 nprint send292.5 結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法核心思想：自頂向下，逐步細化，模塊化設(shè)計，結(jié)核心思想：自頂向下，逐步細化，模塊化設(shè)計，結(jié) 構(gòu)化編碼。構(gòu)