[其它]lesson 7 計(jì)算機(jī)算法初步ppt課件

1、2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作學(xué)習(xí)目的學(xué)習(xí)目的:3 1掌握幾個(gè)常用的解題算法：枚舉、迭代掌握幾個(gè)常用的解題算法：枚舉、迭代2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3窮舉法窮舉法2 概述概述l窮舉法，又稱為枚舉法，是人們?nèi)粘Ｉ钪谐Ｓ酶F舉法，又稱為枚舉法，是人們?nèi)粘Ｉ钪谐Ｓ玫囊环N求解問題的方法。的一種求解問題的方法。l根據(jù)問題中的部分條件的條件將所有可能解根據(jù)問題中的部分條件的條件將所有可能解的情況列舉出來，然后通過一一驗(yàn)證是否符合整的情況列舉出來，然后通過一一驗(yàn)證是否符合整個(gè)問題的求解要求，而得到問題的解。

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

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

4、每個(gè)整數(shù)進(jìn)展排查。 2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作 算法描繪 NY開始開始輸入輸入x2 tt xt 加加1x%t=0結(jié)束結(jié)束輸出輸出“不是素?cái)?shù)不是素?cái)?shù)”輸出輸出“是素?cái)?shù)是素?cái)?shù)”YNt = xYN2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作#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;注意判斷是否是素?cái)?shù)的條件與注意判斷是否是素?cái)?shù)的條件與判斷位置判斷位置lesson8_01.c2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3窮舉法窮舉法2 例例2：百錢買百雞：百錢買百雞l “百錢買百雞是我國古代數(shù)學(xué)家張丘建提出的一個(gè)百錢買百雞是我國古代數(shù)學(xué)家張丘建提出的一個(gè)著名的數(shù)學(xué)問題。假設(shè)某人有錢百枚，希望買一百只著名的數(shù)學(xué)問題。假設(shè)某人有錢百枚，希望買一百只雞；不同的雞價(jià)格不同，公雞雞；不同的雞價(jià)格不同，公雞5枚錢一只，母雞枚錢一

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

7、題目要求找出那些花費(fèi)正好100100枚且枚且雞的總數(shù)也為雞的總數(shù)也為100100只的情況。只的情況。l因此，可以采用窮舉法，將不同的公雞、母雞和小因此，可以采用窮舉法，將不同的公雞、母雞和小雞的數(shù)量枚舉一遍，找出那些符合題目要求的解。雞的數(shù)量枚舉一遍，找出那些符合題目要求的解。 2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作 算法描繪 N Y 開開始始 條條件件判判斷斷 x 加加 1 結(jié)結(jié)束束 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電氣與信息工程學(xué)院計(jì)算機(jī)系

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電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3課堂練習(xí)課堂練習(xí)3、求所有的三位水仙花數(shù)、求所有的三位水仙花數(shù)假設(shè)一個(gè)假設(shè)一個(gè)3位自然數(shù)的各位數(shù)字的位自然數(shù)的各位數(shù)字的3次方之次方之和等于它本身和等

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

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

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

12、ratio item sum 1 i i 10 item*ratio item 加加一一 sum+itemsum i 加加 1 結(jié)結(jié)束束 輸輸出出 sum 2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作#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 結(jié)結(jié) 束束

13、 輸輸 出出 P I 2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作#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ù)據(jù)項(xiàng)精度控制循環(huán)數(shù)據(jù)項(xiàng)精度控制循環(huán) */ printf “PI = %lfn, PI ; return 0; lesson8_04.c2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3遞推與迭代法遞推與迭代

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

15、算法描繪 NY開始開始輸入輸入x計(jì)算整數(shù)最高位權(quán)計(jì)算整數(shù)最高位權(quán)nn = 1x/n的余數(shù)的余數(shù)xn/10 n結(jié)束結(jié)束打印打印x/n2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作#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、信息工程學(xué)院計(jì)算機(jī)系張吳波制作3課堂練習(xí)課堂練習(xí)5求數(shù)列、求數(shù)列、8 8的前項(xiàng)的前項(xiàng)2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3標(biāo)志變量法標(biāo)志變量法6標(biāo)志變量法的根本思想：標(biāo)志變量法的根本思想：為了表示處理對象所處的狀態(tài)結(jié)果，使為了表示處理對象所處的狀態(tài)結(jié)果，使用一個(gè)變量，給其規(guī)定假設(shè)干個(gè)值，并且規(guī)用一個(gè)變量，給其規(guī)定假設(shè)干個(gè)值，并且規(guī)定每個(gè)值所表示的狀態(tài)意義，然后通過定每個(gè)值所表示的狀態(tài)意義，然后通過判斷變量的值來知道程序處理的結(jié)果判斷變量的值來知道程序處理的結(jié)果2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3標(biāo)志變量法標(biāo)志變量法6例例6：使用標(biāo)志變量法判斷：使用標(biāo)志變量法判

17、斷9是否是素?cái)?shù)是否是素?cái)?shù)flag:02 , 3 , 4 , 5 , 6 , 7 , 89能否被能否被2 整除整除9能否被能否被3 整除整除給給flag賦賦1：改：改變標(biāo)志變量的變標(biāo)志變量的值值flag:12022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3標(biāo)志變量法標(biāo)志變量法6使用標(biāo)志變量法判斷使用標(biāo)志變量法判斷11是否是素?cái)?shù)是否是素?cái)?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電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作#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不是素?cái)?shù)不是素?cái)?shù),n; else printf“%d是素?cái)?shù)是素?cái)?shù),n; return 0;lesson8_06.c2022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3課堂練習(xí)課堂練習(xí)72022-5-9電氣與信息工程學(xué)院計(jì)算機(jī)系張吳波制作3課后練習(xí)課后練習(xí)81、一個(gè)數(shù)假如恰好等于它的因子之和，這個(gè)、一個(gè)數(shù)假如恰好等于它的因子之