邏輯思維與計算機解題.ppt

1 邏輯思維與計算機解題 2 將實際問題抽象為邏輯關(guān)系枚舉法解題思路關(guān)系與關(guān)系表達式程序的循環(huán)結(jié)構(gòu)與分支結(jié)構(gòu) 學習目標 3 關(guān)系運算符與關(guān)系表達式人的思維到用計算機語言的表示枚舉的概念與思路循環(huán)結(jié)構(gòu)分支結(jié)構(gòu) 內(nèi)容要點 4 計算機強大的邏輯分析功能是由人通過程序賦給它的 一些邏輯問題必須轉(zhuǎn)換成計算機能夠看得懂的數(shù)學表達式和一定的程序指令 這一章我們通過例子來介紹如何將人對問題的思考轉(zhuǎn)換為讓計算機能解的數(shù)學表達式 同時給出一些通常要用到的程序結(jié)構(gòu)和C C 語句 5 清華附中有四位同學中的一位做了好事 不留名 表揚信來了之后 校長問這四位是誰做的好事 A說 不是我 B說 是C C說 是D D說 他胡說 已知三個人說的是真話 一個人說的是假話 現(xiàn)在要根據(jù)這些信息 找出做了好事的人 例1 誰做的好事 6 為了解這道題 我們需要學習如何通過邏輯思維與判斷解這類問題的思路 7 將四個人說的四句話寫成關(guān)系表達式 在聲明變量時 我們讓thisman表示要尋找的做了好事的人 定義它是字符變量 charthisman 定義字符變量并將其初始化為空讓 的含義為 是 讓 的含義為 不是 8 利用關(guān)系表達式將四個人所說的話表示成 9 A B C D四個人 只有一位是做好事者 令做好事者為1 未做好事者為0 可以有如下4中狀態(tài) 情況 枚舉法的思路 10 這四種狀態(tài)可簡化寫成 顯然第一種狀態(tài)是假定A是做好事者 第二種狀態(tài)是假定B是做好事者 所謂枚舉是按照這四種假定逐一地去測試四個人的話有幾句是真話 如果不滿足三句為真 就否定掉這一假定 換下一個狀態(tài)再試 具體做法如下 11 1 假定讓thisman A 代入四句話中 四個關(guān)系表達式的值的和為1 顯然不是 A 做的好事 12 2 假定讓thisman B 代入四句話中 四個關(guān)系表達式的值的和為2 顯然不是 B 做的好事 13 3 假定讓thisman C 代入四句話中 四個關(guān)系表達式的值的和為3 就是 C 做的好事 14 綜上所述一個人一個人去試 就是枚舉 從編寫程序看 實現(xiàn)枚舉最好用循環(huán)結(jié)構(gòu) 這部分的程序?qū)懗鋈缦?for k 1 k 4 k k 1 計數(shù)型循環(huán) 循環(huán)的控制變量為k thisman 64 k 產(chǎn)生被試者 依次為 A B C D sum thisman A 測試 A 的話是否為真 thisman C 測試 B 的話是否為真 thisman D 測試 C 的話是否為真 thisman D 測試 D 的話是否為真 15 NS圖 有了上述了解之后 我們來看解 誰做的好事 的程序框圖 圖4 7 16 include 預(yù)編譯命令usingnamespacestd intmain 主函數(shù) 主函數(shù)開始intk 0 sum 0 g 0 定義整型變量 均初始化為0charthisman 定義字符變量 初始化為空for k 1 k 4 k k 1 k是循環(huán)控制變量 for循環(huán)體開始thisman 64 k sum thisman A thisman C thisman D thisman D if sum 3 如果3句話為真 則輸出該人cout 做好事者為 char 64 k endl g 1 有解標志置1 for循環(huán)體結(jié)束if g 1 cout Can tfound endl 輸出無解信息return0 主函數(shù)結(jié)束 17 include 預(yù)編譯命令usingnamespacestd voidmain intk 0 sum 0 g 0 charthisman for k 1 k 4 k k 1 thisman 64 k sum thisman A thisman D thisman C thisman D if sum 3 cout 做好事者為 char 64 k endl g 1 if g 1 cout Can tfound endl 18 換個思路數(shù)字1表示A數(shù)字2表示B數(shù)字3表示C數(shù)字4表示D讓K表示要找的人 K從1到4 表示從A找到D 這時A說 不是我 可形式化為K 1 B說 是C 可形式化為K 3 C說 是D 可形式化為K 4 D說 他胡說 可形式化為K 4 19 include 預(yù)編譯命令usingnamespacestd voidmain 主函數(shù) 主函數(shù)開始intk 0 sum 0 g 0 聲明變量為整數(shù)類型 且均初始化為0for k 1 k 4 k k 1 循環(huán)從k為1到4 sum 0 循環(huán)體內(nèi)的初始化 用sum累計真話數(shù)if k 1 sum sum 1 如A的話為真 則讓sum加1 if k 3 sum sum 1 如B的話為真 則讓sum加1 if k 4 sum sum 1 如C的話為真 則讓sum加1 if k 4 sum sum 1 如D的話為真 則讓sum加1 if sum 3 若有三句話為真 則做下列兩件事 cout Thismanis char 64 k endl 輸出做好事者g 1 讓有解標志置1 if g 1 則輸出無解信息 cout Can tfound endl 20 for k 1 k 4 k k 1 sum 0 if k 1 sum sum 1 如A的話為真 則讓sum加1 if k 3 sum sum 1 如B的話為真 則讓sum加1 if k 4 sum sum 1 如C的話為真 則讓sum加1 if k 4 sum sum 1 如D的話為真 則讓sum加1 21 include 預(yù)編譯命令intmain 主函數(shù) 主函數(shù)開始intk 0 g 0 聲明變量為整數(shù)類型 且均初始化為0for k 1 k 4 k k 1 k既是循環(huán)控制變量 也表示第k個人 if k 1 k 3 k 4 k 4 3 如果4句話有3句話為真 則輸出該人cout 做好事者為 char 64 k endl g 1 有解標志置1 if g 1 g 1則輸出無解信息 cout Can tfound endl return0 主函數(shù)結(jié)束 上述程序可以簡化為 22 for k 1 k 4 k k 1 if k 1 k 3 k 4 k 4 3 cout 做好事者為 char 64 k endl g 1 A說B說C說D說 23 for k 1 k 4 k k 1 if k 1 k 3 如果4句話有3句真話 就 k 4 輸出做好事者 k 4 3 cout 做好事者為 char 64 k endl g 1 24 思考和討論for intk 68 k 65 k k 1 if k 65 k 67 如果4句話有3句真話 k 68 就輸出做好事者 k 68 3 cout 做好事者為 char k endl g 1 25 某地刑偵大隊對涉及六個嫌疑人的一樁疑案進行分析 A B至少有一人作案 A E F三人中至少有兩人參與作案 A D不可能是同案犯 B C或同時作案 或與本案無關(guān) C D中有且僅有一人作案 如果D沒有參與作案 則E也不可能參與作案 試編一程序 將作案人找出來 例2 26 思路 1 案情分析 將案情的每一條寫成邏輯表達式 第一條用CC1表示 第二條用CC2表示 27 CC1 A和B至少有一人作案令A(yù)變量表示A作案 B變量表示B作案 顯然這是或的關(guān)系 有CC1 A B 28 CC2 A和D不可能是同案犯可以分析為 A和D是同案犯 寫成A DA和D不是同案犯 寫成 A D 因此有CC2 A D 29 CC3 A E F中至少有兩人涉嫌作案分析有三種可能第一種 A和E作案 A E 第二種 A和F作案 A F 第三種 E和F作案 E F 這三種可能性是或的關(guān)系 因此有CC3 A E A F E F 30 CC4 B和C或同時作案 或都與本案無關(guān)第一種情況 同時作案 B C 第二種情況 都與本案無關(guān) B C 兩者為或的關(guān)系 因此有CC4 B C B C 31 CC5 C D中有且僅有一人作案CC5 C D D C 32 CC6 如果D沒有參與作案 則E也不可能參與作案 分析這一條比較麻煩一些 可以列出真值表再歸納 33 CC6 D E 以上是案情分析 已經(jīng)化成了計算機可解的邏輯表達式 34 6個人每個人都有作案或不作案兩種可能 因此有種組合 從這些組合中挑出符合6條分析的作案者 定義6個整數(shù)變量 分別表示6個人A B C D E F 枚舉每個人的可能性讓0表示不是罪犯 讓1表示就是罪犯 2 采取枚舉方法 枚舉什么呢 枚舉組合 35 為了講多重循環(huán)先做些鋪墊編一個程序輸出000000000001000010 111111從高位到低位 分別用ABCDEF來表示 36 37 寫一個從000000到111111的程序for A 0 A 1 A A 1 for B 0 B 1 B B 1 for C 0 C 1 C C 1 for D 0 D 1 D D 1 for E 0 E 1 E E 1 for F 0 F 1 F F 1 cout A B C D E F endl 38 作業(yè)請你完成輸出000000到111111的程序并上機運行下面是據(jù)案情分析采用枚舉法尋找罪犯的程序框圖 39 40 為了給出每個人是否為罪犯的信息 程序中定義了一個二維數(shù)組 charinfo 2 9 不是罪犯 是罪犯 有兩個字串 每串最多有9 1個英文字符 info為數(shù)組名 41 char是說 info數(shù)組的元素為字符 2 為下標 表示有兩個字符串 每個字符串最多有9 1個字符 因為英文字符占一個字節(jié) 而漢字占兩個字節(jié) 故4個漢字要占8個英文字符的地方 每一字串后面自動跟一個空字符 0 因此可以看出 第0號字符串info 0 的內(nèi)容為 不是罪犯 第1號字符串info 1 的內(nèi)容為 是罪犯 42 在輸出時用cout A info A endl 如果A為0 則輸出A 不是罪犯如果A為1 則輸出A 是罪犯 43 includeusingnamespacestd intmain void 案情分析 A和B至少有一人作案 cc1 A B A和D不可能是同案犯 cc2 A 定義二維數(shù)組 給出是否罪犯信息 44 for A 0 A 1 A A 1 枚舉Afor B 0 B 1 B B 1 枚舉Bfor C 0 C 1 C C 1 枚舉Cfor D 0 D 1 D D 1 枚舉Dfor E 0 E 1 E E 1 枚舉Efor F 0 F 1 F F 1 枚舉F cc1 A B cc2 A 45 測試6句話都為真時 才輸出誰是罪犯if cc1 cc2 cc3 cc4 cc5 cc6 6 輸出判斷結(jié)果cout A info A endl cout B info B endl cout C info C endl cout D info D endl cout E info E endl cout F info F endl 輸出結(jié)束 循環(huán)結(jié)束return0 主函數(shù)體結(jié)束 46 討論 47 大家參與討論的題 五位跳水高手將參加十米高臺跳水決賽 有好事者讓五個人據(jù)實力預(yù)測比賽結(jié)果 A選手說 B第二 我第三 B選手說 我第二 E第四 C選手說 我第一 D第二 D選手說 C最后 我第三 E選手說 我第四 A第一 決賽成績公布之后 每位選手的預(yù)測都只說對了一半 即一對一錯 請編程解出比賽的實際名次 48 思路 1 首先是將五個人的預(yù)測寫成邏輯表達式 讓關(guān)系運算符 的含義是 是 讓數(shù)字1 2 3 4 5分別表示名次第一 第二 第五 讓整型變量A B C D E分別表示每個選手所得名次 A選手說 B 2 A 3 B選手說 B 2 E 4 C選手說 C 1 D 2 D選手說 C 5 D 3 E選手說 E 4 A 1 49 2 考慮到每個人說的話是一對一錯 即一真一假 比如A說的 B 2 A 3 應(yīng)該是11 0 10 1 1 50 我們可以歸納出要同時滿足五個人所說的話都符合一半對一半錯的條件是ta B 2 A 3 1 符合A選手的話tb B 2 E 4 1 符合B選手的話tc C 1 D 2 1 符合C選手的話td C 5 D 3 1 符合D選手的話te E 4 A 1 1 符合E選手的話因為ta tb te非1即0 五個條件值都加在一起 51 ta的取值是0或1ta的取值取決于下列關(guān)系 B 2 A 3 1B 2 可能是0或1A 3 可能是0或1 B 2 A 3 可能是0或1或2只有上式為1才能使ta為1 52 3 只有等于5時才都符合每個人所說的話 這僅只是符合題意的一個必要條件 同時還得考慮A B C D E的取值不得有相同者 可以考慮 是一個條件 53 4 仍然可以用枚舉的方法 讓變量A B C D E在1 5中取值 形成滿足上述條件的A E的組合 即是所求 這時可用循環(huán)結(jié)構(gòu) 如下所示 54 55 作業(yè) 1請你自己完成這個程序 2思考如何提高效率 3思考還有什么其它解法 56 結(jié)束