C語(yǔ)言第3章-計(jì)算機(jī)算法初步課件

1、第3章 計(jì)算機(jī)算法初步 3.3 遞推與迭代法 3.2 窮舉法 3.1 算法的概念 3.1 算法的概念利用計(jì)算機(jī)求解問(wèn)題的一般過(guò)程（1）問(wèn)題分析階段 （2）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)階段 （3）算法設(shè)計(jì)階段 （4）編碼與調(diào)試階段 算法描述在計(jì)算機(jī)科學(xué)的發(fā)展過(guò)程中，人們已經(jīng)提出了很多種類(lèi)的算法描述方法。一種是自然語(yǔ)言的描述方法。鑒于自然語(yǔ)言本身過(guò)于靈活且又缺乏嚴(yán)謹(jǐn)性，所以容易產(chǎn)生理解上的歧義。還有一種算法的圖形描述方式流程圖。它采用一些標(biāo)準(zhǔn)的圖形符號(hào)描述算法的操作過(guò)程，從而避免了人們對(duì)非形式化語(yǔ)言的理解差異。 起止框I/O框處理框判斷框調(diào)用框連接框有向邊 常用流程圖符號(hào)例1：求解一元二次方程問(wèn)題分析假設(shè)一元二次

2、方程可以書(shū)寫(xiě)成ax2+bx+c=0?？梢钥闯?，任何一個(gè)一元二次方程都由三個(gè)系數(shù)a、b、c惟一確定，所以，首先需要用戶(hù)輸入三個(gè)系數(shù)，然后再根據(jù)一元二次方程的求解規(guī)則計(jì)算最終的結(jié)果，并將結(jié)果顯示輸出。 算法描述 #include #include main( )int a, b, c, t;printf( “Input a,b,c: ” );scanf( “%d%d%d”, &a, &b, &c );t = b*b 4*a*c;if (t0)printf( “No solutionn” ); else if ( t=0 )printf( “X = %lfn”, -b/(2.0*a) ); else

3、 double t0;t0 = sqrt( (double)t );printf( “X1 = %lf, X2= %lfn”, (-b+t0)/(2*a), (-b-t0)/(2*a) ); 程序代碼 3.2 窮舉法概述窮舉法，又稱(chēng)為枚舉法，是人們?nèi)粘Ｉ钪谐Ｓ玫囊环N求解問(wèn)題的方法。窮舉法的核心在于明確問(wèn)題的所有可能性，并針對(duì)每種可能情況逐個(gè)進(jìn)行判斷，最終找出正確問(wèn)題的答案。 窮舉法應(yīng)用實(shí)例1：素?cái)?shù)的判斷 所謂素?cái)?shù)是指僅能被1和自身整除，且大于等于2的數(shù)值。判斷一個(gè)給定的數(shù)值是否是素?cái)?shù)是窮舉法的典型實(shí)例。 例2：判斷給定整數(shù)是否是素?cái)?shù) 。 問(wèn)題分析為了檢查一個(gè)整數(shù)是不是素?cái)?shù)，可以采用窮舉法。假

4、設(shè)給定的整數(shù)用x表示，則判斷過(guò)程就是確認(rèn)x不能整除以2x-1之間的任何整數(shù)。這就需要一一列舉出2x-1之間的每個(gè)整數(shù)進(jìn)行排查。 NY開(kāi)始輸入x2 tt xt 加1x%t=0結(jié)束輸出“不是素?cái)?shù)”輸出“是素?cái)?shù)”YNt = xYN算法描述 #include main( )int x, t;printf( “Enter an integer: ” );scanf( “%d”, &x );for (t = 2; tx; t+ ) /* 列舉小于x大于1的所有整數(shù) */ if ( x%t = 0 ) break;if ( t = x )/* 是否通過(guò)循環(huán)條件出口 */ printf( “%d is pri

5、men”, x );else printf( “%d isnt primen”, x ); 程序代碼 窮舉法應(yīng)用實(shí)例2：百錢(qián)買(mǎi)百雞 “百錢(qián)買(mǎi)百雞”是我國(guó)古代數(shù)學(xué)家張丘建提出的一個(gè)著名的數(shù)學(xué)問(wèn)題。假設(shè)某人有錢(qián)百枚，希望買(mǎi)一百只雞；不同的雞價(jià)格不同，公雞5枚錢(qián)一只，母雞3枚錢(qián)一只，而小雞3只1枚錢(qián)。試問(wèn)：如果用百枚錢(qián)買(mǎi)百只雞，可以包含幾只公雞、幾只母雞和幾只小雞。 例3：百錢(qián)買(mǎi)百雞。 問(wèn)題分析從題目要求可知：公雞、母雞和小雞的數(shù)量是有限的，都不會(huì)超過(guò)100。通過(guò)對(duì)不同數(shù)量的公雞、母雞和小雞進(jìn)行組合，可以計(jì)算出購(gòu)買(mǎi)這些雞所用的花費(fèi)，但這個(gè)題目要求找出那些花費(fèi)正好100枚且雞的總數(shù)也為100只的情況。

6、因此，可以采用窮舉法，將不同的公雞、母雞和小雞的數(shù)量枚舉一遍，找出那些符合題目要求的解。 算法描述 #include #include 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 ); 程序代碼 3.3 遞推與迭代法 概述遞推常用于序列數(shù)據(jù)的計(jì)算。其基本策略是用已知結(jié)果和特定關(guān)系（遞推公式）計(jì)算中間值。采用遞推法進(jìn)行問(wèn)題求

7、解的關(guān)鍵在于找出遞推公式和邊界條件。迭代也是計(jì)算機(jī)數(shù)值計(jì)算的一種基本算法，其基本策略是從初值出發(fā)，不斷計(jì)算問(wèn)題的近似解。遞推與迭代法應(yīng)用實(shí)例1：等比數(shù)列求和 所謂等比數(shù)列是指在一組數(shù)據(jù)中，后項(xiàng)和前項(xiàng)之前存在著一個(gè)固定的比例關(guān)系。例如：整數(shù)序列3、15、75、375的初值是3，后項(xiàng)與前項(xiàng)是5倍的關(guān)系，即前項(xiàng)乘以5得到后項(xiàng)。本題要求給定等比序列的首項(xiàng)和比例，計(jì)算這個(gè)數(shù)列的前10項(xiàng)之和。例4：等比數(shù)列求和。 問(wèn)題分析等比數(shù)列的遞推公式為： itemi= itemi-1 * ratio后項(xiàng)等于前項(xiàng)乘以比例值sumi= sumi-1 + itemi前i項(xiàng)之和等于前i-1項(xiàng)之和加當(dāng)前項(xiàng)由于在重復(fù)上述遞推計(jì)

8、算之前，需要將第1項(xiàng)的值累加到sum中，所以，需要先將item存入sum中。 算法描述 #include main( )int item, ratio, sum,i;printf( “nEnter the first item and ratio: ” );scanf( “%d%d”, &item, &ratio );sum=item;for ( i=1; i10; i+ ) item *= ratio; sum += item; printf( “Sum of 10 items is %dn”, sum );程序代碼 遞推與迭代法應(yīng)用實(shí)例2：求圓周率圓周率的計(jì)算公式為： = 4 4/3 +

9、4/5 4/7 +4/9 4/11 + 例5：求圓周率。問(wèn)題分析圓周率的計(jì)算公式為： = 4 4/3 + 4/5 4/7 +4/9 4/11 + 圓周率是通過(guò)將數(shù)列4、-4/3、4/5求和得到的。在這個(gè)數(shù)列中，每個(gè)數(shù)據(jù)項(xiàng)的取值與前一項(xiàng)及該項(xiàng)的序號(hào)存在著一定的關(guān)系。可以通過(guò)迭代，逐個(gè)計(jì)算出每一個(gè)數(shù)據(jù)項(xiàng)，再將它們累加起來(lái)。為了滿(mǎn)足要求的精度，可以通過(guò)檢查數(shù)據(jù)項(xiàng)的大小來(lái)控制循環(huán)的終止。由于數(shù)據(jù)項(xiàng)的絕對(duì)值是遞減的，且相鄰項(xiàng)的符號(hào)不同，如果第n個(gè)數(shù)據(jù)項(xiàng)的絕對(duì)值已經(jīng)小于精度值，則前n項(xiàng)之和一定已經(jīng)滿(mǎn)足精度要求了。算法描述 #include #include main( )int i = 1, sign = 1; double PI=