第四章算法設(shè)計與應(yīng)用

1、第四章第四章 算法設(shè)計與應(yīng)用算法設(shè)計與應(yīng)用 Page 2任務(wù)任務(wù) 4.1猴子吃桃問題猴子吃桃問題 Page 34.1.1 案例描述案例描述題目：題目：猴子吃桃問題：猴子第一天摘下若干個桃子，當(dāng)即吃了猴子吃桃問題：猴子第一天摘下若干個桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個一半，還不過癮，又多吃了一個; ;第二天早上又將剩下的第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第一天剩下的一半零一個。到第1010天早上想再吃時，見只天早上想再吃時，見只剩下一個桃子了。求第一天共摘了多少剩下一個桃子了。求第一

2、天共摘了多少? ? Page 44.1.2 案例分析案例分析問題規(guī)律：每天的桃子數(shù)是第問題規(guī)律：每天的桃子數(shù)是第2 2天桃子數(shù)加天桃子數(shù)加1 1后的后的2 2倍。倍。假設(shè)假設(shè)a(ia(i) )表示第表示第i i天的桃子數(shù)，則：天的桃子數(shù)，則：a(1)=(a(2)+1)*2a(2)=(a(3)+1)*2a(3)=(a(4)+1)*2a(4)=(a(5)+1)*2a(8)=(a(9)+1)*2a(9)=(a(10)+1)*2a(10)=1f(n)=(f(n+1)+1)*2 1=n10 f(n)=1 n=10解決思路：解決思路：遞歸算法遞歸算法Page 54.1.3 知識準(zhǔn)備知識準(zhǔn)備1 1、算法、算

3、法（1 1）算法的定義）算法的定義：是對特定問題求解步驟的一種描述：是對特定問題求解步驟的一種描述, ,是一個有窮是一個有窮的指令集，這些指令表示一個或多個操作。的指令集，這些指令表示一個或多個操作。（2 2）算法的特性）算法的特性( (要素要素) )：有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束, ,且每一步都在有窮時間內(nèi)且每一步都在有窮時間內(nèi)完成。完成。確定性確定性 每步定義都是確切、無歧義的。每步定義都是確切、無歧義的。可行性可行性 算法中描述的操作應(yīng)能通過執(zhí)行有限次已經(jīng)實現(xiàn)的基算法中描述的操作應(yīng)能通過執(zhí)行有限次已經(jīng)實現(xiàn)的基本運算而實現(xiàn)。本運算而實現(xiàn)。輸入輸入 有有0

4、0個或多個輸入。個或多個輸入。輸出輸出 有一個或多個輸出有一個或多個輸出( (處理結(jié)果處理結(jié)果) )。Page 64.1.3 知識準(zhǔn)備知識準(zhǔn)備（3 3）算法設(shè)計的要求）算法設(shè)計的要求正確性正確性：不含有語法錯誤；對于各種合法的輸入數(shù)據(jù)能夠得：不含有語法錯誤；對于各種合法的輸入數(shù)據(jù)能夠得到滿足規(guī)格說明要求的結(jié)果。到滿足規(guī)格說明要求的結(jié)果?？勺x性可讀性：要求程序有較好的人機(jī)交互性：要求程序有較好的人機(jī)交互性, ,有助于人們對算法有助于人們對算法的理解。的理解。健壯性健壯性：對輸入的非法數(shù)據(jù)能作出適當(dāng)?shù)捻憫?yīng)或處理。：對輸入的非法數(shù)據(jù)能作出適當(dāng)?shù)捻憫?yīng)或處理。效率與低存儲需求效率與低存儲需求：主要指算法

5、的執(zhí)行時間和所需的最大存：主要指算法的執(zhí)行時間和所需的最大存儲空間，這兩方面主要和問題的規(guī)模有關(guān)。儲空間，這兩方面主要和問題的規(guī)模有關(guān)。Page 74.1.3 知識準(zhǔn)備知識準(zhǔn)備（4 4）算法性能分析與度量）算法性能分析與度量 一個算法的優(yōu)劣可以從算法的一個算法的優(yōu)劣可以從算法的時間復(fù)雜度時間復(fù)雜度與與空間復(fù)雜度空間復(fù)雜度來評價。來評價。 時間復(fù)雜度：時間復(fù)雜度：算法的執(zhí)行時間是依據(jù)該算法編制的程序在算法的執(zhí)行時間是依據(jù)該算法編制的程序在計算機(jī)上運行時所消耗的時間來度量。計算機(jī)上運行時所消耗的時間來度量。通常把算法中進(jìn)行簡單通常把算法中進(jìn)行簡單操作的次數(shù)的多少操作的次數(shù)的多少稱為算法的時間復(fù)稱為

6、算法的時間復(fù)雜度，這是一個算法執(zhí)行時間的相對度量，它可估算出當(dāng)雜度，這是一個算法執(zhí)行時間的相對度量，它可估算出當(dāng)問題的規(guī)模變大時，算法運行時間增長的速度，這種分析問題的規(guī)模變大時，算法運行時間增長的速度，這種分析實際上是一種數(shù)學(xué)化的實際上是一種數(shù)學(xué)化的估算估算方法。方法。Page 84.1.3 知識準(zhǔn)備知識準(zhǔn)備 通常的做法是：從算法中選取一種對于所研究的問題來通常的做法是：從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該說是基本運算的原操作，以該原操作重復(fù)執(zhí)行的次數(shù)原操作重復(fù)執(zhí)行的次數(shù)作為作為算法的時間度量。算法的時間度量。若所解決的問題的數(shù)據(jù)規(guī)模（數(shù)據(jù)量）為若所解決的問題的數(shù)據(jù)規(guī)

7、模（數(shù)據(jù)量）為n n，那么算法的時，那么算法的時間復(fù)雜度就是數(shù)據(jù)規(guī)模間復(fù)雜度就是數(shù)據(jù)規(guī)模n n的一個函數(shù)的一個函數(shù)f(nf(n) )，假定時間復(fù)雜度，假定時間復(fù)雜度記作記作T(nT(n) )，則：，則： T(n) (f(n)Page 94.1.3 知識準(zhǔn)備知識準(zhǔn)備加法規(guī)則加法規(guī)則 針對并列程序段針對并列程序段 T(T(n n, , m m) = T1 () = T1 (n n) + T2 () + T2 (m m) ) = = O(maxO(max ( (f f ( (n n), ), g g ( (m m)乘法規(guī)則乘法規(guī)則 針對嵌套程序段針對嵌套程序段 T (n, m) = T1 (n) T

8、 (n, m) = T1 (n) * * T2 (m) T2 (m) = = O(fO(f (n) (n)* *g (m)g (m)Page 10 x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)4.1.3 知識準(zhǔn)備知識準(zhǔn)備Page 114.1.3 知識準(zhǔn)備

9、知識準(zhǔn)備空間復(fù)雜度空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大是對一個算法在運行過程中臨時占用存儲空間大小的度量，記作：小的度量，記作： S(nS(n) = ) = O(g(nO(g(n) 表示隨著問題規(guī)模表示隨著問題規(guī)模n n的增大，算法運行所需存儲量的增長率的增大，算法運行所需存儲量的增長率與與g(ng(n) )的增長率相同。的增長率相同。算法的存儲量包括：算法的存儲量包括：輸入數(shù)據(jù)所占空間輸入數(shù)據(jù)所占空間; ; 程序本身所占空間；程序本身所占空間； 輔助變量所占空間。輔助變量所占空間。 Page 124.1.3 知識準(zhǔn)備知識準(zhǔn)備說明：說明： 算法的所有性能之間都存在著或多或少的相

10、互影響，算法的所有性能之間都存在著或多或少的相互影響，因此，當(dāng)設(shè)計一個算法，特別是大型算法時，要綜合考慮因此，當(dāng)設(shè)計一個算法，特別是大型算法時，要綜合考慮算法的各項性能、算法的使用頻率、算法處理的數(shù)據(jù)量的算法的各項性能、算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性及算法運行的機(jī)器系統(tǒng)環(huán)境等大小、算法描述語言的特性及算法運行的機(jī)器系統(tǒng)環(huán)境等各方面因素，才能設(shè)計出比較好的算法。各方面因素，才能設(shè)計出比較好的算法。 Page 134.1.3 知識準(zhǔn)備知識準(zhǔn)備u若一個算法直接或間接的若一個算法直接或間接的調(diào)用自己本身調(diào)用自己本身，則稱這個算法是，則稱這個算法是遞歸算法。遞歸算法。2 2、

11、遞歸、遞歸（1 1）問題的定義是遞推的）問題的定義是遞推的（2 2）問題的解法存在自調(diào)用）問題的解法存在自調(diào)用（1 1）遞歸的定義）遞歸的定義Page 144.1.3 知識準(zhǔn)備知識準(zhǔn)備f(n)=(f(n+1)+1)*2 1=n10 f(n)=1 n=10（2 2）遞歸的執(zhí)行過程（）遞歸的執(zhí)行過程（遞推、回歸遞推、回歸） f(1)f(2)main()(f(3)+1)*2f(3)f(9)f(10)(f(4)+1)*2(f(10)+1)*2return 143827661534遞推遞推回歸回歸(f(2)+1)*2Page 154.1.3 知識準(zhǔn)備知識準(zhǔn)備（3 3）遞歸算法的設(shè)計方法）遞歸算法的設(shè)計方

12、法遞歸算法求解問題的基本思想是：遞歸算法求解問題的基本思想是：對于一個較為復(fù)雜的問題，把原問題分解對于一個較為復(fù)雜的問題，把原問題分解成若干個相對簡單且類同的子問題，這樣較為復(fù)雜的原問題就變成了相對簡成若干個相對簡單且類同的子問題，這樣較為復(fù)雜的原問題就變成了相對簡單的子問題；而簡單到一定程度的子問題可以直接求解；這樣，原問題就可單的子問題；而簡單到一定程度的子問題可以直接求解；這樣，原問題就可遞推得到解。遞推得到解。注意：并不是每個問題都適宜于用遞歸算法求解。適宜于用遞歸算法求解的注意：并不是每個問題都適宜于用遞歸算法求解。適宜于用遞歸算法求解的問題的問題的充分必要條件充分必要條件是：是：（

13、1 1）問題具有某種可借用的類同自身的子問題描述的性質(zhì)；）問題具有某種可借用的類同自身的子問題描述的性質(zhì)；（2 2）某一有限步的子問題有直接的解存在。）某一有限步的子問題有直接的解存在。當(dāng)一個問題存在上述兩個基本要素時，設(shè)計該問題的當(dāng)一個問題存在上述兩個基本要素時，設(shè)計該問題的遞歸算法的方法遞歸算法的方法是：是：（1 1）把對原問題的求解設(shè)計成包含有對子問題求解的形式（）把對原問題的求解設(shè)計成包含有對子問題求解的形式（遞歸步驟遞歸步驟）。）。（2 2）設(shè)計遞歸出口（）設(shè)計遞歸出口（停止條件停止條件）。）。相似性相似性出口出口Page 164.1.3 知識準(zhǔn)備知識準(zhǔn)備 設(shè)計遞歸算法時，必須小心區(qū)

14、分停止條件和遞歸步驟，設(shè)計遞歸算法時，必須小心區(qū)分停止條件和遞歸步驟，一般使用一般使用if-else語法來實現(xiàn)這個區(qū)別。語法來實現(xiàn)這個區(qū)別。 （4 4）遞歸算法的實現(xiàn)）遞歸算法的實現(xiàn) 遞歸主要用于解決用于采用迭代處理進(jìn)行設(shè)計和實現(xiàn)的問遞歸主要用于解決用于采用迭代處理進(jìn)行設(shè)計和實現(xiàn)的問 題。題。（5 5）遞歸的應(yīng)用）遞歸的應(yīng)用Page 174.1.4 案例實現(xiàn)案例實現(xiàn)#includeint f( int n ) if(n=1&n1n!= 1 n=0n*(n-1) ！ n1f(n)= 1 n=0n*f(n-1) n14.1.5 拓展訓(xùn)練拓展訓(xùn)練1 1、求一個非負(fù)整數(shù)、求一個非負(fù)整數(shù)n n的

15、階乘。的階乘。階乘的公式：階乘的公式：n!=n * (n-1)* (n-2) * .*2*1 Page 194.1.5 拓展訓(xùn)練拓展訓(xùn)練#includeint f(int n) if(n0) printf(ERRORn); if(n=1|n=0) return 1; else return f(n-1)*n;void main() int n; printf(請輸入一個正整數(shù)請輸入一個正整數(shù):n); scanf(%d,&n); printf(%d的階乘是的階乘是%dn,n,f(n);Page 204.1.5 拓展訓(xùn)練拓展訓(xùn)練2 2、設(shè)計求解委員會問題的算法。、設(shè)計求解委員會問題的算法。

16、委員會問題是：從一個有委員會問題是：從一個有n n個人的團(tuán)體中抽出個人的團(tuán)體中抽出k(knk(kn) )個人組個人組成一個委員會，計算共有多少種構(gòu)成方法。成一個委員會，計算共有多少種構(gòu)成方法。問題分析問題分析：從：從n n個人中抽出個人中抽出k(knk(kn) )個人的問題是一個組合個人的問題是一個組合問題。把問題。把n n個人固定位置后，從個人固定位置后，從n n個人中抽出個人中抽出k k個人的問題可個人的問題可分解為兩部分之和：第一部分是第一個人包括在分解為兩部分之和：第一部分是第一個人包括在k k個人中，個人中，第二部分是第一個人不包括在第二部分是第一個人不包括在k k個人中。對于第一部

17、分，則個人中。對于第一部分，則問題簡化為從問題簡化為從n-1n-1個人中抽出個人中抽出k-1k-1個人的問題；對于第二部個人的問題；對于第二部分，則問題簡化為從分，則問題簡化為從n-1n-1個人中抽出個人中抽出k k個人的問題。個人的問題。Page 214.1.5 拓展訓(xùn)練拓展訓(xùn)練圖中給出了圖中給出了n=5, k=2n=5, k=2時問題的分解示意圖。時問題的分解示意圖。ABCDEABACADAEBCBDBECDCEDE包含包含A A，選，選1 1個個不包含不包含A A，選，選2 2個個f(n,k)=f(n-1,k-1)+ f(n-1,k) kn1 n=k1 k=0Page 224.1.5 拓

18、展訓(xùn)練拓展訓(xùn)練#includeint f(int n,int k) if(kn|k0|n1) printf(ERRORn); if(k=n|k=0) return 1; else return f(n-1,k-1)+f(n-1,k);void main() printf(從從5個人里找出兩個委員的情況有個人里找出兩個委員的情況有%d種種n,f(5,2);Page 23任務(wù)任務(wù) 4.3百錢買百雞百錢買百雞Page 244.3.1 案例描述案例描述中國古代數(shù)學(xué)家張丘建在他的中國古代數(shù)學(xué)家張丘建在他的算經(jīng)算經(jīng)中提到了一個著中提到了一個著名的名的“百錢買百雞百錢買百雞”問題：雞翁一，值錢五，雞母一，問

19、題：雞翁一，值錢五，雞母一，值錢三，雞雉三，值錢一，百錢買百雞。問翁、母、值錢三，雞雉三，值錢一，百錢買百雞。問翁、母、雉雉各幾何？各幾何？Page 254.3.2 案例分析案例分析 設(shè)雞翁、雞母、雞雉的個數(shù)分別為設(shè)雞翁、雞母、雞雉的個數(shù)分別為x,y,zx,y,z。題意給定共。題意給定共100100錢錢買買100100雞，若買公翁最多是雞，若買公翁最多是2020只，則只，則x x的取值范圍在的取值范圍在0-200-20之間之間；同理；同理y y的取值范圍是的取值范圍是0-330-33之間，可得到以下的不定方程：之間，可得到以下的不定方程： 5x+3y+z/3=100 x+y+z=100 此問題

20、可歸結(jié)為求該不定方程的整數(shù)解。在分析確定方程中此問題可歸結(jié)為求該不定方程的整數(shù)解。在分析確定方程中未知數(shù)變化范圍的前提下，可通過對未知數(shù)可變范圍的未知數(shù)變化范圍的前提下，可通過對未知數(shù)可變范圍的窮舉窮舉，驗證方程在什么情況下成立，從而得到相應(yīng)的解。，驗證方程在什么情況下成立，從而得到相應(yīng)的解。Page 264.3.3 知識準(zhǔn)備知識準(zhǔn)備u 1 1、什么是窮舉算法？、什么是窮舉算法？Page 27u算法簡單，但運行時所花費的時間量大。因此，我們在算法簡單，但運行時所花費的時間量大。因此，我們在用窮舉方法解決問題時，應(yīng)盡可能將明顯的不符合條件用窮舉方法解決問題時，應(yīng)盡可能將明顯的不符合條件的情況排除

21、在外，以盡快取得問題的解。的情況排除在外，以盡快取得問題的解。u適合窮舉策略求解的問題，首先必須滿足其問題規(guī)模和適合窮舉策略求解的問題，首先必須滿足其問題規(guī)模和可能解的規(guī)模（個數(shù)）不是特別大，且解變量的值的變可能解的規(guī)模（個數(shù)）不是特別大，且解變量的值的變化具有一定的規(guī)律性?；哂幸欢ǖ囊?guī)律性。 4.3.3 知識準(zhǔn)備知識準(zhǔn)備2 2、窮舉算法的特點、窮舉算法的特點Page 284.3.3 知識準(zhǔn)備知識準(zhǔn)備u 3 3、窮舉算法模式、窮舉算法模式 1 1、確定、確定問題解的可能搜索范圍：問題解的可能搜索范圍： 用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實現(xiàn)。用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實現(xiàn)。 2 2、寫出符合問題解的判斷條件寫出

22、符合問題解的判斷條件 ( (直接條件和隱含條件直接條件和隱含條件) )。 3 3、使程序優(yōu)化的語句，以便縮小搜索范圍，使程序優(yōu)化的語句，以便縮小搜索范圍， 減少程序運行時間。減少程序運行時間。 Page 294.3.3 知識準(zhǔn)備知識準(zhǔn)備u 4 4、窮舉算法的應(yīng)用、窮舉算法的應(yīng)用 窮舉法應(yīng)用很多，比如一些密碼破譯軟件通常就窮舉法應(yīng)用很多，比如一些密碼破譯軟件通常就是用的窮舉算法。如在是用的窮舉算法。如在QQQQ上，上，OicqPassOverOicqPassOver這個這個工具窮舉你的口令，它根據(jù)機(jī)器性能最高可以每工具窮舉你的口令，它根據(jù)機(jī)器性能最高可以每秒測試秒測試2000020000個口令，

23、如果口令簡單，一分鐘內(nèi)，個口令，如果口令簡單，一分鐘內(nèi)，密碼就會遭到破譯。密碼就會遭到破譯。Page 304.3.4 案例實現(xiàn)案例實現(xiàn)#includevoid main() int x,y,z,n=0;/x表示雞翁，表示雞翁，y表示雞母表示雞母,z表示雞雉表示雞雉 for(x=0;x=20;x+) for(y=0;y=33;y+) z=100-x-y; if(x*5+y*3+z/3=100&z%3=0) printf(第第%d種情況：雞翁種情況：雞翁%d只，雞母只，雞母%d只，雞雉只，雞雉%d只只n,+n,x,y,z);直接條件直接條件隱含條件隱含條件Page 314.3.5 拓展訓(xùn)練

24、拓展訓(xùn)練1 1、阿姆斯特朗數(shù)、阿姆斯特朗數(shù)問題描述：編一個程序找出所有的三位數(shù)到四位數(shù)問題描述：編一個程序找出所有的三位數(shù)到四位數(shù)中的阿姆斯特朗數(shù)。它的定義如下中的阿姆斯特朗數(shù)。它的定義如下: :若一個若一個n n位自然位自然數(shù)的各位數(shù)字的數(shù)的各位數(shù)字的n n次方之和等于它本身次方之和等于它本身, ,則稱這個自則稱這個自然數(shù)為阿姆斯特朗數(shù)。然數(shù)為阿姆斯特朗數(shù)。例如：例如：153(153=1*1*1+3*3*3+5*5*5)是一個三位數(shù)是一個三位數(shù)的阿姆斯特朗數(shù)的阿姆斯特朗數(shù),8208,8208則是一個四位數(shù)的阿姆斯特則是一個四位數(shù)的阿姆斯特朗數(shù)。朗數(shù)。 Page 324.3.5 拓展訓(xùn)練拓展訓(xùn)

25、練算法分析：算法分析：1 1、問題規(guī)模分為兩個區(qū)間：、問題規(guī)模分為兩個區(qū)間：111-999111-999和和1111-99991111-9999；2 2、 對每一個數(shù)要先分離出其各位數(shù)字，然后判斷對每一個數(shù)要先分離出其各位數(shù)字，然后判斷各位數(shù)字的各位數(shù)字的n n次方之和是否等于其本身，若相等，次方之和是否等于其本身，若相等，則輸出，否則，繼續(xù)判斷下一個數(shù)字。則輸出，否則，繼續(xù)判斷下一個數(shù)字。Page 334.3.5 拓展訓(xùn)練拓展訓(xùn)練void main()int i,x,y,z,m,n=0;for(i=111;i=999;i+) x=i/100; y=i%100/10; z=i%10; if(x

26、*x*x+y*y*y+z*z*z=i) printf(%d:%dn,+n,i); for(i=1111;iz&x+zy&z+yx&(x!=y|z!=x|y!=z)&x=y&y=z Page 36#includevoid main()int n,x,y,z,m=0;printf(請輸入一個大于請輸入一個大于3的正整數(shù)的正整數(shù):);scanf(%d,&n);for(x=1;xn;x+) for(y=1;yz&x+zy&z+yx&(x!=y|z!=x|y!=z)&x=y&y=z) printf(%d:%d,%d,

27、%dn,+m,x,y,z);4.3.5 拓展訓(xùn)練拓展訓(xùn)練Page 37任務(wù)任務(wù) 4.4新娘與新郎問題新娘與新郎問題 Page 384.4.1 案例描述案例描述題目：題目： 三對情侶參加婚禮，新郎分別是三對情侶參加婚禮，新郎分別是A,B,CA,B,C，三個新娘為，三個新娘為X,Y,ZX,Y,Z。有人不知道誰和誰結(jié)婚。于是詢問了六位新人中。有人不知道誰和誰結(jié)婚。于是詢問了六位新人中的三位，但聽到的回答是這樣的：的三位，但聽到的回答是這樣的：A A說他將和說他將和X X結(jié)婚，結(jié)婚，X X說說她的未婚夫是她的未婚夫是C C，C C說她將和說她將和Z Z結(jié)婚。這個人聽后覺得是開結(jié)婚。這個人聽后覺得是開玩

28、笑，都是假話。請編程找出誰和誰結(jié)婚玩笑，都是假話。請編程找出誰和誰結(jié)婚? ? Page 394.4.2 案例分析案例分析問題規(guī)律：將問題規(guī)律：將A,B,CA,B,C三人用三人用1 1，2,32,3表示，那么表示，那么X X和和A A結(jié)婚記做：結(jié)婚記做：X=1X=1，X X與與B B結(jié)婚記做結(jié)婚記做X=2X=2，Y Y不與不與A A結(jié)婚記做結(jié)婚記做Y Y！=1=1。則：則：X!=1 AX!=1 A不與不與X X結(jié)婚結(jié)婚X!=3 XX!=3 X的未婚夫不是的未婚夫不是C CZ!=3 ZZ!=3 Z不與不與C C結(jié)婚結(jié)婚X!=Y X!=Y 隱含條件（同性不能結(jié)婚）隱含條件（同性不能結(jié)婚）Y!=Z Y

29、!=Z Z!=XZ!=XPage 404.4.2 案例分析案例分析n 使用窮舉策略，使窮舉變量使用窮舉策略，使窮舉變量x x、y y、z z窮盡三個新郎的編號，構(gòu)造循環(huán)結(jié)窮盡三個新郎的編號，構(gòu)造循環(huán)結(jié)構(gòu)，并在循環(huán)體內(nèi)檢驗所有的約束條件是否成立，找出使邏輯命題成構(gòu)，并在循環(huán)體內(nèi)檢驗所有的約束條件是否成立，找出使邏輯命題成立的解空間立的解空間(x,y,z)(x,y,z)。n 從解題思路中不難看出：三個窮舉變量從解題思路中不難看出：三個窮舉變量x x、y y、z z在整個問題的求解中擔(dān)在整個問題的求解中擔(dān)負(fù)著舉足輕重的作用。一般地，將這類變量稱為邏輯推理題的負(fù)著舉足輕重的作用。一般地，將這類變量稱為

30、邏輯推理題的推理變量。n 將解空間將解空間(x,y,z)(x,y,z)的各個元素值映射為對應(yīng)新郎的名稱，顯示出類似的各個元素值映射為對應(yīng)新郎的名稱，顯示出類似于于“誰和誰結(jié)婚的問題誰和誰結(jié)婚的問題”的信息，作為程序運行結(jié)果的輸出。的信息，作為程序運行結(jié)果的輸出。解決思路：解決思路：邏輯推斷算法邏輯推斷算法Page 414.4.3 知識準(zhǔn)備知識準(zhǔn)備1 1、算法描述、算法描述（1 1）邏輯推理）邏輯推理：利用已知條件，通過分析和判斷，得出正確的答：利用已知條件，通過分析和判斷，得出正確的答案。案。（2 2）算法的特性）算法的特性( (要素要素) )：假想值假想值 算法執(zhí)行過程中設(shè)計邏輯表達(dá)式的值得

31、確定問題，用算法執(zhí)行過程中設(shè)計邏輯表達(dá)式的值得確定問題，用的最多就是的最多就是0 0和和1 1（兩種選擇問題），數(shù)字（兩種選擇問題），數(shù)字1,2,31,2,3（有限多（有限多步）步）表達(dá)式表達(dá)式 根據(jù)推理描述條件轉(zhuǎn)換成計算機(jī)識別的邏輯表達(dá)式。根據(jù)推理描述條件轉(zhuǎn)換成計算機(jī)識別的邏輯表達(dá)式。窮舉運算窮舉運算 優(yōu)化算法，計算結(jié)果（也可以考慮遞歸）優(yōu)化算法，計算結(jié)果（也可以考慮遞歸）Page 424.4.3 知識準(zhǔn)備知識準(zhǔn)備 邏輯推理題目一般包含兩類條件：直接條件與間接條件。直接條件又稱為顯性條件或顯式條件，是題目中明確給出的命題斷言。間接條件又稱為隱性條件或隱式條件，是題目中沒有明確指明、但通過題意

32、或通過某些常識、某些條件論述，可以推斷出來的、隱含于題目的命題斷言。Page 434.4.4 案例實現(xiàn)案例實現(xiàn)例題的顯式條件分別是A、X和C講的三句假話：A說：他和X結(jié)婚，即X的新郎是編號為1的A；A提出的命題表達(dá)為：X=1；但由于A講的是假話，因此第一個顯式條件應(yīng)為：not(X=1)，它等價于(X！=1)。X說：她的未婚夫是C；XA提出的命題表達(dá)為：X=3。同理，由于X講了假話，于是第二個顯式條件應(yīng)為：X!=3。第三個顯式條件應(yīng)為：Z！=3。以上三個顯式條件應(yīng)同時成立，由此得到顯性的綜合邏輯表達(dá)式：(X!=1)&(X!=3)&(Z!=3)。Page 44n 例題的隱式條件為：

33、n 一個新郎只能娶一位新娘，三個新郎的新娘互不相同。于是隱式條件表達(dá)為：(x！=y)&(y！=z)&(z！=x)4.4.4 案例實現(xiàn)案例實現(xiàn)Page 45n C語言參考程序代碼：nmain() n char * xinlang3=“A”,“B”,“C”; / /* *以新郎編號為下標(biāo)的數(shù)組定義以新郎編號為下標(biāo)的數(shù)組定義* */ /n int x,y,z; / /* *新娘對應(yīng)的窮舉變量定義新娘對應(yīng)的窮舉變量定義* */ /n printf(%18sn,The Result is:n);n for (x=1;x=3;x+) / /* *用窮舉變量構(gòu)造循環(huán)結(jié)構(gòu)用窮舉變量構(gòu)造循環(huán)結(jié)構(gòu)

34、* */ /n for (y=1;y=3;y+)n for (z=1;z=3;z+)n if (x!=y)&(x!=z)&(y!=z) /* */n if (x!=1)&(x!=3)&(z!=3) / /* *約束條件的表達(dá)式約束條件的表達(dá)式* */ /n printf(“ X 的新郎的新郎 是是 %sn”,xinlangx-1); / /* *輸出求解出的夫妻關(guān)系輸出求解出的夫妻關(guān)系* */ /n printf(“ Y 的新郎的新郎 是是 %sn”,xinlangy-1);n printf(“ Z 的新郎的新郎 是是 %sn”,xinlangz-1); n4.

35、4.4 案例實現(xiàn)案例實現(xiàn)Page 46u運行結(jié)果：運行結(jié)果：4.4.4 案例實現(xiàn)案例實現(xiàn)Page 474.4.5 拓展訓(xùn)練拓展訓(xùn)練 案例為一個典型的邏輯推理的題目，對這類問題編程求解的關(guān)鍵在于首先找出問題中顯式或隱式的關(guān)聯(lián)條件，然后利用計算機(jī)所具備的強大的邏輯推斷能力，找出能使題目中的邏輯條件成立的可行解。 上述解決邏輯推理題目的思維方法，稱為判斷推理的方法。該方法一般要使用窮舉的策略，將每種可能的情形一一列舉出來，利用題目所給定的命題條件作為解題的線索，通過驗證各種可能情況下題目所給出的條件是否成立來尋找問題的答案。Page 484.4.5 拓展訓(xùn)練拓展訓(xùn)練 在求解邏輯推理問題時，如何設(shè)置推

36、理變量，設(shè)置多少推理變量，怎么確定推理變量的值域范圍，這些往往是問題的難點。推理變量的設(shè)定因題而異，具體問題要具體分析。但總的原則是：設(shè)定的推理變量應(yīng)該能夠覆蓋題目所有可能的情形；推理變量應(yīng)該能夠表達(dá)出題目所蘊含的所有的命題條件，包括顯式條件與隱式條件；Page 494.4.5 拓展訓(xùn)練拓展訓(xùn)練如果題目采用窮舉策略來解，大多數(shù)情況下，推理變量與窮舉變量往往是一致的；一般而言，一道邏輯推理題的推理變量的設(shè)定并非只有一種方案，有時可以有幾種不同的設(shè)定方法，這些不同的推理變量都能使問題得以解決，它們的區(qū)別僅在于對解題的算法思路與運行效率產(chǎn)生完全不同的影響；推理變量設(shè)置得好，往往會使問題求解的過程變得

37、非常簡單；反之，可能會增加解題的難度與復(fù)雜度。Page 504.4.5 拓展訓(xùn)練拓展訓(xùn)練解決邏輯推理題目的關(guān)鍵步驟包括：解決邏輯推理題目的關(guān)鍵步驟包括：推理變量的正確選擇與構(gòu)造；蘊藏于題目之中的顯性條件命題與隱性條件命題的挖掘；窮舉策略的合理應(yīng)用（多數(shù)情況下，窮舉變量往往采用推理變量）。Page 514.4.5 拓展訓(xùn)練拓展訓(xùn)練【案例2】區(qū)分國籍：有六個不同國籍的人A、B、C、D、E和F，分別來自美國、德國、英國、日本、中國和法國?，F(xiàn)在已知：A與美國人是醫(yī)生。E和中國人是教師。C和德國人是律師。B和F已經(jīng)做了父親，而德國人還未結(jié)過婚。法國人比A年齡大；日本人比C年齡大。B同美國人穿著藍(lán)色衣服，

38、而C同法國人穿著黑色衣服。由上述已知條件，編程求解A、B、C、D、E和F各是哪國人？Page 524.4.5 拓展訓(xùn)練拓展訓(xùn)練【第一步第一步】分別為美國、德國、英國、日本、中國和法國六個不同的國家設(shè)置自然數(shù)編號1、2、3、4、5、6。為連接編號與國家名稱，設(shè)置字符串?dāng)?shù)組Nation：Nation1.6 of String= (America,Germany,England,Japan,China,France);Page 534.4.5 拓展訓(xùn)練拓展訓(xùn)練【第二步第二步】為不同國籍的人A、B、C、D、E和F分別設(shè)置對應(yīng)的六個推理變量a、b、c、d、e、f，變量的取值為1到6這六個國家的編號。當(dāng)某

39、一推理變量值為k時，表示對應(yīng)于該變量的人來自于編號為k的國家。Page 544.4.5 拓展訓(xùn)練拓展訓(xùn)練【第三步第三步】羅列出題目包含的所有條件命題，并轉(zhuǎn)化為算法能夠識別的表達(dá)式。例題明確給出了六句條件斷言，但每句條件論述包含的信息不止一項，其中有顯性的條件命題，也有需要運用分析推理手段才能捕捉到的隱性條件命題。Page 554.4.5 拓展訓(xùn)練拓展訓(xùn)練下面將對于解題有關(guān)鍵作用的信息逐一析取出來：“A與美國人是醫(yī)生”，言下之意：A不是美國人，否則不會將A與美國人并列在一起來講；于是得到一個條件命題：a1。“E和中國人是教師”，于是有：E不是中國人，得到命題：e5。“C和德國人是律師”，于是有：

40、C不是德國人，得到命題：c2。Page 564.4.5 拓展訓(xùn)練拓展訓(xùn)練綜合考慮上述三個條件知：A是醫(yī)生，E是教師，C是律師；此外，美國人、中國人與德國人的職業(yè)分別是醫(yī)生、教師及律師。由生活常識知，一個人不能同時從事一種以上的職業(yè)。A既然是醫(yī)生，就不再會是教師或律師；而中國人的職業(yè)是教師，德國人是律師；于是不難推出：A不是中國人，也不是德國人。由此得到兩個條件命題：a5；a2。同理，C不是美國人或中國人，E不是美國人或德國人。于是推出以下四個命題：c1；c5；e1；e2。Page 574.4.5 拓展訓(xùn)練拓展訓(xùn)練“B和F已經(jīng)做了父親，而德國人還未結(jié)過婚”，言下之意：B和F都不是德國人。于是得到

41、以下兩個條件命題：b2；f2。“法國人比A年齡大；日本人比C年齡大”。年齡不同，肯定不是一個人，因此：A不是法國人；C不是日本人。于是得到以下兩個條件命題：a6；c4。Page 584.4.5 拓展訓(xùn)練拓展訓(xùn)練“B同美國人穿著藍(lán)色衣服，而C同法國人穿著黑色衣服”。由題意首先得到兩個命題：B不是美國人；C不是法國人。對應(yīng)的邏輯表達(dá)式為：b1；c6。其次，題意表明：美國人著藍(lán)裝，法國人著黑裝；B著藍(lán)裝，不著黑裝，所以B不是法國人；同理，C不是美國人。轉(zhuǎn)化為邏輯表達(dá)式，得到：b6；c 1。Page 594.4.5 拓展訓(xùn)練拓展訓(xùn)練【第四步第四步】整理以上17個邏輯命題表達(dá)式：去除重復(fù)的項目（命題“c

42、1”出現(xiàn)再次）；左符號為相同推理變量的命題排放在一起。整理后，得到由16個邏輯命題表達(dá)式為元素的命題集合： p=a1,a2,a5,a6,b1,b2,b6,c1,c2,c4,c5,c6,e1, e2,e5,f2。Page 604.4.5 拓展訓(xùn)練拓展訓(xùn)練 用邏輯與（and）運算符將該集合中所有的邏輯命題聯(lián)接成統(tǒng)一的表達(dá)式：condition_1=(a1)and(a2)and(a5)and(a6)and(b1)and(b2)and(b6)and(c1)and(c2)and(c4)and(c5)and(c6)and(e1)and(e2)and(e5)and(f2)。Page 614.4.5 拓展訓(xùn)練

43、拓展訓(xùn)練【第五步第五步】為體現(xiàn)“A、B、C、D、E、F是來自六個不同國家的人，即六個人的國籍各自互不相同”這一隱性約束條件，構(gòu)造另一邏輯表達(dá)式：condition_2=(a!=b)and(a!=c)and(a!=d)and(a!=e)and(a!=f)and(b!=c)and(b!=d)and(b!=e)and(b!=f)and(c!=d)and(c!=e)and(c!=f)and(d!=e)and(d!=f)and(e!=f)。 Page 624.4.5 拓展訓(xùn)練拓展訓(xùn)練【第六步】以六個推理變量a、b、c、d、e、f為窮舉變量，構(gòu)造多重循環(huán)，使每個變量分別取盡六個國家的編號；在循環(huán)體內(nèi)測試邏

44、輯命題condition_1和condition_2，找出使這兩個命題都能同時成立的解變量組 (a,b,c,d,e,f)。Page 634.4.5 拓展訓(xùn)練拓展訓(xùn)練【第七步第七步】由解變量組(a,b,c,d,e,f)的值作為下標(biāo)，映射到Nation數(shù)組的元素內(nèi)容，得到A、B、C、D、E和F六個人各自所屬的國籍名稱，輸出問題的最終答案。Page 644.4.5 拓展訓(xùn)練拓展訓(xùn)練本題的算法模型描述如下：a取值1、26 b取值1、26 c取值1、26 d取值1、26 e取值1、26 f取值1、26begin如果當(dāng)前的(a,b,c,d,e,f)能夠使condition_1和condition_2同時成

45、立，則該(a,b,c,d,e,f)即為問題的解變量組；將解變量組映射到數(shù)組Nation；組織并輸出符合題意的答案。end.Page 654.4.5 拓展訓(xùn)練拓展訓(xùn)練程序結(jié)果：Page 664.4.5 拓展訓(xùn)練拓展訓(xùn)練Page 674.4.5 拓展訓(xùn)練拓展訓(xùn)練Page 684.4.5 拓展訓(xùn)練拓展訓(xùn)練 練習(xí)題練習(xí)題11誰是竊賊:公安人員審問四名竊賊嫌疑犯。已知，這四人當(dāng)中僅有一名是竊賊，還知道這四人中每人要么是誠實的，要么總是說謊的。在回答公安人員的問題中：甲說：“乙沒有偷，是丁偷的?！币艺f：“我沒有偷，是丙便的。”丙說：“甲沒有偷，是乙偷的?！倍≌f：“我沒有偷。”編程判斷誰是盜竊者。 練習(xí)題練

46、習(xí)題22甲乙兩個網(wǎng)球隊進(jìn)行比賽，甲隊有隊員A、B、C三人，乙隊有隊員M、N、T三人?，F(xiàn)抽簽決定兩隊對打名單。記者向隊員打聽比賽的名單，得到以下答復(fù)：A說：我不和M對打；C說：我不和M、T對打。 編程推算兩隊對打的名單。Page 69任務(wù)任務(wù) 4.6找出偽幣找出偽幣 Page 704.6.1 案例描述案例描述Page 71引例引例2：金塊問題：金塊問題Page 72Page 73問題問題S問題問題S問題問題SS的解的解問題問題S1問題問題S2問題問題Si問題問題SnS1的解的解S2的解的解Si的解的解Sn的解的解問題的分解問題的分解子集解的合并子集解的合并子問題求子問題求解解分治思想Page 7

47、4 if(問題不可分) 直接求解； 返回問題的解； else 對原問題進(jìn)行分治； 遞歸對每一個分治的部分求解; 歸并整個問題，得出全問題的解； 分治策略的解題思路Page 75Page 76Page 77一元三次方程求解【問題描述問題描述】：有形如：有形如：ax3+bx2+cx+d=0這樣的一個一這樣的一個一元三次方程。給出該方程中各項的系數(shù)元三次方程。給出該方程中各項的系數(shù)(a，b，c，d均為實均為實數(shù)數(shù))，并約定該方程存在三個不同實根，并約定該方程存在三個不同實根(根的范圍在根的范圍在-100至至100之間之間)，且根與根之差的絕對值，且根與根之差的絕對值=1。要求由小到大依次在同。要求由

48、小到大依次在同一行輸出這三個實根一行輸出這三個實根(根與根之間留有空格根與根之間留有空格)，并精確到小數(shù)，并精確到小數(shù)點后點后4位。位。提示：記方程提示：記方程f(x)=ax3+bx2+cx+d，若存在，若存在2個數(shù)個數(shù)x1和和x2，且且x1x2，f(x1)*f(x2)0，則在，則在(x1，x2)之間一定有一個根。之間一定有一個根?！緲永斎霕永斎搿浚? -5 -4 20【樣例輸出樣例輸出】：-2.00 2.00 5.00Page 78n如果精確到小數(shù)點后兩位，可用簡單的枚舉法：將x從-100.00 到100.00（步長0.01） 逐一枚舉，得到20000個 f(x)，取其值與0最接近的三個f(x)，對應(yīng)的x即為答案。而題目已改成精度為小數(shù)點后4位，枚舉算法時間復(fù)雜度將達(dá)不到要求。n直接使用求根公式，極為復(fù)雜。加上本題的提示