[其它]lesson 7 計算機算法初步ppt課件

1、2022-5-9電氣與信息工程學院計算機系張吳波制作2022-5-9電氣與信息工程學院計算機系張吳波制作學習目的學習目的:3 1掌握幾個常用的解題算法：枚舉、迭代掌握幾個常用的解題算法：枚舉、迭代2022-5-9電氣與信息工程學院計算機系張吳波制作3窮舉法窮舉法2 概述概述l窮舉法，又稱為枚舉法，是人們日常生活中常用窮舉法，又稱為枚舉法，是人們日常生活中常用的一種求解問題的方法。的一種求解問題的方法。l根據問題中的部分條件的條件將所有可能解根據問題中的部分條件的條件將所有可能解的情況列舉出來，然后通過一一驗證是否符合整的情況列舉出來，然后通過一一驗證是否符合整個問題的求解要求，而得到問題的解。

2、個問題的求解要求，而得到問題的解。2022-5-9電氣與信息工程學院計算機系張吳波制作3窮舉法窮舉法21、旅行途中發(fā)現(xiàn)自己忘記了開鎖的密碼，怎么辦？2、從某個班中找出所有班干部，需要逐一對每個同學進展查看，判斷是否是班干部。2022-5-9電氣與信息工程學院計算機系張吳波制作3窮舉法窮舉法2 窮舉法的核心在于明確問題的所有可能性，并針對每種可能情況逐個進展判斷，最終找出正確問題的答案。 窮舉解題步驟：窮舉解題步驟：1、問題解的可能搜索的范圍：問題解的可能搜索的范圍： 用循環(huán)或循環(huán)嵌套構造實現(xiàn)用循環(huán)或循環(huán)嵌套構造實現(xiàn) 2、寫出符合問題解的條件。寫出符合問題解的條件。 2022-5-9電氣與信息工

3、程學院計算機系張吳波制作3窮舉法窮舉法2所謂素數(shù)是指僅能被所謂素數(shù)是指僅能被1和自身整除，且和自身整除，且大于等于大于等于2的數(shù)值。如的數(shù)值。如7，11，17，23等等例1：判斷給定整數(shù)是否是素數(shù) 。 2022-5-9電氣與信息工程學院計算機系張吳波制作3窮舉法窮舉法2 問題分析問題分析l為了檢查一個整數(shù)是不是素數(shù)，可以采用窮舉法。為了檢查一個整數(shù)是不是素數(shù)，可以采用窮舉法。假設給定的整數(shù)用假設給定的整數(shù)用x表示，那么判斷過程就是確表示，那么判斷過程就是確認認x不能整除以不能整除以2x-1之間的任何整數(shù)。這就需要之間的任何整數(shù)。這就需要一一列舉出一一列舉出2x-1之間的每個整數(shù)進展排查。之間的

4、每個整數(shù)進展排查。 2022-5-9電氣與信息工程學院計算機系張吳波制作 算法描繪 NY開始開始輸入輸入x2 tt xt 加加1x%t=0結束結束輸出輸出“不是素數(shù)不是素數(shù)”輸出輸出“是素數(shù)是素數(shù)”YNt = xYN2022-5-9電氣與信息工程學院計算機系張吳波制作#include int main int x, t;printf “Enter an integer: ;scanf “%d, &x ;for t = 2; tx; t+ /* 列舉小于列舉小于x大于大于1的所有整數(shù)的所有整數(shù) */ if x%t = 0 break;if t = x /* 是否通過循環(huán)條件出口是否通過循

5、環(huán)條件出口 */ printf “%d is primen, x ;else printf “%d isnt primen, x ; return 0;注意判斷是否是素數(shù)的條件與注意判斷是否是素數(shù)的條件與判斷位置判斷位置lesson8_01.c2022-5-9電氣與信息工程學院計算機系張吳波制作3窮舉法窮舉法2 例例2：百錢買百雞：百錢買百雞l “百錢買百雞是我國古代數(shù)學家張丘建提出的一個百錢買百雞是我國古代數(shù)學家張丘建提出的一個著名的數(shù)學問題。假設某人有錢百枚，希望買一百只著名的數(shù)學問題。假設某人有錢百枚，希望買一百只雞；不同的雞價格不同，公雞雞；不同的雞價格不同，公雞5枚錢一只，母雞枚錢一

6、只，母雞3枚錢枚錢一只，而小雞一只，而小雞3只只1枚錢。試問：假如用百枚錢買百只枚錢。試問：假如用百枚錢買百只雞，可以包含幾只公雞、幾只母雞和幾只小雞。雞，可以包含幾只公雞、幾只母雞和幾只小雞。 2022-5-9電氣與信息工程學院計算機系張吳波制作3窮舉法窮舉法2 問題分析問題分析l從題目要求可知：公雞、母雞和小雞的數(shù)量是有限從題目要求可知：公雞、母雞和小雞的數(shù)量是有限的，都不會超過的，都不會超過100100。通過對不同數(shù)量的公雞、母。通過對不同數(shù)量的公雞、母雞和小雞進展組合，可以計算出購置這些雞所用的雞和小雞進展組合，可以計算出購置這些雞所用的花費，但這個題目要求找出那些花費正好花費，但這個

7、題目要求找出那些花費正好100100枚且枚且雞的總數(shù)也為雞的總數(shù)也為100100只的情況。只的情況。l因此，可以采用窮舉法，將不同的公雞、母雞和小因此，可以采用窮舉法，將不同的公雞、母雞和小雞的數(shù)量枚舉一遍，找出那些符合題目要求的解。雞的數(shù)量枚舉一遍，找出那些符合題目要求的解。 2022-5-9電氣與信息工程學院計算機系張吳波制作 算法描繪 N Y 開開始始 條條件件判判斷斷 x 加加 1 結結束束 z=100 x = 100/5 y = 100/3 y 加加 1 z 加加 1 0 x 0 y 0 z 輸輸出出 x, y, z N Y Y N N Y 2022-5-9電氣與信息工程學院計算機系

8、張吳波制作#include #include int main int x, y, z; for x=0; x=100/5; x+ for y=0; y=100/3; y+ for z=0; z=100; z+ if x+y+z =100 &15*x+9*y+z=300 printf “x=%d, y=%d, z=%dn, x, y, z ; return 0;lesson8_02.c2022-5-9電氣與信息工程學院計算機系張吳波制作3課堂練習課堂練習3、求所有的三位水仙花數(shù)、求所有的三位水仙花數(shù)假設一個假設一個3位自然數(shù)的各位數(shù)字的位自然數(shù)的各位數(shù)字的3次方之次方之和等于它本身和等

9、于它本身,那么稱這個自然數(shù)為水仙花那么稱這個自然數(shù)為水仙花數(shù)。數(shù)。例如例如:153153=13+33+53是水仙花是水仙花數(shù)數(shù)2022-5-9電氣與信息工程學院計算機系張吳波制作3遞推與迭代法遞推與迭代法4 概述概述l遞推是計算機數(shù)值計算中的一個重要算法。其根本遞推是計算機數(shù)值計算中的一個重要算法。其根本策略是將復雜的運算劃分為可以重復操作的假設干策略是將復雜的運算劃分為可以重復操作的假設干個簡單的運算，進而充分利用計算機擅長重復計算個簡單的運算，進而充分利用計算機擅長重復計算的特點。的特點。l采用遞推法進展問題求解的關鍵在于找出遞推公式采用遞推法進展問題求解的關鍵在于找出遞推公式和邊界條件。

10、和邊界條件。2022-5-9電氣與信息工程學院計算機系張吳波制作3遞推與迭代法遞推與迭代法4 例例3 3：等比數(shù)列求和：等比數(shù)列求和 l等比數(shù)列是指在一組數(shù)據中，后項和前項之前存在著等比數(shù)列是指在一組數(shù)據中，后項和前項之前存在著一個固定的比例關系。例如：整數(shù)序列一個固定的比例關系。例如：整數(shù)序列3、15、75、375的初值是的初值是3，后項與前項是，后項與前項是5倍的關系，即前項乘以倍的關系，即前項乘以5得到后項。得到后項。l此題要求給定等比序列的首項和比例，計算這個數(shù)列此題要求給定等比序列的首項和比例，計算這個數(shù)列的前的前10項之和。項之和。2022-5-9電氣與信息工程學院計算機系張吳波制

11、作3遞推與迭代法遞推與迭代法4 問題分析問題分析l等比數(shù)列的遞推公式為：等比數(shù)列的遞推公式為： itemi= itemi-1 * ratio后項等于前項乘以比例值后項等于前項乘以比例值sumi= sumi-1 + itemi前前i i項之和等于前項之和等于前i-1i-1項之和加當前項項之和加當前項l由于在重復上述遞推計算之前，需要將第由于在重復上述遞推計算之前，需要將第1 1項的值累加到項的值累加到sumsum中，所以，需要先將中，所以，需要先將itemitem存入存入sumsum中。中。 2022-5-9電氣與信息工程學院計算機系張吳波制作 算法描繪 N Y 開開始始 輸輸入入 item,

12、ratio item sum 1 i i 10 item*ratio item 加加一一 sum+itemsum i 加加 1 結結束束 輸輸出出 sum 2022-5-9電氣與信息工程學院計算機系張吳波制作#include int main long item, ratio, sum,i;printf “nEnter the first item and ratio: ;scanf “%ld%ld, &item, &ratio ; sum=item;for i=1; i 10-4 (-1)i+ 14/(2i-1) item P I+ item P I i 加加 1 結結 束束

13、 輸輸 出出 P I 2022-5-9電氣與信息工程學院計算機系張吳波制作#include #include int main int sign = 1; long i = 1; double PI= 0.0, item;do item= sign * 4.0 / 2 * i-1;sign= -sign;PI+= item; i+; while fabs item 1e-4 ; /* 數(shù)據項精度控制循環(huán)數(shù)據項精度控制循環(huán) */ printf “PI = %lfn, PI ; return 0; lesson8_04.c2022-5-9電氣與信息工程學院計算機系張吳波制作3遞推與迭代法遞推與迭代

14、法4例5：按位分解整數(shù)。 問題分析問題分析l可以利用程序設計語言提供的整除和求余運算實現(xiàn)將整可以利用程序設計語言提供的整除和求余運算實現(xiàn)將整數(shù)分解的目的。數(shù)分解的目的。l例如，對于整數(shù)例如，對于整數(shù)7326，用，用7326/1000就得到了最高位就得到了最高位7，而而7326%1000得到了其余的位數(shù)得到了其余的位數(shù)326。但是，這種方法要。但是，這種方法要求首先獲得整數(shù)最高位的權，因此，算法應該先求整數(shù)求首先獲得整數(shù)最高位的權，因此，算法應該先求整數(shù)最高位的權，然后從高向低逐個別離出每位數(shù)字。最高位的權，然后從高向低逐個別離出每位數(shù)字。 2022-5-9電氣與信息工程學院計算機系張吳波制作

15、算法描繪 NY開始開始輸入輸入x計算整數(shù)最高位權計算整數(shù)最高位權nn = 1x/n的余數(shù)的余數(shù)xn/10 n結束結束打印打印x/n2022-5-9電氣與信息工程學院計算機系張吳波制作#include int main long x, y, n;printf “Enter an integer: ;scanf “%ld, &x ; y =x; n =1; while y10 n *= 10; y = y/10; do printf “%ldt, x / n ;x=x % n;n=n / 10; while n = 1 ; return 0; lesson8_05.c2022-5-9電氣與

16、信息工程學院計算機系張吳波制作3課堂練習課堂練習5求數(shù)列、求數(shù)列、8 8的前項的前項2022-5-9電氣與信息工程學院計算機系張吳波制作3標志變量法標志變量法6標志變量法的根本思想：標志變量法的根本思想：為了表示處理對象所處的狀態(tài)結果，使為了表示處理對象所處的狀態(tài)結果，使用一個變量，給其規(guī)定假設干個值，并且規(guī)用一個變量，給其規(guī)定假設干個值，并且規(guī)定每個值所表示的狀態(tài)意義，然后通過定每個值所表示的狀態(tài)意義，然后通過判斷變量的值來知道程序處理的結果判斷變量的值來知道程序處理的結果2022-5-9電氣與信息工程學院計算機系張吳波制作3標志變量法標志變量法6例例6：使用標志變量法判斷：使用標志變量法判

17、斷9是否是素數(shù)是否是素數(shù)flag:02 , 3 , 4 , 5 , 6 , 7 , 89能否被能否被2 整除整除9能否被能否被3 整除整除給給flag賦賦1：改：改變標志變量的變標志變量的值值flag:12022-5-9電氣與信息工程學院計算機系張吳波制作3標志變量法標志變量法6使用標志變量法判斷使用標志變量法判斷11是否是素數(shù)是否是素數(shù)flag:02 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 1011能否被能否被2 整除整除11能否被能否被3 整除整除11能否被能否被4 整除整除11能否被能否被5 整除整除11能否被能否被6 整除整除11能否被能否被7 整除整除11能否被能

18、否被8 整除整除11能否被能否被9 整除整除11能否被能否被10 整除整除完畢！完畢！2022-5-9電氣與信息工程學院計算機系張吳波制作#include int main int n, i,flag; printf “Enter an integer: ; scanf “%d, &n; flag=0; fori=2;i=n/2;i+ ifn%i=0 flag=1; break; ifflag=1 printf“%d不是素數(shù)不是素數(shù),n; else printf“%d是素數(shù)是素數(shù),n; return 0;lesson8_06.c2022-5-9電氣與信息工程學院計算機系張吳波制作3課堂練習課堂練習72022-5-9電氣與信息工程學院計算機系張吳波制作3課后練習課后練習81、一個數(shù)假如恰好等于它的因子之和，這個、一個數(shù)假如恰好等于它的因子之