第3章 算法與程序設計

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

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

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

迭代公式

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

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