邏輯思維與計(jì)算機(jī)解題.ppt

《邏輯思維與計(jì)算機(jī)解題.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《邏輯思維與計(jì)算機(jī)解題.ppt（56頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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