第3章 算法與程序設(shè)計(jì)

算法與程序設(shè)計(jì)第3章講課人：***目錄01中國古典數(shù)學(xué)02算法概述03算法策略04經(jīng)典算法設(shè)計(jì)05程序設(shè)計(jì)知識導(dǎo)圖本章節(jié)主要為同學(xué)們介紹算法及程序設(shè)計(jì)的相關(guān)知識。程序員的主要任務(wù)是根據(jù)用戶的需求為計(jì)算機(jī)設(shè)計(jì)算法。計(jì)算機(jī)的工作特點(diǎn)是可以快速地重復(fù)，因此，算法多是“重復(fù)”，表現(xiàn)為循環(huán)和遞歸。循環(huán)是有條件的重復(fù)。窮舉與迭代最常見。嵌套的循環(huán)往往意味著“自頂向下，逐步求精”，多用于處理復(fù)雜的問題。遞歸算法是“規(guī)模上”的重復(fù)，可完美解決特定的問題。本章最后簡要介紹了一些常見的查找與排序算法及程序設(shè)計(jì)語言。本章內(nèi)容中國古典數(shù)學(xué)第3章01作為世界四大文明古國之一，中國從很早開始就發(fā)展出了自己的數(shù)學(xué)體系。商代的甲骨文上出現(xiàn)了完整的十進(jìn)制，春秋時(shí)代嚴(yán)格的籌算已經(jīng)成型并得到了廣泛的應(yīng)用，戰(zhàn)國時(shí)代《考工記》中實(shí)用的幾何知識流傳到今天?！稄埱鸾ㄋ憬?jīng)》：最小公倍數(shù)的應(yīng)用、等差數(shù)列各元素互求、“百雞術(shù)”。《周髀算經(jīng)》：勾股術(shù)?！毒耪滤阈g(shù)》：開平方和開立方的方法、一般一元二次方程(首項(xiàng)系數(shù)不是負(fù))的數(shù)值解法?！逗u算經(jīng)》：“割圓術(shù)”開創(chuàng)了中國古代圓周率計(jì)算方面的重要方法。算法概述第3章023.2.1算法的概念所謂算法，就是指完成某一特定任務(wù)所需要的具體方法和步驟的有序集合。“有序”說明算法中的步驟是有順序關(guān)系的。同時(shí)，算法所描述的步驟也應(yīng)該是“明確的”和“可執(zhí)行的”，這樣算法才可以實(shí)現(xiàn)。著名的計(jì)算機(jī)科學(xué)家尼古拉斯·沃斯（NiklausWirth）曾提出一個(gè)著名的公式：

程序=算法+數(shù)據(jù)結(jié)構(gòu)3.2.2算法的特征有窮性（Finiteness）確切性（Definiteness）輸入項(xiàng)（Input）輸出項(xiàng)（Output）可行性（Effectiveness）3.2.3算法的描述1.自然語言表示法2.偽代碼表示法3.流程圖表示法4.N-S圖表示法算法策略第3章033.3.1循環(huán)計(jì)算機(jī)的工作特點(diǎn)是可以高速地重復(fù)，因此在設(shè)計(jì)算法時(shí)常用循環(huán)（特定條件下的重復(fù)）解決問題。1.模擬重復(fù)以編程計(jì)算1+2+3+…+100的和為例來說明如用循環(huán)解決問題。先求1+2+3+4+5的和。1+2+3+4+5=3+3+4+5=6+4+5=10+5=15整個(gè)計(jì)算過程就是重復(fù)算加法。什么數(shù)在相加呢？前一次的和與新的加數(shù)。用存儲(chǔ)單元sum存儲(chǔ)和，存儲(chǔ)單元i存儲(chǔ)加數(shù)，計(jì)算過程就是把把sum中的數(shù)與i中的數(shù)相加，結(jié)果還存入sum中。這個(gè)過程可記為sum=sum+i;。人工計(jì)算

1+2+3+4+5=3+3+4+5=6+4+5=10+5=15代碼命令sum=1,i=2;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;計(jì)算過程的模擬用循環(huán)計(jì)算sum=1,i=2;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;sum=sum+i;i=i+1;intsum=1,i=2;while(i<=5){sum=sum+i;i=i+1;}1+2+3+4+5intsum=1,i=2;while(i<=5){sum=sum+i;i=i+1;}1+2+3+…+100intsum=1,i=2;while(i<=100){sum=sum+i;i=i+1;}用循環(huán)計(jì)算1+2+3+…+1002.窮舉與迭代嘗試所有可能的選項(xiàng)以找到正確答案的方法又稱為窮舉法。一百個(gè)僧人分一百個(gè)饅頭，大僧每人分三個(gè)，小僧三人分一個(gè)，正好分完。問大小僧各幾人？嘗試所有的可能。大僧1人時(shí)，小僧（100-1）人，需要饅頭3*1+(100-1)/3個(gè)，如果饅頭的個(gè)數(shù)等于100，就找到了答案，輸出大小僧的人數(shù)；否則，就不輸出。大僧2人時(shí)，小僧（100-2）人，需要饅頭3*2+(100-2)/3個(gè)，如果饅頭的個(gè)數(shù)等于100，就找到了答案，輸出大小僧的人數(shù)；否則，就不輸出。……大僧33人時(shí)，小僧（100-33）人，需要饅頭3*33+(100-33)/3個(gè)，如果饅頭的個(gè)數(shù)等于100，就找到了答案，輸出大小僧的人數(shù)；否則，就不輸出。窮舉法整個(gè)過程可描述為。//大僧1人時(shí)當(dāng)3*1+(100-1)/3==100時(shí)，輸出大僧:1,小僧:100-1;//大僧2人時(shí)當(dāng)3*2+(100-2)/3==100時(shí)，輸出大僧:2,小僧:100-2;……//大僧33人時(shí)當(dāng)3*33+(100-33)/3==100時(shí)，輸出大僧:33,小僧:100-33;顯然大僧的人數(shù)在重復(fù)，從1重復(fù)到33。用存儲(chǔ)單元i存放大僧的人數(shù)，初值設(shè)置為1，如i<=33成立，重復(fù)下面的兩步：當(dāng)3*i+(100-i)/3==100時(shí)，輸出大僧:i,小僧:100-i;i=i+1;一百個(gè)僧人分一百個(gè)饅頭inti=1;while(i<=33){if(3*i+(100-i)/3==100)printf("大僧:%d,小僧:%d\n",i,100-i);i=i+1;}迭代法

迭代公式

3.自頂向下，逐步求精“自頂向下，逐步求精”是分析解決復(fù)雜問題行之有效的方法。“自頂向下”要求從宏觀上分析，不拘泥于細(xì)節(jié)，理清脈絡(luò)把握問題的本質(zhì)；“逐步求精”要求從局部著力，從細(xì)節(jié)入手，分析問題的獨(dú)特性，針對具體問題，列舉“原始數(shù)據(jù)”發(fā)現(xiàn)“規(guī)律”，最終解決問題。用循環(huán)輸出如下圖形圖形共5行，輸出第1行；輸出第2行；輸出第3行；輸出第4行；輸出第5行。這個(gè)過程是重復(fù)，“行”在重復(fù)，重復(fù)了5次。這個(gè)過程可用圖表示第i行什么樣子呢？第1行有一個(gè)“空格星號*”和一個(gè)換行符，第2行有2個(gè)“空格星號*”和一個(gè)換行符，……，因此第i行有i個(gè)“空格星號*”和一個(gè)換行符。怎樣輸出i個(gè)“空格星號*”呢？輸出第1個(gè)“空格星號*”，輸出第2個(gè)，

輸出第3個(gè)，……，輸出第i個(gè)?？梢娸敵龅趇行的過程是重復(fù)，可以用圖表示。用循環(huán)輸出如下圖形inti,j;i=1;while(i<=5){j=1;while(j<=i){

printf("*");j=j+1;}printf("\n");i=i+1;}用循環(huán)輸出如下圖形如果忽略細(xì)節(jié)，則這個(gè)圖形也有5行，依然是輸出第1行；輸出第2行；輸出第3行；輸出第4行；輸出第5行。這個(gè)過程是重復(fù)，“行”在重復(fù)，重復(fù)了5次。這個(gè)過程依然可用圖表示。第i行什么樣子呢？第1行有4個(gè)“空格空格”、一個(gè)“空格星號*”和一個(gè)換行符，第2行有3個(gè)“空格空格”、3個(gè)“空格星號*”和一個(gè)換行符，……，因此第i行有5-i個(gè)“空格空格”、2*i-1個(gè)“空格星號*”和一個(gè)換行符?？梢韵容敵?-i個(gè)“空格空格”，再輸出2*i-1個(gè)“空格星號*”，最后輸出一個(gè)換行符。這個(gè)過程可用圖表示。用循環(huán)輸出如下圖形自頂向下，逐步求精當(dāng)忽略細(xì)節(jié)從宏觀上看時(shí)，兩個(gè)圖形的形狀“相同”，都有五行，可以用相同的循環(huán)結(jié)構(gòu)輸出。重復(fù)5次，每次輸出一行，即輸出第i行。這種把握本質(zhì)忽略細(xì)節(jié)的分析方法可稱為“自頂向下”。在確定第i行是什么樣子時(shí)，從第1行的具體形狀開始，依次分析每行的具體形狀，關(guān)注細(xì)節(jié)，在綜合“原始數(shù)據(jù)”的基礎(chǔ)上總結(jié)出規(guī)律，即第i行的形狀?！瓣P(guān)注細(xì)節(jié)”恰恰是進(jìn)一步（“逐步求精”）分析時(shí)所強(qiáng)調(diào)的。3.3.2遞歸分析問題時(shí)經(jīng)常發(fā)現(xiàn)，一些難以直接解決的規(guī)模較大的問題，往往可以轉(zhuǎn)化為一些規(guī)模較小且與原問題性質(zhì)相同的子問題。問題的難易程度通常與其規(guī)模相關(guān)，問題的規(guī)模越小，問題就越容易解決。以求523的階乘為例，523！等于523×522！，原問題變成了523乘以522的階乘。雖然還需計(jì)算乘法，但只要知道了522的階乘，進(jìn)行一次乘法運(yùn)算求出523的階乘應(yīng)該不難。與原問題相比，現(xiàn)在問題的關(guān)鍵依然是求一個(gè)數(shù)的階乘，問題的性質(zhì)沒有變，不過，原來需求523的階乘，現(xiàn)在只要求出522的階乘即可，問題的規(guī)模變小了，難度降低了。遞歸與原問題性質(zhì)相同就意味著子問題可以繼續(xù)轉(zhuǎn)化為規(guī)模更小性質(zhì)相同的子問題，新得到的子問題還可以繼續(xù)轉(zhuǎn)化，……，只要性質(zhì)相同，轉(zhuǎn)化的過程就可以一直重復(fù)下去。當(dāng)轉(zhuǎn)化后子問題的規(guī)模小到可以很容易地求解時(shí)，轉(zhuǎn)化的過程就可以停止了。子問題有解后，就可以按照轉(zhuǎn)化的過程逆向求解，每次都得到規(guī)模稍大一點(diǎn)的子問題的解，最終就能得到原問題的解。原問題轉(zhuǎn)化子問題的過程可稱為遞進(jìn)；由子問題的解構(gòu)造原問題的解的過程可稱為回歸。通過遞進(jìn)和回歸兩個(gè)過程解決問題的方法稱為“遞歸”。用遞歸算法求階乘設(shè)函數(shù)fac可以求出整數(shù)n的階乘，該函數(shù)的首部為intfac(intn)。求2的階乘時(shí)用fac(2)；fac(2)的執(zhí)行結(jié)果就是2的階乘。實(shí)現(xiàn)遞歸算法時(shí)一定要轉(zhuǎn)化為規(guī)模較小的子問題呢？那倒未必。如果整數(shù)n的規(guī)模已經(jīng)小到能輕易地求出它的階乘時(shí)（如0或1），就不再需要轉(zhuǎn)化的過程了，直接返回結(jié)果；否則，求整數(shù)n的階乘需要轉(zhuǎn)化成求n-1的階乘，返回n*(n-1)!的值。函數(shù)可定義為：用遞歸算法求階乘C語言中有乘法命令，但沒有求整數(shù)階乘的命令，怎樣命令計(jì)算機(jī)求出(n-1)的階乘呢？函數(shù)fac的功能是求一個(gè)整數(shù)的階乘，函數(shù)是C語言中的自定義命令，可以用函數(shù)fac命令計(jì)算機(jī)求出(n-1)的階乘。fac(n)的返回值為n的階乘，相應(yīng)地fac(n-1)的返回值就是(n-1)的階乘。求出了(n-1)的階乘，函數(shù)fac也就定義好了。使用fac函數(shù)求3的階乘可以使用fac函數(shù)求出3的階乘。printf("3!=%u\n",fac(3));，語句的運(yùn)行結(jié)果為：遞歸示例樓梯有n階臺階，上樓時(shí)一步可以上1階，也可以上2階，計(jì)算n階樓梯共有多少種不同的走法。分析：設(shè)n階臺階的走法為f(n)，當(dāng)樓梯只有1階時(shí)，顯然只有一種走法，f(1)=1。只有2階時(shí)，有兩種走法，一步一階地或一步兩階地走上樓梯,f(2)=2。樓梯多于2階的時(shí)，有幾種走法呢？遞歸示例上樓梯時(shí)，第一步可以上1階也可以上2階并且只有這兩種情況，也就是說，樓梯的所有不同走法等于這兩種情況下上完整個(gè)樓梯的不同走法之和，即f(n)等于第一步上1階時(shí)的走法加上第一步上2階時(shí)的走法。第一步上1階時(shí)上完整個(gè)樓梯的走法有多少種呢？它等于余下的n-1階臺階的所有不同走法，于是問題變成了上有n-1階臺階的樓梯有多少種走法？性質(zhì)相同，規(guī)模變小了。n階臺階的走法為f(n)，所以上n-1階臺階的樓梯共有f(n-1)種走法。4階樓梯的走法棋盤覆蓋問題問題描述：在一個(gè)2k×2k個(gè)方格組成的棋盤中，有一個(gè)帶有特殊標(biāo)記的方格。要求是用4種不同形態(tài)的L型骨牌覆蓋棋盤上除特殊方格以外的所有方格，在覆蓋時(shí)L型骨牌不能重疊。如圖所示。棋盤覆蓋問題首先，解決如何在程序中表示棋盤的問題?？梢杂靡粋€(gè)二維整型數(shù)組表示棋盤，如上面的棋盤可表示為：intchessboard[4][4]={0};，把特殊方格對應(yīng)的元素賦值為-1（chessboard[0][1]=-1），則數(shù)組元素輸出后即可形成棋盤形狀，棋盤覆蓋問題其次，表示L型骨牌的覆蓋。把同一個(gè)L型骨牌覆蓋的方格賦值為同一個(gè)整數(shù)，輸出時(shí)用相同的數(shù)字模擬骨牌的形狀。棋盤覆蓋問題第一步：把棋盤一分為4，形成4個(gè)2k-1×2k-1個(gè)方格組成棋盤。如圖所示。棋盤覆蓋問題第二步：觀察大棋盤中心位置的四個(gè)小方格，它們分屬四個(gè)小棋盤，會(huì)發(fā)現(xiàn)其中一個(gè)小方格所在的小棋盤與其它三個(gè)不同，因?yàn)樗颂厥夥礁瘛Ｆ灞P覆蓋問題第三步：不考慮包含了特殊方格的小棋盤中的小方格，剩下的三個(gè)小方格恰好構(gòu)成一個(gè)L型骨牌，用相同的數(shù)字標(biāo)記這三個(gè)小方格，完成一個(gè)L型骨牌的覆蓋，如圖所示。棋盤覆蓋問題第四步：觀察這四個(gè)小棋盤會(huì)發(fā)現(xiàn)它們都是一個(gè)2n×2n（n的值為k-1）個(gè)方格組成的棋盤，且棋盤中都有一個(gè)帶有特殊標(biāo)記的方格，即黑色的方格（在程序中為非0的方格）?，F(xiàn)在的任務(wù)是用L型骨牌覆蓋這四個(gè)小棋盤，如圖所示。棋盤覆蓋問題依次用L型骨牌覆蓋這四個(gè)小棋盤。先處理左上角的小棋盤。左上角的小棋盤由21×21個(gè)方格和一個(gè)特殊方格組成。任務(wù)相同，規(guī)模變小，可以用遞歸算法處理。其它三個(gè)小棋盤也用遞歸算法處理，任務(wù)完成。為便于初學(xué)者理解，下面詳細(xì)分析一下用遞歸算法處理左上角小棋盤的過程。棋盤由21×21個(gè)方格組成，k的值為1，規(guī)模還是較大，應(yīng)繼續(xù)依照前面的步驟處理，即先把棋盤一分為四，如圖所示。棋盤覆蓋問題不考慮含有特殊方格小棋盤中的小方格，完成一個(gè)L型骨牌的覆蓋恰好構(gòu)成一個(gè)L型骨牌，用相同的數(shù)字標(biāo)識這三個(gè)方格，完成一個(gè)L型骨牌的覆蓋，棋盤覆蓋問題圖中的四個(gè)小棋盤均由一個(gè)小空格組成，處理這個(gè)四個(gè)小棋盤時(shí)依然要一分為四。左上角由一個(gè)小空格組成棋盤一分為四時(shí)，它們由20×20個(gè)方格組成，k的值為0，顯然還是一個(gè)棋盤，且這個(gè)小空格還是特殊方格，因此，當(dāng)k的值為0時(shí)，無須繼續(xù)處理，不用再“遞推”了。至此，左上角的小棋盤完成了覆蓋。棋盤覆蓋問題對于由2k×2k個(gè)方格組成的棋盤，如果k的值等于0，則棋盤由特殊方格組成無須覆蓋，直接返回；否則，先把這個(gè)棋盤一分為四，找到中心位置的四個(gè)小方格，不考慮包含了特殊方格的小棋盤中的小方格，剩下的三個(gè)小方格恰好構(gòu)成一個(gè)L型骨牌，用相同的數(shù)字標(biāo)識標(biāo)識這些小方