1、第四章 算法設(shè)計(jì)方法14.1 算法的概念4.2 算法的三種基本結(jié)構(gòu)4.3 算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究提綱2程序設(shè)計(jì)的目的和步驟算法的描述方式計(jì)算機(jī)算法及其特性4.1 算法的概念34.1 算法的概念一. 程序設(shè)計(jì)的目的計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的根本問(wèn)題是：什么能夠被有效地自動(dòng)化 ；設(shè)計(jì)程序的根本目的：讓計(jì)算機(jī)幫助人們自動(dòng)地完成所要處理的復(fù)雜任務(wù)；程序設(shè)計(jì)兩個(gè)核心問(wèn)題：“做什么”與“怎么做” ；其中需求分析解決“做什么”，程序設(shè)計(jì)解決“怎么做” 。44.1 算法的概念二. 程序設(shè)計(jì)兩步走對(duì)復(fù)雜問(wèn)題，直接寫(xiě)出能解決該問(wèn)題的計(jì)算機(jī)程序是困難的，為此，人們?cè)谶M(jìn)行程序設(shè)計(jì)

2、時(shí)分兩步走：1）算法設(shè)計(jì)：不使用程序設(shè)計(jì)語(yǔ)言，而使用一種較簡(jiǎn)單明了的表達(dá)方式（例如自然語(yǔ)言）設(shè)計(jì)出求解問(wèn)題的步驟序列-算法。2）程序編寫(xiě)：根據(jù)設(shè)計(jì)并描述好的算法，使用某種程序設(shè)計(jì)語(yǔ)言編寫(xiě)對(duì)應(yīng)于該算法的程序 。5三. 算法的概念算法：是解決問(wèn)題的步驟序列（操作序列）。 4.1 算法的概念起床穿衣、疊被去水房洗漱回宿舍放洗漱用品騎車(chē)去食堂排隊(duì)買(mǎi)飯吃飯交回餐具騎車(chē)去教室描述的是活動(dòng)和過(guò)程7:20前離開(kāi)宿舍7:50前離開(kāi)食堂8:00前進(jìn)入教室描述的是操作執(zhí)行后的狀態(tài)，通過(guò)狀態(tài)的轉(zhuǎn)移來(lái)描述所執(zhí)行的操作?？赡艿幕顒?dòng)：起床、穿衣疊被、洗漱等可能的活動(dòng)：騎車(chē)到食堂、排隊(duì)買(mǎi)飯、吃飯、交回餐具64.1 算法的概念

3、四. 計(jì)算機(jī)算法及其特性什么是計(jì)算機(jī)可執(zhí)行的操作；要在計(jì)算機(jī)能力集上進(jìn)行算法設(shè)計(jì)；算法必須具備的五個(gè)特性：可執(zhí)行性：算法中的每一個(gè)步驟都是計(jì)算機(jī)可執(zhí)行的（在計(jì)算機(jī)能力集范圍內(nèi)） ；確定性：算法中的每一個(gè)步驟，必須是明確定義的，不得有任何歧義性 ；有窮性：算法必須在執(zhí)行有窮步之后結(jié)束； 有輸入信息的說(shuō)明：對(duì)加工對(duì)象提要求；有輸出信息的步驟 ：至少要輸出問(wèn)題答案。7例1 求12910 ，即10！算法思路： 計(jì)算機(jī)能力集只提高兩數(shù)相乘的運(yùn)算。 N！=N （N-1）！ 10！=10 9！=10 9 8！ =10 9 8 7！ =. =10 9 8 2 1!先計(jì)算1！、再計(jì)算2!=2*1!、再計(jì)算3!=

4、3*2!,以此類(lèi)推，直到計(jì)算出10!=10*9!。使用變量p8例1 求12910 ，即10！第一種算法：S1(求2!)：先求21，得到結(jié)果2并賦值給變量p；即：21p；S2 (求3!) ：將步驟S1得到的乘積p（p=2）再乘以3，得結(jié)果6并 賦值給變量p；即： 3 pp；S3(求4!)：將p（p=6）再乘以4，得24并賦值給變量p；即： 4pp；S4(求5！)：將p（p=24）再乘以5，得120并賦值給變量p；即： 5pp；S9(求10!)：將p（p=362880)乘以10，得3628800，10pp；9#includemain() int p; p=2*1; /求2!賦值給p p=3*p;

5、/求3!賦值給p p=4*p; p=5*p; p=6*p; p=7*p; p=8*p; p=9*p; p=10*p; /求10!賦值給p printf(%d,p); system(pause); return 0; 評(píng)價(jià)：求10!需要寫(xiě)9個(gè)賦值操作，算法過(guò)于繁瑣！試想：求1000！的算法10對(duì)算法進(jìn)行抽象:核心操作就是兩數(shù)相乘ipp ，反復(fù)相乘10-1=9次，i初始值為2，p初始值為1，每相乘一次i的值加1。根據(jù)上述分析，本題可利用循環(huán)結(jié)構(gòu)求解：第1次循環(huán)用于求2！，第2次循環(huán)在第1次循環(huán)基礎(chǔ)上求3！，,第9次循環(huán)在第8次循環(huán)基礎(chǔ)上求10！例1 求12910 ，即10！11定義兩個(gè)變量p和i，

6、p代表階乘結(jié)果,i代表本次循環(huán)要求的是i!； 循環(huán)條件：ip；S4：使i的值加1，即i+1=i；S5：如果i=10，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。 最后得到p的值就是10！的值。 求12910算法思路：“迭代”和“循環(huán)” ：在程序設(shè)計(jì)中，重復(fù)執(zhí)行同樣操作的過(guò)程稱(chēng)為“迭代”。程序中被重復(fù)執(zhí)行的程序段稱(chēng)為“循環(huán)”。13例1源程序#include main() int n, i, p; /n：存儲(chǔ)要求階乘的數(shù)；p：存儲(chǔ)求得的階乘； printf(input n:n);scanf(%d,&n);i=2; p=1; while (i = n) p=i*p; i=i+1;

7、printf(%d!=%d,n,p); system(pause); return 0;14練習(xí)1：輸入十個(gè)整數(shù)，求出最大值、最小值。算法思路：采用迭代計(jì)算的方法 以求最大值為例，即：Max(N1)=N1Max(N2,N1)= N1 if N2=N1Max(N3,N2,N1)= Max( N3, Max(N2,N1) ).Max(Nn , Nn-1 ,N2,N1) Max(Nn ,Max(Nn-1 ,N2,N1)定義變量max來(lái)存儲(chǔ)前n-1個(gè)整數(shù)的最大值。第n個(gè)數(shù)將和max比較，決定前n個(gè)數(shù)的最大值。整個(gè)問(wèn)題就被轉(zhuǎn)變?yōu)榍?次兩個(gè)數(shù)的最大值。每一次都是讀入一個(gè)數(shù)，和之前求得的最大數(shù)再去比較。15

8、循環(huán)條件：imax,則max=n； 否則，如果nmin,則min=n； i=i+1;循環(huán)初始化：讀入一整數(shù)n;minn; max=n;i2；請(qǐng)寫(xiě)出本題源程序16源程序：輸入十個(gè)整數(shù)，求出最大值、最小值#include#define COUNT 10 main() int i, n, max, min;/i:循環(huán)計(jì)數(shù)；n:讀取的數(shù)； /max:當(dāng)前最大值; min:當(dāng)前最小值 scanf(%d, &n); max=n; /將第一個(gè)數(shù)作為最大值和最小值 min=n; i=2; /代表接下去要讀取的是第2個(gè)數(shù) 17源程序：輸入十個(gè)整數(shù)，求出最大值、最小值(續(xù)) while (i max) /求最大數(shù)

9、 max = n; else if (n i；問(wèn)題分析：就是反復(fù)輸入處理每一個(gè)學(xué)生的信息，處理120次。19輸入120個(gè)學(xué)生的學(xué)號(hào)和成績(jī)，要求將他們之中成績(jī)?cè)?0分以上者的學(xué)號(hào)和成績(jī)打印出來(lái)。S1：1=i；S2：讀入第i個(gè)學(xué)生的學(xué)號(hào)和成績(jī)分別到變量num和score中；S3：如果score 60，則打印num和score ；S4：i+1=i；S5：如果i120，則返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。循環(huán)處理模式：處理本次循環(huán)要做的任務(wù)；為下一次循環(huán)做準(zhǔn)備；204.1 算法的概念練習(xí)2：請(qǐng)寫(xiě)出本題對(duì)應(yīng)的程序214.1 算法的概念#include main() int no,total,count

10、;/no:學(xué)號(hào)。total:總學(xué)生數(shù)。count：計(jì)數(shù) float score;/成績(jī) printf(how many int numbers do you want to input:n);scanf(%d,&total); count=1;while(count60) printf(no:%dtscore:%fn,no,score); count=count+1; system(pause); return 0；22例3 一個(gè)大于或等于3的正整數(shù)，判斷它是否為一個(gè)素?cái)?shù)（質(zhì)數(shù)） 。所謂質(zhì)數(shù)，是指除了1和該數(shù)本身外，不能被其他任何整數(shù)整除的數(shù)。例如，13是素?cái)?shù)（質(zhì)數(shù)）。因?yàn)樗荒鼙?，3，4，

11、12整除。由于素?cái)?shù)在當(dāng)代的密碼學(xué)中扮演了中心的作用，所以該問(wèn)題具有重要意義。判斷一個(gè)數(shù)n（n3）是否為質(zhì)數(shù)：將n作為被除數(shù)，將2到（n-1）各個(gè)整數(shù)依次作為除數(shù)，如果都不能被整除，則n為素?cái)?shù)。4.1 算法的概念23判斷質(zhì)數(shù)看n能否被2到（n-1）之間的各個(gè)整數(shù)整除： 變量抽象：n：存放被判斷的整數(shù)；i：存放除 數(shù)，取值為2,n-1；r：存放n/i得到的余數(shù)循環(huán)體：n被i除，得余數(shù)r；即n mod i=r；如果r=0，表示n能被i整除，則打印n“不是素?cái)?shù)”，算法結(jié)束；否則i+1=i；循環(huán)條件： ir；如果r=0，表示n能被i整除，則打印n“不是素?cái)?shù)”，令isPrim=1；否則i+1=i；循環(huán)條件

12、： irS4：如果r=0，表示n能被i整除，則打印n“不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行S5；S5：i+1=i；S6：如果in-1，返回S3；否則，打印n“是素?cái)?shù)”，算法結(jié)束。 n：被判斷的整數(shù)；i：被除數(shù)；r：存放n/i得到的余數(shù)事實(shí)上，i只需2到 之間的整數(shù)整除即可。264.1 算法的概念4.2 算法的三種基本結(jié)構(gòu)4.3 算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究提綱274.2 算法的三種基本結(jié)構(gòu) 三種控制結(jié)構(gòu)(Bohra和Jacopini )順序結(jié)構(gòu)、 選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 順序結(jié)構(gòu) 按書(shū)寫(xiě)順序執(zhí)行的語(yǔ)句構(gòu)成的程序段。28選擇結(jié)構(gòu) 根據(jù)給定的表達(dá)式是否成立而選擇執(zhí)行操作A

13、或操作B。如果表達(dá)式成立，則執(zhí)行操作A；如果表達(dá)式不成立，則執(zhí)行操作B。操作B可以為空。4.2 算法的三種基本結(jié)構(gòu)29 當(dāng)型循環(huán)結(jié)構(gòu)4.2 算法的三種基本結(jié)構(gòu)C語(yǔ)言無(wú)直到型循環(huán)結(jié)構(gòu)。比較：直到型循環(huán)結(jié)構(gòu)和C語(yǔ)言中的do-while結(jié)構(gòu)？ 直到型循環(huán)結(jié)構(gòu)30三種控制結(jié)構(gòu)的共同點(diǎn) 只有一個(gè)入口（a處） 只有一個(gè)出口（b處） 結(jié)構(gòu)內(nèi)的每一個(gè)部分都有機(jī)會(huì)被執(zhí)行到 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”（無(wú)終止的循環(huán)）4.2 算法的三種基本結(jié)構(gòu)由這三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜問(wèn)題！314.1 算法的概念4.2 算法的三種基本結(jié)構(gòu)4.3 算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究

14、提綱324.3 算法的描述方法 用自然語(yǔ)言描述 用流程圖描述 用N-S流程圖描述 用偽碼描述 用計(jì)算機(jī)語(yǔ)言描述 334.3 算法的描述方法自然語(yǔ)言文字冗長(zhǎng)； 不嚴(yán)格，易產(chǎn)生歧義（二義性）； 不方便描述分支和循環(huán)結(jié)構(gòu)；344.3 算法的描述方法流程圖 流程圖的基本元素（ANSI規(guī)定） 起止框輸入/出框判斷框處理框流程線(xiàn) 連接點(diǎn) 注釋框 354.3 算法的描述方法流程圖流程圖描述的選擇結(jié)構(gòu)36 當(dāng)型循環(huán)結(jié)構(gòu) 直到型循環(huán)結(jié)構(gòu)流程圖描述的循環(huán)結(jié)構(gòu)4.3 算法的描述方法流程圖37連接點(diǎn)（小圓圈）：用于將畫(huà)在不同地方的流程線(xiàn)連接起來(lái) 38求10！流程圖使用當(dāng)型循環(huán)結(jié)構(gòu)描述39打印學(xué)生序號(hào)及成績(jī)流程圖40判

15、斷質(zhì)數(shù)的流程圖使用直到型循環(huán)結(jié)構(gòu)描述判斷r是否為0條件成立則跳出循環(huán)41練習(xí)：將以上流程圖改成用當(dāng)型循環(huán)結(jié)構(gòu)表示。該流程圖中循環(huán)結(jié)構(gòu)有兩個(gè)出口！違反單入單出原則！如何改進(jìn)？42改進(jìn)后的流程圖：?jiǎn)稳雴纬?設(shè)置標(biāo)志位isPrim43傳統(tǒng)流程圖的弊端 對(duì)流程線(xiàn)的使用沒(méi)有嚴(yán)格限制，閱讀困難； 不能保證算法結(jié)構(gòu)的單入單出特性； 占用篇幅較多 ； 4.3 算法的描述方法N-S流程圖必須限制箭頭的濫用，讓流程只能順序執(zhí)行下去！保證結(jié)構(gòu)化原則的流程描述工具N-S圖44 基本結(jié)構(gòu)4.3 算法的描述方法N-S流程圖p、p1表示的是判斷條件；A、B框是操作；注意：A、B框可以是一個(gè)簡(jiǎn)單的操作（如讀入數(shù)據(jù)或打印輸出等

16、），也可以是三種基本結(jié)構(gòu)之一順序結(jié)構(gòu)選擇結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)45例1 求10!的N-S流程圖4.3 算法的描述方法N-S流程圖46例2 打印學(xué)生成績(jī)N-S流程圖4.3 算法的描述方法N-S流程圖47例3 判斷質(zhì)數(shù)的N-S流程圖4.3 算法的描述方法N-S流程圖484.3 算法的描述方法偽碼描述流程圖和N-S圖畫(huà)起來(lái)比較費(fèi)事，適合于表示算法，而在算法設(shè)計(jì)中使用不是很理想。偽碼 用介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。【返回】 IF x is positive THEN print x ELSE print yWHILE i60 THEN print score i加14

17、94.3 算法的描述方法例4：利用泰勒級(jí)數(shù)：-LLLL+-+-+-=+)!12()1(!7!5!3sin121753nxxxxxxnn計(jì)算正弦的值，直到最后一項(xiàng)絕對(duì)值小于10-6 時(shí)為止。被除數(shù)除數(shù)符號(hào)n1n2n3分析：求n項(xiàng)和的算法思路Sum(a1)=a1Sum(a1,a2)=Sum(a1)+a2 =a1+a2Sum(a1,a2, a3)=Sum(a1,a2)+a3Sum(a1,a2,an)=Sum(a1,a2,an-1)+an504.3 算法的描述方法算法的核心操作是求兩數(shù)之和，其中第一個(gè)操作數(shù)是前一次求得的和。如何求第二個(gè)操作數(shù)？算法1：n決定了第n項(xiàng)因子的值，即第二個(gè)操作數(shù)；因此每一次

18、可根據(jù)當(dāng)前n的值計(jì)算出第二個(gè)操作數(shù)。請(qǐng)用NS圖描述出算法1。51求sin(x)算法1i代表下一個(gè)p是第幾項(xiàng)，因此初值是1變量抽象： x：存儲(chǔ)未知數(shù)x的值； sum：存儲(chǔ)和 ； p：存儲(chǔ)當(dāng)前待加的因子；i：當(dāng)前待加的是第幾個(gè)因子52問(wèn)題：任何數(shù)據(jù)類(lèi)型只能表示一定范圍內(nèi)的數(shù)，當(dāng)試圖往變量中存儲(chǔ)在范圍之外的數(shù)，數(shù)據(jù)無(wú)法正確存儲(chǔ)。求x的n次方和(2n-1)!時(shí)可能會(huì)導(dǎo)致結(jié)果太大而溢出。解決方法：改進(jìn)算法算法2534.3 算法的描述方法=-)!32()1(32ixii=-+)!12()1(121ixii-LLLL+-+-+-=+)!12()1(!7!5!3sin121753nxxxxxxnn算法2：設(shè)第

19、i項(xiàng)因子表示為 ，考察 和 的關(guān)系。 = *(-1)* x2 /(2i-1)*(2i-2)54請(qǐng)用NS圖描述算法2。4.3 算法的描述方法【源程序演示】i代表下一個(gè)p是第幾項(xiàng)，因此初值是155#include#includemain()int i;float x; double sum, p; /p用于存放待加的那一項(xiàng)printf(input x:);scanf(%f,&x);/*變量初始化*/sum=0.0;i=1;p=x;/*求解*/while(fabs(p)1e-8) sum=sum+p; i=i+1; p=-p*x*x/(2*i-2)*(2*i-1); printf(sin(%f) =

20、 %lfn,x,sum); system(pause); return 0;564.1 算法的概念4.2 算法的三種基本結(jié)構(gòu)4.3 算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究提綱57源自于對(duì)goto語(yǔ)句的爭(zhēng)論goto語(yǔ)句詳見(jiàn)程序設(shè)計(jì)教程436頁(yè)4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法58#include #include main() int count=1; start: /標(biāo)號(hào),是跟有冒號(hào)的標(biāo)識(shí)符 if (count10) goto end; printf(%d ,count); count=count+1; goto start; end: printf(n); system(p

21、ause); return 0; 1 2 3 4 5 6 7 8 9 10請(qǐng)按任意鍵繼續(xù). . .運(yùn)行效果：594.4 結(jié)構(gòu)化程序設(shè)計(jì)方法用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫(xiě)、閱讀、修改和維護(hù) 。結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu) 。結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思想：采用分而治之的方法，將一個(gè)復(fù)雜問(wèn)題分解為相對(duì)簡(jiǎn)單的一些子問(wèn)題，然后針對(duì)這些子問(wèn)題進(jìn)行求解。如果某個(gè)子問(wèn)題仍然是比較復(fù)雜的，再進(jìn)一步分解為子-子問(wèn)題，直到所有問(wèn)題都能夠求解。求解問(wèn)題的過(guò)程是分階段進(jìn)行的，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)（67個(gè)之內(nèi)）。604.4

22、結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法自頂向下；逐步細(xì)化；模塊化設(shè)計(jì)（函數(shù)）；結(jié)構(gòu)化編碼（三種基本結(jié)構(gòu)）。61例4.13 利用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)的最大公約數(shù)。輾轉(zhuǎn)相除法求最大公約數(shù)的數(shù)學(xué)定義如下：GCD（x,y）= y | xy and x MOD y = 0 GCD（y, x MOD y）| xy and x MOD y 0; 說(shuō)明：先判斷x能否被y整除，若可以，則最大公約數(shù)就是除數(shù)y；否則，則將y 作為被除數(shù)，x MOD y 作為除數(shù)繼續(xù)上面的操作，直到x能否被y整除為止。 GCD(6,4)GCD(4,2)=2=GCD(124,6)最大公約數(shù)為2例如：求GCD(124,6)的過(guò)程為：62

23、算法1xyr231交換變量x和y的值：自頂向下，逐步細(xì)化63最終算法1算法設(shè)計(jì)任務(wù)結(jié)束的標(biāo)準(zhǔn)是各步驟已精細(xì)到能用語(yǔ)句描述，即滿(mǎn)足算法的5大特征標(biāo)志算法設(shè)計(jì)任務(wù)結(jié)束 。64算法2思考：能否不借助于變量r，而是xy; y x%y？ 或者y x%y；x y65練習(xí)3：設(shè)計(jì)算法，求一個(gè)正整數(shù)的長(zhǎng)度。算法1：例如num=12345，求num的長(zhǎng)度第1步：去掉最低位，num=1234，長(zhǎng)度len=1第2步：去掉最低位，num=123，長(zhǎng)度len=2第3步：去掉最低位，num=12，長(zhǎng)度len=3第4步：去掉最低位，num=1，長(zhǎng)度len=4第5步：去掉最低位，num=0，長(zhǎng)度len=5算法中每一步的核心操

24、作是從num中去掉最低位，長(zhǎng)度len加16667求正整數(shù)的長(zhǎng)度-算法2假設(shè)num長(zhǎng)度不超過(guò)8，例如num=12345，求num的長(zhǎng)度算法2：試探能被10的幾次方除后商不為0第1步： num /107=0第2步： num /106=0第3步： num /105=0第4步： num /104!=0,說(shuō)明長(zhǎng)度為4+15算法中每一步的核心操作是試探：num除10i后商是否068 增加對(duì)輸入為0的判斷進(jìn)一步細(xì)化69練習(xí)4：分解數(shù)字練習(xí)4：輸入一個(gè)不超過(guò)8位的正整數(shù)，要求把這個(gè)整數(shù)分解為單個(gè)數(shù)字，然后打印出每一個(gè)數(shù)字（每一個(gè)數(shù)字之間用兩個(gè)空格分開(kāi)）。例如用戶(hù)輸入了4200，程序打印結(jié)果為：4 2 0 0。

25、設(shè)計(jì)算法。第1步：得到num最高位4并輸出，num=200第2步：得到num最高位2并輸出，num=0第3步：得到num最高位0并輸出，num=9第4步：得到num最高位0并輸出，num=070求num的長(zhǎng)度len，以及p（p為10的len-1次方）得到m最高位并輸出：m/p去掉m最高位：m=m%pp=p/10; len=len-1細(xì)化練習(xí)4：分解數(shù)字71練習(xí)5：判斷回文數(shù)練習(xí)5：設(shè)計(jì)算法，判斷一個(gè)正整數(shù)是否是回文數(shù)?；匚臄?shù)是指正讀和反讀都一樣的數(shù)。如121、1221就是回文數(shù)。算法1：回文數(shù)的第i位和倒數(shù)第i位肯定相等比較第1位和倒數(shù)第1位比較第2位和倒數(shù)第2位算法2：反著讀，假設(shè)讀得的數(shù)為

26、reverseNum，判斷num和reverseNum是否相等72判斷回文數(shù)-算法1left=num/10的len-1次方right=num%10num= num%10的len-1次方/1073以求a0a1a2a3的逆數(shù)為例，假設(shè)reverse實(shí)現(xiàn)逆著讀reverse(a3)=a3reverse(a2a3)=a3a2=a3*10 + a2= reverse(a3)*10+a2reverse(a1a2a3)=a3a2a1=a3a2*10 + a1 =reverse(a2a3)*10+ a1reverse(a0a1a2a3)=a3a2a1a0 =a3a2a1*10+a0 =reverse(a1a2

27、a3)*10+a0判斷回文數(shù)-算法274判斷回文數(shù)-算法275判斷回文數(shù)-算法2#include#includemain() int num;/存放輸入的整數(shù) int num1; /*循環(huán)中處理的數(shù),每循環(huán)一次,右邊少一位,假設(shè)num為1234,則 num1初始值為1234,然后是123,然后是12.;*/ int reverse;/*是用分解出來(lái)的數(shù)字組成的新數(shù)*/ int m;/*m:存放每一個(gè)分解出來(lái)的數(shù)字;*/ printf(請(qǐng)輸入一個(gè)小于8位的正整數(shù):); /讀取要判斷的整數(shù) scanf(%d,&num); 76 /*從右到左依次取出各個(gè)數(shù)字組裝成一個(gè)新的整數(shù)保持到reverse中*

28、/ num1=num; reverse=0; while(num1!=0) m=num1%10; /*取出num1的最低位*/ reverse=reverse*10+m; /*將最低位組裝到reverse中*/ num1=num1/10; /*去掉num1的最低位*/ if (num=reverse) printf(%d 是回文數(shù)n,num); else printf(%d 不是回文數(shù)n,num); system(PAUSE); return 0; 判斷回文數(shù)-算法277總結(jié)：循環(huán)結(jié)構(gòu)解題很多題目都需要循環(huán)結(jié)構(gòu)進(jìn)行求解。當(dāng)一時(shí)難以整理出每次循環(huán)（迭代）所做的事情時(shí)，可以先看一下如果這件事情交給

29、人做的話(huà)，一步一步是怎么做的。在上一步基礎(chǔ)上抽象出循環(huán)結(jié)構(gòu)的四個(gè)方面。78總結(jié)：循環(huán)結(jié)構(gòu)解題2和3一般沒(méi)有絕對(duì)的先后順序。在分析清楚2和3后，才分析4（為什么？）。一般將1放在最后分析在4中，要對(duì)出現(xiàn)在2和3中的某些變量進(jìn)行修改，為下次循環(huán)做好準(zhǔn)備，并使得循環(huán)能最終結(jié)束。思考上述四項(xiàng)工作有無(wú)先后順序？應(yīng)該是什么順序？79總結(jié)：對(duì)一批數(shù)進(jìn)行處理的模式循環(huán)次數(shù)未知循環(huán)次數(shù)已知804.1 算法的概念4.2 算法的三種基本結(jié)構(gòu)4.3 算法的描述方法4.4 結(jié)構(gòu)化程序設(shè)計(jì)方法4.5 算法設(shè)計(jì)實(shí)例研究提綱81例4.14 設(shè)計(jì)交通車(chē)輛觀測(cè)統(tǒng)計(jì)算法。 問(wèn)題描述：在一個(gè)路口設(shè)置一個(gè)探測(cè)器，通過(guò)通信線(xiàn)路連接到后臺(tái)

30、的計(jì)算機(jī)。路口每通過(guò)一輛汽車(chē)，探測(cè)器向計(jì)算機(jī)發(fā)出一個(gè)車(chē)輛信號(hào)1，探測(cè)器每隔1秒鐘向計(jì)算機(jī)發(fā)出一個(gè)時(shí)鐘信號(hào)0，觀測(cè)結(jié)束向計(jì)算機(jī)發(fā)出結(jié)束信號(hào)。 要求在計(jì)算機(jī)上設(shè)計(jì)一個(gè)程序，能夠接收探測(cè)器發(fā)出的信號(hào)，統(tǒng)計(jì)出觀測(cè)的時(shí)長(zhǎng)、在觀測(cè)時(shí)長(zhǎng)內(nèi)通過(guò)的車(chē)輛總數(shù)、以及兩輛車(chē)之間最大的時(shí)間間隔。 問(wèn)題分析：探測(cè)器向計(jì)算機(jī)發(fā)出的信號(hào)可以認(rèn)為是一個(gè)任意長(zhǎng)的字符序列（以#結(jié)束），比如：“011011000111101#”，這樣設(shè)計(jì)程序?qū)嶋H上演變?yōu)樽x取該字符序列，然后進(jìn)行相關(guān)的操作。 1 4.5 算法設(shè)計(jì)實(shí)例研究觀測(cè)時(shí)長(zhǎng)：字符序列中0的個(gè)數(shù)(6秒)；車(chē)輛總數(shù)：字符序列中1的個(gè)數(shù)(9輛)；兩車(chē)間最大時(shí)間間隔：兩個(gè)1之間的最大連續(xù)

31、0的個(gè)數(shù)(3秒)；探測(cè)器82計(jì)算觀測(cè)時(shí)長(zhǎng)（0的個(gè)數(shù)）和車(chē)輛總數(shù)（1的個(gè)數(shù)）是容易實(shí)現(xiàn)的，但是如何計(jì)算最大時(shí)間間隔需要進(jìn)一步考慮。在對(duì)一個(gè)比較復(fù)雜的問(wèn)題進(jìn)行分析時(shí)，我們應(yīng)該采用分而治之的方法，將復(fù)雜的問(wèn)題分解為相對(duì)比較簡(jiǎn)單的問(wèn)題，再針對(duì)該較簡(jiǎn)單問(wèn)題進(jìn)行求解。 我們首先設(shè)計(jì)算法主體框架?！?000110100011010#”！注意：2006年9月出版的教材假設(shè)接收到的信號(hào)總是以1開(kāi)始，因此算法會(huì)有所簡(jiǎn)化83“0000110100011010#”signal!=#待細(xì)化8485Level 1層算法設(shè)計(jì)第0層算法第1層算法86“0000110100011010#”分析：處理時(shí)鐘信號(hào)0觀測(cè)時(shí)長(zhǎng)secon

32、ds加1；兩種情況。如果此前已接收到車(chē)輛信號(hào)1 (如何判斷？)，則間隔時(shí)長(zhǎng)interval加1；否則不做任何處理。87“0000110100011010#”分析：處理車(chē)輛信號(hào)1第一種： “0000110100011010#”（這是第一個(gè)1）車(chē)輛總數(shù)vehicles加1第二種： “0000110100011010#”（不是第一個(gè)1，且前一個(gè)信號(hào)也是1 ）車(chē)輛總數(shù)vehicles加1第三種： “0000110100011010#”（不是第一個(gè)1，且前一個(gè)信號(hào)是0 ）車(chē)輛總數(shù)vehicles加1處理是否要更新最長(zhǎng)時(shí)間間隔（ interval：兩車(chē)之間的時(shí)間間隔，longest：兩車(chē)之間的最長(zhǎng)時(shí)間間隔

33、）88“0000110100011010#”分析：處理車(chē)輛信號(hào)1vehicles vehicles +1；情況1：第一個(gè)1 判斷式： vehicles =1情況2：不是第一個(gè)1，且前一個(gè)信號(hào)也是1 判斷式： vehicles1 & interval=0情況3：不是第一個(gè)1，且前一個(gè)信號(hào)是0 : 判斷式： vehicles1 & interval0 處理：1）若intervallongest 則 longest interval。 2） interval0。情況1情況3情況289“0000110100011010#”驗(yàn)證算法【程序演示】90#includemain() int vehicles;

34、 /記錄車(chē)輛信號(hào)總數(shù) int seconds; /記錄時(shí)鐘信號(hào)總數(shù) int longest; /記錄最長(zhǎng)時(shí)間間隔 int interval; /記錄時(shí)間間隔 char signal; /存放讀取的信號(hào) /* 初始化設(shè)置 */ vehicles=0; seconds=0; longest=0; interval=0; printf(please input signal: n); scanf(%c,&signal);/* 讀入第一個(gè)信號(hào) */91 /* 循環(huán)結(jié)構(gòu)處理輸入信號(hào)的字符序列,邊讀取邊處理 */ while (signal!=#) if (signal=1) /* 處理車(chē)輛信號(hào)*/ ve

35、hicles=vehicles+1; if (vehicles1 & interval0) if (intervallongest) longest=interval; interval=0; else/* 處理時(shí)鐘信號(hào)*/ seconds=seconds+1; if (vehicles0) interval=interval+1; scanf(%c,&signal); 92/* 輸出結(jié)果 */ printf(%d vehicles passed in %d secondsn,vehicles,seconds); printf(the longest gap was %d secondsn,l

36、ongest); system(PAUSE); return 0; 93練習(xí)：將一個(gè)由數(shù)字字符組成的字符串轉(zhuǎn)換為整數(shù)或者小數(shù)并輸出。如：輸入:134.567# 輸出:134.56794 #includemain() char ch; int num; /存放小數(shù)點(diǎn)前面的字符轉(zhuǎn)換后得到的整數(shù) float fnum; /存放小數(shù)點(diǎn)后面的字符轉(zhuǎn)換后得到的浮點(diǎn)數(shù) int n; /存放字符對(duì)應(yīng)的數(shù)字 int p; / 存放小數(shù)點(diǎn)后面的字符轉(zhuǎn)換后得到的數(shù)字對(duì)應(yīng)的基數(shù)1/p。小數(shù)點(diǎn)后第一位數(shù)的基數(shù)是1/10 int flag;/用于表示輸入的字符中是否有小數(shù)點(diǎn)。若有，則flag值為1；否則為0 num =

37、0; fnum = 0; p = 10; flag = 0; printf(please input the string:); 算法1：逐情況對(duì)字符進(jìn)行處理95 scanf(%c,&ch); while( ch != #) if (ch=.) flag = 1;/flag為1，表示輸入了小數(shù)點(diǎn) else /處理小數(shù)點(diǎn)之前的字符 n = ch - 0; if (flag = 0)/若輸入的是小數(shù)點(diǎn)之前的數(shù) num = num * 10 + n; else/處理小數(shù)點(diǎn)之后的字符 fnum = fnum + (float)n / p; /必須進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換，否則n/p結(jié)果為0 p = p * 1

38、0; scanf(%c,&ch); 96 if (flag = 0) printf(the result is:%dn,num); else printf(the result is:%fn,num+fnum); system(pause); return 0;97 #includemain() char ch; int num; float fnum; int n,p,flag=0; printf(please input the string:); /處理整數(shù)部分 num = 0; scanf(%c,&ch); while(ch != . & ch != #) n = ch - 0; nu

39、m = num * 10 + n; scanf(%c,&ch); 算法2：先循環(huán)處理小數(shù)點(diǎn)前面的字符，再循環(huán)處理小數(shù)點(diǎn)后面的字符98 if (ch=.) /處理小數(shù)部分 p = 10; flag = 1; /flag為1表示有小數(shù)部分 scanf(%c,&ch); while(ch != #) n = ch - 0; fnum = fnum + (float)n / p; /必須進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換，否則n/p結(jié)果為0 scanf(%c,&ch); p = p * 10; if (flag = 0) printf(the result is:%dn,num); else printf(the re

40、sult is:%fn,num+fnum); system(pause); return 0;99迭代算法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。利用迭代算法解決問(wèn)題，需要做好以下三個(gè)方面的工作 確定迭代變量ai。在可以用迭代算法解決的問(wèn)題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。 建立迭代關(guān)系式，即aif(ai-1)對(duì)迭代過(guò)程進(jìn)行控制 。迭代過(guò)程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值

41、，可以計(jì)算出來(lái)；另一種是所需的迭代次數(shù)無(wú)法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來(lái)實(shí)現(xiàn)對(duì)迭代過(guò)程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來(lái)結(jié)束迭代過(guò)程的條件。 100例4.15 猴子吃桃問(wèn)題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺(jué)得不過(guò)癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個(gè)，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問(wèn)這堆桃子原來(lái)有多少個(gè)？ 4.5 算法設(shè)計(jì)實(shí)例研究101分析：假設(shè)第一天早上吃前有桃子a1個(gè),第二天早上吃前有桃子a2個(gè)，第三天早上吃前有桃子a3個(gè)，以此類(lèi)推，則a2a1（a1/2+1）= a1/2-1a9a8（a8/2+1）= a8/2

42、-1 a10a9（a9/2+1）= a9/2-1 = 1可見(jiàn)，在已知a10的情況下，可以求得a9，已知a9可以求得a8最終求得a1102即：a9= 2 ( a10+ 1 ) a8= 2 ( a9+ 1 )a1= 2 ( a2+ 1 )也就是：ai2(ai+1+1) i=9,8,7,6,.,1現(xiàn)在已知a10值為1，可以采用迭代法求得a1。103104依次計(jì)算出第9天、第8天第1天吃前的桃子數(shù)current_day_count 表示當(dāng)天的桃子數(shù)，代表數(shù)學(xué)模型中的ai。初始值是1，代表第10天早上的桃子數(shù)是1。day_count 表示第幾天，代表數(shù)學(xué)模型中的i。初始值為9，代表第一次循環(huán)求的是第9天

43、早上的桃子數(shù)?！境绦蜓菔尽?05#includemain() int day；/表示當(dāng)前求解的是第幾天吃前的桃子數(shù) int peach; /示某一天的桃子數(shù) day = 9; /第一次循環(huán)求第9天吃前的桃子數(shù) peach = 1; /第10天吃前的桃子數(shù)是1 while(day = 1) peach = 2 * ( peach + 1); day = day - 1; printf(桃子數(shù)是：%d,peach); system(pause);106第一天：1534個(gè)桃子第二天：766個(gè)桃子第三天：382個(gè)桃子第四天：190個(gè)桃子第五天：94個(gè)桃子第六天：46個(gè)桃子第七天：22個(gè)桃子第八天：10

44、個(gè)桃子第九天：4個(gè)桃子第十天：1個(gè)桃子107練習(xí)6：一個(gè)皮球從100m高處落下，每次落地后反彈到原來(lái)高度的一半。編寫(xiě)程序，求20次反彈時(shí)彈起的高度?！境绦蜓菔尽糠治觯篴0=100a1=a0/2a2=a1/2a20=a19/2108#include#define TIMES 20 main() int times; /記錄是第幾次彈起 double height; /記錄小球彈起時(shí)的高度 height=10000.0; /*height的單位是cm*/ times=1;/*第一次循環(huán)求第1次彈起高度 */ while(times=TIMES) height=height/2;/*除以2后的hei

45、ght表示第times次彈起的高度*/ times=times+1; printf(第%d次小球彈起的高度是%f厘米,TIMES,height); system(pause); return 0; 109練習(xí)7：在許多情況下，知道一個(gè)數(shù)是否是素?cái)?shù)還不夠，有時(shí)，還需要知道它的約數(shù)。每個(gè)大于1的正整數(shù)都能表示為素?cái)?shù)的乘積。這個(gè)因數(shù)分解是唯一的，被稱(chēng)為素?cái)?shù)分解（prime factorization）。例如，數(shù)字60=2*2*3*5, 799=17 *47,其中每一個(gè)約數(shù)都是素?cái)?shù)。注意，同一個(gè)素?cái)?shù)在因數(shù)分解中可以出現(xiàn)多次。設(shè)計(jì)一個(gè)算法顯示數(shù)n的素?cái)?shù)分解 。 要求用自頂向下、逐步求精的方法設(shè)計(jì)算法。1

46、10問(wèn)題分析： 60=2*2*3*5f(p)=n*f(p/n), n是p的最小質(zhì)數(shù)因子對(duì)p進(jìn)行素?cái)?shù)分解，可以轉(zhuǎn)化為兩步：1：找到num的最小質(zhì)數(shù)因子n；2：對(duì)p/n繼續(xù)進(jìn)行素?cái)?shù)分解；111isPrim=1；j=2;當(dāng)j*j=i而且isPrim=1 i是否被j整除nyj+isPrim=0isPrim為1表示質(zhì)數(shù)。設(shè)置初始最小質(zhì)因數(shù)n=prePrim設(shè)置能否找到質(zhì)因數(shù)found為0當(dāng)np而且found=0時(shí)判斷n是否是質(zhì)數(shù)，結(jié)果存于isPrim中nyisPrim=1p整除nynfound1i是最小的質(zhì)因數(shù)prePrim=in=n+1n=n+1【程序演示】素?cái)?shù)分解算法1：prePrim=2當(dāng)p!=1

47、時(shí)求p的最小質(zhì)因數(shù)n輸出npp/n輸入一個(gè)整數(shù)p每一次找質(zhì)因數(shù)都是從prePrim開(kāi)始試探112f(p)=n*f(p/n), p從2開(kāi)始試探，逐漸變大（加1）。若試探過(guò)程中發(fā)現(xiàn)p能被n整除，則n肯定是素?cái)?shù)。原因分析：根據(jù)題意，任何合數(shù)均能分解為若干個(gè)素?cái)?shù)的乘積。假設(shè)n為6且p除以n余數(shù)為0，則n=6*，由于62*3, 因此n=2*3*，在分解出6之前早就已經(jīng)分解得到2*3了，所以 p不可能為6。其他的合數(shù)也是如此。素?cái)?shù)分解算法2：113為了方便窮舉法解題，補(bǔ)充下述C語(yǔ)言知識(shí)逗號(hào)運(yùn)算符和逗號(hào)表達(dá)式for語(yǔ)句114逗號(hào)運(yùn)算符和逗號(hào)表達(dá)式逗號(hào)運(yùn)算符 ， 用于把幾個(gè)表達(dá)式串在一起。逗號(hào)表達(dá)式 含有逗號(hào)

48、運(yùn)算符的表達(dá)式，實(shí)現(xiàn)對(duì)各個(gè)表達(dá)式的順序求值，主要用于for語(yǔ)句中。執(zhí)行過(guò)程 先計(jì)算表達(dá)式1，然后依次計(jì)算其后的各個(gè)表達(dá)式的值，并將最右邊那個(gè)表達(dá)式的值作為逗號(hào)表達(dá)式的值。表達(dá)式1 ，表達(dá)式2， ，表達(dá)式ny = 1 0 ;x = ( y = y - 5 , 30 / y ) ;/運(yùn)算后y的值為5，x的值為6。/逗號(hào)表達(dá)式優(yōu)先級(jí)比賦值表達(dá)式低，所以必須加括號(hào)115/*使用for結(jié)構(gòu)的計(jì)數(shù)器控制的循環(huán)*/main（） int counter; /*控制變量的初始化、循環(huán)條件、循環(huán)計(jì)數(shù)器*/ /*值的遞增（遞減）都包含在for結(jié)構(gòu)的頭部*/ for （counter = 1; counter=10;

49、 counter+） printf(“%dn”,counter)for循環(huán)指定了計(jì)數(shù)循環(huán)所需的每一方面的內(nèi)容for語(yǔ)句116for語(yǔ)句的一般格式： 表達(dá)式1：初始化循環(huán)控制變量 表達(dá)式2：循環(huán)條件 表達(dá)式3：遞增（遞減）循環(huán)控制變量的值for （表達(dá)式1; 表達(dá)式2; 表達(dá)式3） 語(yǔ)句表達(dá)式1； while（表達(dá)式2) 語(yǔ)句組； 表達(dá)式3；大多數(shù)情況下for語(yǔ)句等價(jià)于以下的while語(yǔ)句：例外情況：當(dāng)for循環(huán)體中有continue語(yǔ)句時(shí)，以后會(huì)講for語(yǔ)句1174.4 for循環(huán)結(jié)構(gòu)表達(dá)式1和表達(dá)式3可以是用逗號(hào)格開(kāi)的表達(dá)式列表。 如：for(i=1,j=50;i=20;i=i+1, j =

50、 j-5 )在for結(jié)構(gòu)中，表達(dá)式1和表達(dá)式3部分應(yīng)該只放置包含控制變量的表達(dá)式。對(duì)其他變量的操作應(yīng)該放在循環(huán)體之前或循環(huán)體之后；循環(huán)控制條件要防止“丟一錯(cuò)誤”，盡量用=)而不用)。如counter=10,而不寫(xiě)成counter11；for結(jié)構(gòu)中的三個(gè)表達(dá)式是可有可無(wú)的：如果在程序的其他地方初始化了控制變量，則可以省去表達(dá)式1；如果省略了表達(dá)式2，則假定條件為真，建立了一個(gè)“無(wú)限循環(huán)”；如果在for結(jié)構(gòu)體中計(jì)算了遞增（遞減）表達(dá)式或者不需要遞增（遞減）表達(dá)式，則可以省去表達(dá)式3。for （表達(dá)式1; 表達(dá)式2; 表達(dá)式3）118例：求n！#include main() int i;/for循環(huán)

51、控制變量 int n;/求n! long long int mul;/存放求階乘結(jié)果 scanf(%d,&n); for(i=1, mul=1; i=n; i+)/求階乘 mul=mul*i; printf(%d!=%ld,n,mul); system(pause); return 0;i=1;mul=1;while (i=n) mul=mul*i; i=i+1; 為了算法表達(dá)的清晰性，可以采用下述表達(dá)方式：119/*讀程序，寫(xiě)出運(yùn)行結(jié)果*/#include main() int high,mid,low; int count=0; for(high=5; high=7; high+) for

52、(mid=5; mid=7; mid+) for(low=5; low=7; low+) printf(%d,%d,%d,high,mid,low); system(pause); return 0; 120窮舉法解題窮舉法解題 解題思路：對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，從中找出那些符合要求的候選解作為問(wèn)題的解。如：打印所有除以11后所得商正好是它的各個(gè)數(shù)字平方和的三位數(shù) 。121窮舉法解題 例1：編寫(xiě)程序，求出所有5、6、7組成的、且各位數(shù)字互不相同的三位數(shù)。 明確所有的組合情況百位可以是5,6,7十位可以是5,6,7個(gè)位可以是5,6,7檢查是否滿(mǎn)足約束條件百、十、個(gè)位互

53、不相同對(duì)候選解進(jìn)行檢驗(yàn)并輸出122窮舉法解題算法優(yōu)化：【程序演示】1235、6、7組成的數(shù)#include main() int high,mid,low;/依次記錄最高位、中間位、最低位數(shù)字 int count=0; printf(5、6、7可組成的且各位數(shù)字互不相同的數(shù)有：n) ; for(high=5; high=7; high+) for(mid=5; mid=7; mid+) if(high!=mid) for(low=5; low=7; low+) if(low!=high & low!=mid) count+; printf(%dt,high*100+mid*10+low); i

54、f(count%3=0) printf(n); system(pause); return 0; 124窮舉法解題例2：5位跳水高手將參加10m高臺(tái)跳水決賽，好事者讓5人據(jù)實(shí)力預(yù)測(cè)比賽結(jié)果。A選手說(shuō)：B第二，我第三；B選手說(shuō)：我第二，E第四；C選手說(shuō)：我第一，D第二；D選手說(shuō)：C最后，我第三；E選手說(shuō)：我第四，A第一。決賽成績(jī)公布后，每位選手的預(yù)測(cè)都說(shuō)對(duì)了一半，即一對(duì)一錯(cuò)。請(qǐng)?jiān)O(shè)計(jì)算法求出比賽的實(shí)際名次。125明確組合情況：A可以是第一、第二、第三、第四或者第五B可以是第一、第二、第三、第四或者第五C可以是第一、第二、第三、第四或者第五D可以是第一、第二、第三、第四或者第五E可以是第一、第二、第

55、三、第四或者第五檢查是否滿(mǎn)足約束條件：A說(shuō)：B第二，A第三；B說(shuō)：B第二，E第四；C說(shuō)：C第一，D第二；D說(shuō)：C第五，D第三；E說(shuō)：E第四，A第一。而且都只說(shuō)對(duì)了一半。窮舉法解題126例2算法主體框架127檢測(cè)條件：A說(shuō)：B第二，A第三；B說(shuō)：B第二，E第四；C說(shuō)：C第一，D第二；D說(shuō)：C第五，D第三；E說(shuō)：E第四，A第一。而且都只說(shuō)對(duì)了一半。(b=2 & a!=3 | b!=2 & a=3) &(b=2 & e!=4 | b!=2 & e=4) &(c=1 & d!=2 | c!=1 & d=2) &(c=5 & d!=3 | c!=5 & d=3) &(e=4 & a!=1 | e!=4

56、& a=1)countA=(b=2)+(a=3);countB=(b=2)+(e=4);countC=(c=1)+(d=2);countD=(c=5)+(d=3);countE=(e=4)+(a=1);if (countA=1 & countB=1 & countC=1 & countD=1 & countE=1)128比賽名次-1main() int a,b,c,d,e;/用于記錄AE分別的名次 int countA,countB,countC,countD,countE;/用于記錄AE分別說(shuō)對(duì)的話(huà)個(gè)數(shù) for(a=1;a=5;a+)/ae分別代表AE選手的名次 for(b=1;b=5;b+

57、) if (a!=b) for(c=1;c=5;c+)if (c!=a &c!=b) for(d=1;d=5;d+) if (d!=a & d!=b & d!=c) for(e=1;e=5;e+) if (e!=a & e!=b & e!=c & e!=d) if (b=2 & a!=3 | b!=2 & a=3) & (b=2 & e!=4 | b!=2 & e=4) & (c=1 & d!=2 | c!=1 & d=2) & (c=5 & d!=3 | c!=5 & d=3) & (e=4 & a!=1 | e!=4 & a=1) printf(比賽名次是:n); printf(A:第%d

58、名nB:第%d名nC:第%d名nD:第%d名nE:第%d名n,a,b,c,d,e); /if system(pause); return 0; 129比賽名次-2main() int a,b,c,d,e;/用于記錄AE分別的名次 int countA,countB,countC,countD,countE;/用于記錄AE分別說(shuō)對(duì)的話(huà)個(gè)數(shù) for(a=1;a=5;a+)/ae分別代表AE選手的名次 for(b=1;b=5;b+) if (a!=b) for(c=1;c=5;c+)if (c!=a &c!=b) for(d=1;d=5;d+) if (d!=a & d!=b & d!=c) for

59、(e=1;e=5;e+) if (e!=a & e!=b & e!=c & e!=d) countA=(b=2)+(a=3); countB=(b=2)+(e=4); countC=(c=1)+(d=2); countD=(c=5)+(d=3); countE=(e=4)+(a=1); if (countA=1 & countB=1 & countC=1 & countD=1 & countE=1) printf(比賽名次是:n); printf(A:第%d名nB:第%d名nC:第%d名nD:第%d名nE:第%d名n,a,b,c,d,e); /if /if system(pause); return 0; 130練習(xí)：百雞問(wèn)題：用100元買(mǎi)100只雞，大公雞5元1只，母雞3元1只，小雞1元3只。問(wèn)各能買(mǎi)多少只？main() int cocks,hens,chicken; for(cocks=0;cocks=20;cocks+) for(hens=0;hens=34;hens+) for(chicken=0;chicken=100;chicken+=3) if (cocks+hens+chicken=1