1、第6部分 反猜數(shù)游戲何光宇，2010.61 復(fù)習(xí)2 補(bǔ)充知識(shí)：棧、函數(shù)調(diào)用機(jī)理與遞歸3 反猜數(shù)游戲教學(xué)重點(diǎn)C語(yǔ)言學(xué)習(xí)需要掌握三個(gè)方面內(nèi)容：C語(yǔ)言知識(shí)編程技能：使用Visual C+，查找?guī)椭{(diào)試排除常見(jiàn)錯(cuò)誤等分析問(wèn)題和解決問(wèn)題能力1 復(fù)習(xí)C語(yǔ)言知識(shí)解題方法2.1 棧2.2 基于棧的函數(shù)調(diào)用機(jī)理2.3 遞歸2.4 棧與遞歸2.5 遞歸與循環(huán)2 棧、函數(shù)調(diào)用機(jī)理與遞歸棧: 一種”后進(jìn)先出”數(shù)據(jù)結(jié)構(gòu)。操作系統(tǒng)用其為變量進(jìn)行內(nèi)存空間分配.開(kāi)始調(diào)用時(shí)實(shí)參被壓入堆棧(push),供子程序使用;調(diào)用結(jié)束后參數(shù)被彈出,堆棧恢復(fù)到原有位置.2.1 棧1.調(diào)用前堆棧位置堆棧2.調(diào)用時(shí)，壓入?yún)?shù)后, 堆棧位置(實(shí)參

2、值即傳遞給了形參）3. 調(diào)用結(jié)束后堆棧位置主調(diào)函數(shù)被調(diào)函數(shù)基于棧的函數(shù)調(diào)用過(guò)程：1 開(kāi)始調(diào)用時(shí)，參數(shù)值被壓入棧（參數(shù)值被傳遞到被調(diào)函數(shù)）2 在棧中為被調(diào)函數(shù)使用變量分配內(nèi)存空間3 執(zhí)行被調(diào)函數(shù)（棧中變量值相應(yīng)改變）4 被調(diào)函數(shù)執(zhí)行完畢，分配空間收回，棧恢復(fù)到調(diào)用前位置5 返回值被賦值給相應(yīng)變量（如果沒(méi)有賦值語(yǔ)句，則返回值被拋棄）2.2 基于棧的函數(shù)調(diào)用機(jī)理遞歸是指一個(gè)函數(shù)除了可調(diào)用其它函數(shù)外，還可以直接或間接地調(diào)用自身遞歸反映的思想：可以將問(wèn)題轉(zhuǎn)化為一個(gè)弱一些、與自身相似的問(wèn)題，再予以求解是計(jì)算機(jī)思維中非常重要的一類求解問(wèn)題方法舉例：n！ = (n-1)! * n要點(diǎn)：遞歸關(guān)系、遞歸終止條件2

3、.3 遞歸 double factorial(int n) if (n=1) return 1; return n*factorial(n-1); 設(shè)計(jì)要點(diǎn)：找出遞歸方程式和遞歸終止條件遞歸方程式：使問(wèn)題向邊界條件轉(zhuǎn)化的規(guī)則。遞歸定義必須能使問(wèn)題越來(lái)越簡(jiǎn)單。N! = N*(N-1)!遞歸終止條件：所描述問(wèn)題的最簡(jiǎn)單情況，它本身不再使用遞歸的定義。N=1遞歸方法只需少量的步驟就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了算法的代碼量棧是一種應(yīng)用范圍廣泛的數(shù)據(jù)結(jié)構(gòu)，適用于各種具有“后進(jìn)先出”特性的問(wèn)題 函數(shù)調(diào)用利用棧來(lái)完成遞歸是函數(shù)調(diào)用特殊形式，同樣利用棧來(lái)實(shí)現(xiàn)2.4 棧與遞歸遞歸調(diào)用過(guò)程中

4、調(diào)用關(guān)系示例過(guò)程A1在其過(guò)程體的某一處調(diào)用過(guò)程A2，A2以在其過(guò)程體的某一處調(diào)用過(guò)程A3，A3不調(diào)用其他過(guò)程。當(dāng)過(guò)程A1執(zhí)行到的r處時(shí)，它自己實(shí)際上被掛起來(lái)，而被調(diào)用過(guò)程A2開(kāi)始運(yùn)行。一直等到A2執(zhí)行完畢這后才返回過(guò)程A1的r1處繼續(xù)執(zhí)行A1剩下部分。 在過(guò)程A2的上述運(yùn)行中，由于調(diào)用了A3，A2同樣在t處掛起并一直等到A3執(zhí)行結(jié)束后返回t1處才能繼續(xù)執(zhí)行后繼語(yǔ)句。 相應(yīng)的工作棧狀態(tài)變化 每遇到一個(gè)過(guò)程調(diào)用便立刻將相應(yīng)的返回位置(及其它有用的信息)進(jìn)棧；每當(dāng)一被調(diào)用過(guò)程執(zhí)行結(jié)束時(shí)，工作棧棧頂元素下好是此過(guò)程的返回位置。 2.5 遞歸與循環(huán)的比較 遞歸與循環(huán)都是解決“重復(fù)操作”的機(jī)制。遞歸使一些

5、復(fù)雜的問(wèn)題處理起來(lái)簡(jiǎn)單明了。就效率而言，遞歸算法的實(shí)現(xiàn)往往要比迭代算法耗費(fèi)更多的時(shí)間（調(diào)用和返回均需要額外的時(shí)間）與存貯空間（用來(lái)保存不同次調(diào)用情況下變量的當(dāng)前值的棧棧空間），也限制了遞歸的深度。每個(gè)迭代算法原則上總可以轉(zhuǎn)換成與它等價(jià)的遞歸算法；反之不然 。遞歸的層次是可以控制的，而循環(huán)嵌套的層次只能是固定的，因此遞歸是比循環(huán)更靈活的重復(fù)操作的機(jī)制。【例】任給十進(jìn)制的正整數(shù)，請(qǐng)從高位到低位逐位輸出各位數(shù)字。循環(huán)算法設(shè)計(jì)： 本題目中要求“從高位到低位”逐位輸出各位數(shù)字，但由于我們并不知道正整數(shù)的位數(shù)，算法還是“從低位到高位”逐位求出各位數(shù)字比較方便。 這樣就不能邊計(jì)算邊輸出，而需要用數(shù)組保存計(jì)算

6、的結(jié)果，最后倒著輸出。循環(huán)算法如下：void f3(int n) int j,i=0,a16; while(n=10) ai=n % 10; i=i+1; n=n/10; ai=n; for(j=i;j=0;j=j-1) printf(“%d”,n);遞歸算法設(shè)計(jì)： 與f2不同，遞歸算法是先遞歸地求n/10的個(gè)位數(shù)字，然后再求個(gè)位數(shù)字n的個(gè)位數(shù)字并輸出。這樣輸出操作是在回溯時(shí)完成的。遞歸停止條件與f2相同為n10。遞歸算法如下：void f4(n) if(n10) print(“%d”,n); else f4(n/10); print(”%d”, n % 10); 遞歸是一種強(qiáng)有力的算法設(shè)計(jì)方

7、法。遞歸是一種比循環(huán)更強(qiáng)、更好用的實(shí)現(xiàn)“重復(fù)操作”的機(jī)制。因?yàn)檫f歸不需要編程者（算法設(shè)計(jì)者）自己構(gòu)造“循環(huán)不變式”，而只需要找出遞歸關(guān)系和最小問(wèn)題的解。遞歸與數(shù)學(xué)歸納法遞歸非遞歸程序可讀性易難代碼量大小小大時(shí)間長(zhǎng)短占用空間大小適用范圍廣窄設(shè)計(jì)難度易難游戲者想四個(gè)任意數(shù)字，讓計(jì)算機(jī)來(lái)猜這四個(gè)數(shù)。如果計(jì)算機(jī)猜中或游戲者給出的答案為44， 則程序結(jié)束解題思路：列出求解問(wèn)題步驟(分析問(wèn)題，列出步驟)對(duì)難以求解子問(wèn)題先抽象，確定要做什么。待其他子問(wèn)題解決后，再來(lái)分析解決此問(wèn)題。3 反猜數(shù)游戲步驟：1 打印游戲規(guī)則2 提示：游戲者想好四個(gè)數(shù)，按某個(gè)鍵繼續(xù)3 進(jìn)行猜測(cè)4 提示游戲者評(píng)價(jià)猜測(cè)結(jié)果5 如果猜測(cè)結(jié)

8、果是40，則打印勝利標(biāo)志,程序結(jié)束6 如果猜測(cè)結(jié)果是44，則打印放棄標(biāo)志,程序結(jié)束7 返回第3步進(jìn)行猜測(cè)正向，根據(jù)每次猜測(cè)結(jié)果，確定猜測(cè)結(jié)果應(yīng)該是什么？逆向：（基于枚舉的搜索）列出所有可能答案在所有可能結(jié)果中選一個(gè)給猜數(shù)者根據(jù)猜數(shù)者反饋，對(duì)所有可能答案進(jìn)行篩選1 打印游戲規(guī)則2 提示：游戲者想好四個(gè)數(shù)，按某個(gè)鍵繼續(xù)3 列出所有可能答案4 在所有可能結(jié)果中選一個(gè)給猜數(shù)者5 提示游戲者評(píng)價(jià)猜測(cè)結(jié)果6 如果猜測(cè)結(jié)果是40，則打印勝利標(biāo)志,程序結(jié)束7 如果猜測(cè)結(jié)果是44，則打印放棄標(biāo)志,程序結(jié)束8 根據(jù)游戲者評(píng)價(jià)猜測(cè)結(jié)果，對(duì)可能結(jié)果進(jìn)行篩選9 返回第3步細(xì)化后問(wèn)題求解思路難點(diǎn)1：如何列出所有可能答案難

9、點(diǎn)2：在所有可能結(jié)果中選一個(gè)給猜數(shù)者難點(diǎn)3：如何根據(jù)猜數(shù)者所猜答案，對(duì)可能結(jié)果進(jìn)行篩選進(jìn)一步思考：將所有數(shù)字都猜一次，看哪個(gè)數(shù)字所需的猜數(shù)次數(shù)最多？哪個(gè)數(shù)字所需的猜數(shù)次數(shù)最少。分析原因，找出所需猜數(shù)次數(shù)最少的猜數(shù)方法。2.1 早期程序設(shè)計(jì)方法2.2 結(jié)構(gòu)化程序設(shè)計(jì)方法2.3 面向?qū)ο蟪绦蛟O(shè)計(jì)方法2.4 反猜數(shù)游戲2 結(jié)構(gòu)化程序設(shè)計(jì)與面向?qū)ο缶幊?9早期的程序設(shè)計(jì)方法追求程序的高效率，編程過(guò)份依賴技巧，而不注重所編寫程序的結(jié)構(gòu)，也就是沒(méi)有固定程序設(shè)計(jì)方法的時(shí)期。程序的可讀性、可重用性都很差。其中一個(gè)典型問(wèn)題是頻繁使用goto語(yǔ)句。雖然這種方法存在很多問(wèn)題，但對(duì)于單人完成較為簡(jiǎn)單的任務(wù)，事實(shí)上還是

10、經(jīng)常被采用的。2.1 早期的程序設(shè)計(jì)方法30結(jié)構(gòu)化方法出現(xiàn)在70年代中期，我們可以這樣理解它：結(jié)構(gòu)化程序設(shè)計(jì)方法是從程序要實(shí)現(xiàn)的功能的角度出發(fā)的。一般按照自頂向下、逐步求精的方式，將程序要完成的功能逐級(jí)劃分成許多小的功能模塊，象搭積木一樣搭起來(lái)。這些小的功能模塊最終都可以轉(zhuǎn)化成三種基本控制結(jié)構(gòu)的組合。所謂的功能可以理解為對(duì)數(shù)據(jù)的操作。在程序?qū)崿F(xiàn)中，特定的功能或功能模塊一般用函數(shù)來(lái)實(shí)現(xiàn)，它們要對(duì)特定的數(shù)據(jù)進(jìn)行操作。2.2 結(jié)構(gòu)化程序設(shè)計(jì)方法31結(jié)構(gòu)化設(shè)計(jì)方法的特點(diǎn)結(jié)構(gòu)化程序設(shè)計(jì)方法的主要技術(shù)是自頂向下、逐步求精，采用單入口、單出口的控制結(jié)構(gòu)自頂向下是一種分解問(wèn)題的技術(shù)，逐步求精指結(jié)構(gòu)化程序的連續(xù)

11、分解，最終成為下面三種基本控制結(jié)構(gòu)的組合三種基本控制結(jié)構(gòu)：順序、分支、循環(huán)32分支結(jié)構(gòu)語(yǔ)句1語(yǔ)句2語(yǔ)句3條件語(yǔ)句2語(yǔ)句1語(yǔ)句1語(yǔ)句2順序結(jié)構(gòu)循環(huán)結(jié)構(gòu)33例：從鍵盤輸入一個(gè)學(xué)生的信息（包括姓名、年齡、性別、學(xué)號(hào)等）和一個(gè)老師的信息（包括姓名、年齡、性別、是否授課等），然后將信息輸出到屏幕。一個(gè)簡(jiǎn)單的例子34分析：根據(jù)需求（題目要求），我們可以把問(wèn)題劃分為兩個(gè)功能模塊，一個(gè)是輸入模塊，一個(gè)是輸出模塊，做完了輸入模塊，再做輸出模塊。再具體考慮每個(gè)模塊如何實(shí)現(xiàn)（逐步求精）。我們用C語(yǔ)言來(lái)寫，參看下面的代碼：35/ void main()/ 主函數(shù)開(kāi)始/ 聲明用于存儲(chǔ)學(xué)生信息的變量char strStu

12、dentName20;/ 學(xué)生姓名int nStudentAge;/ 學(xué)生年齡char cStudentSex;/ 學(xué)生性別int nStudentNumber; / 學(xué)生學(xué)號(hào)/ 聲明用于存儲(chǔ)老師信息的變量char strTeacherName20;/ 老師姓名int nTeacherAge;/ 老師年齡char cTeacherSex;/ 老師性別int nIsTeaching; / 是否授課/ 輸入模塊GetStudentInfo();/ 輸入學(xué)生信息GetTeacherInfo();/ 輸入老師信息/ 輸出模塊PrintStudentInfo();/ 輸出學(xué)生信息PrintStudent

13、Info();/ 輸出老師信息描述學(xué)生的數(shù)據(jù)描述老師的數(shù)據(jù)函數(shù)函數(shù)36上面的例子中，我們可以進(jìn)一步將屬于學(xué)生和老師的變量放入結(jié)構(gòu)中。這樣可以在一定程度上完成對(duì)數(shù)據(jù)的封裝。但在結(jié)構(gòu)化程序設(shè)計(jì)中，數(shù)據(jù)與對(duì)其進(jìn)行操作的函數(shù)仍是分離的。/ 聲明學(xué)生結(jié)構(gòu)Studentstruct Studentchar strStudentName20;/ 學(xué)生姓名int nStudentAge;/ 學(xué)生年齡char cStudentSex;/ 學(xué)生性別int nStudentNumber; / 學(xué)生學(xué)號(hào);/ 聲明老師結(jié)構(gòu)Teacherstruct Teacherchar strTeacherName20;/ 老師姓名

14、int nTeacherAge;/ 老師年齡char cTeacherSex;/ 老師性別int nIsTeaching; / 是否教書;3738問(wèn)題：函數(shù)用于完成一定的功能，它們都是針對(duì)特定的數(shù)據(jù)進(jìn)行操作的。那么我們能不能以特定的數(shù)據(jù)為中心，將數(shù)據(jù)與對(duì)其進(jìn)行操作的函數(shù)封裝起來(lái)呢？392.3面向?qū)ο蟪绦蛟O(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)出現(xiàn)在80年代中后期面向?qū)ο蟪绦蛟O(shè)計(jì)是建立在結(jié)構(gòu)化程序設(shè)計(jì)基礎(chǔ)上的，但它不再是從功能入手，而是從對(duì)象（人、地方、事情等）入手面向?qū)ο蟪绦蛟O(shè)計(jì)以類作為構(gòu)造程序的基本單位，它具有封裝、數(shù)據(jù)抽象、繼承、多態(tài)等特點(diǎn)40簡(jiǎn)單地說(shuō)，對(duì)象就是現(xiàn)實(shí)世界中的各種實(shí)體，包括人、地點(diǎn)和事物等。

15、例如，桌子、椅子、教室、學(xué)生、老師、電話、汽車等等。一般都要從屬性和行為兩個(gè)方面來(lái)對(duì)它們加以描述。在這里，我們認(rèn)為對(duì)象和對(duì)象的實(shí)例是同一個(gè)概念。什么是對(duì)象？41對(duì)象具有的一些特征稱為屬性，以一個(gè)人為例，他的姓名、年齡、身高、體重等可以作為他的屬性。這些屬性會(huì)有其對(duì)應(yīng)的值，一般至少會(huì)有一項(xiàng)區(qū)別于其它對(duì)象，它們?cè)诔绦蛟O(shè)計(jì)中對(duì)應(yīng)的是一定的數(shù)據(jù)。為了達(dá)到目的，對(duì)象必須提供的功能（或必須提供的服務(wù)）稱為對(duì)象的行為，在程序設(shè)計(jì)中對(duì)應(yīng)一定的方法（函數(shù)）。屬性和行為42類描述了一組具有相同屬性（數(shù)據(jù)元素）和相同行為（函數(shù)）的對(duì)象。類的數(shù)據(jù)成員是對(duì)對(duì)象屬性的抽象，類的函數(shù)成員是對(duì)對(duì)象行為的抽象，而類本身就是對(duì)對(duì)

16、象的抽象。 可以理解為一種擴(kuò)充的數(shù)據(jù)類型，既定義了如何存儲(chǔ)數(shù)據(jù)，也定義了如何對(duì)數(shù)據(jù)進(jìn)行操作。什么是類？43class Student/ Student類的聲明public: / 公有成員Student();/ 構(gòu)造函數(shù)Student();/ 析構(gòu)函數(shù)char*GetName();/ 查詢姓名intGetAge();/ 查詢年齡charGetSex();/ 查詢姓名intGetNumber();/ 查詢學(xué)號(hào)boolSetName(char* n);/ 設(shè)置姓名boolSetAge(int age);/ 設(shè)置年齡boolSetSex(char* s);/ 設(shè)置性別boolSetNumber(int

17、 num);/ 設(shè)置學(xué)號(hào)protected: / 保護(hù)成員charm_strName20;/ 姓名，字符串?dāng)?shù)組intm_nAge;/ 年齡，整型charm_cSex;/ 性別，字符型intm_nNumber;/ 學(xué)號(hào)，整型;例：C+中類的聲明Student類成員函數(shù)成員函數(shù)成員變量44Student A;/ 聲明Student的對(duì)象AA.SetName(“張三”);/ 設(shè)置A的名字A.SetAge(20);/ 設(shè)置A的年齡例：C+中類使用4546總的來(lái)說(shuō)，結(jié)構(gòu)化程序設(shè)計(jì)方法是一種模塊化程序設(shè)計(jì)方法，它在解決問(wèn)題時(shí)是以功能為中心的，一定的功能模塊雖然也作用于特定的數(shù)據(jù)，但它們并沒(méi)有被封裝在一起。

18、面向?qū)ο蟪绦蛟O(shè)計(jì)方法則是以對(duì)象為中心來(lái)解決問(wèn)題的。屬于同種對(duì)象的屬性（數(shù)據(jù)）和服務(wù)（功能）被抽象出來(lái)封裝到一起。47簡(jiǎn)單地說(shuō)，對(duì)象就是現(xiàn)實(shí)世界中的各種實(shí)體，包括人、地點(diǎn)和事物等。例如，桌子、椅子、教室、學(xué)生、老師、電話、汽車等等。一般都要從屬性和行為兩個(gè)方面來(lái)對(duì)它們加以描述。在這里，我們認(rèn)為對(duì)象和對(duì)象的實(shí)例是同一個(gè)概念。什么是對(duì)象？2.4 反猜數(shù)游戲如何過(guò)濾？6月19日左右，具體時(shí)間、地點(diǎn)下周通知已參加大作業(yè)的同學(xué)不參加考試 考試題目形式：考試范圍：C語(yǔ)言（即前十三周所講內(nèi)容）題型：編程題3道，算法題（只要求寫出程序流程，不要求具體編程)1道，程序閱讀題（挑出已有程序中錯(cuò)誤） 2道。關(guān)于考試1 本周日課上進(jìn)行演示。2 演示按大組進(jìn)行按所選題目，將參加大作業(yè)的同學(xué)分成了11組，每組指定了兩個(gè)聯(lián)系人。大組內(nèi)可互相交流和協(xié)作，盡量保證彼此之間實(shí)現(xiàn)功能有些區(qū)別。課上留3040分鐘供大家進(jìn)行討論請(qǐng)選作特定題目的同學(xué)，到聯(lián)系人那里登記，留下班級(jí)、學(xué)號(hào)、姓名、郵件和電話等聯(lián)系方式請(qǐng)聯(lián)系人將選作人信息匯總后