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

第三章邏輯思維與計(jì)算機(jī)解題 續(xù) 2 例3 3求10 程序名 3 3 cpp 循環(huán)語句示例 作者 wuwh 編制時(shí)間 2002年9月20日 主要功能 計(jì)算10的階乘 include 預(yù)編譯命令voidmain 主函數(shù) 主函數(shù)開始inti 0 j 0 k 0 聲明i j k為整型變量 并初始化為0longsum 1 聲明sum為長整型變量 并初始化為1for i 10 i 1 i i 1 用for循環(huán)作累乘運(yùn)算 cout i i 顯示isum sum i 每一步乘積cout tsum sum endl 顯示每一步乘積for j 1 j 5500 j j 1 用for循環(huán)延遲時(shí)間for k 1 k 10000 k k 1 用for循環(huán)延遲時(shí)間 cout 10 sum endl 顯示運(yùn)算結(jié)果 主函數(shù)結(jié)束 3 includevoidmain inti 0 j 0 k 0 longsum 1 for i 10 i 1 i i 1 cout i i sum sum i cout tsum sum endl for j 1 j 5500 j j 1 for k 1 k 10000 k k 1 cout 10 sum endl 4 i 10sum 10i 9sum 90i 8sum 720i 7sum 5040i 6sum 30240i 5sum 151200i 4sum 604800i 3sum 1814400i 2sum 3628800i 1sum 362880010 3628800 該程序的運(yùn)行結(jié)果如下 5 將10 展開為10 9 8 7 6 5 4 3 2 1讓整型變量i去表示10 9 1讓長整型變量sum來表示乘積 初始時(shí)讓其為1將求10的階乘考慮成累乘問題 讓i 10去乘sum再將積存至sum中 即sum sum i之后讓i i 1 再用上式累乘 不斷地反復(fù)做這兩個(gè)運(yùn)算 從i 10 9 1 就完成了求10 的任務(wù) 見圖3 2 求10 的思路是 6 圖3 2 7 恰好計(jì)算機(jī)擅長做這種重復(fù)操作 使用for循環(huán)是最佳選擇 讓循環(huán)控制變量i就是數(shù)字10 9 1 i的初值為10 終值為1 for循環(huán)的三個(gè)表達(dá)式為 表達(dá)式1為i 10 表達(dá)式2為i 1 表達(dá)式3為i i 1 8 for循環(huán)的NS圖為了以后講解的方便 有必要使用更為簡便的N S結(jié)構(gòu)流程圖 如圖3 3 圖3 3 9 if sum 3 cout Thismanis char 64 k endl g 1 這一段程序可以讀作 如果sum真的為3時(shí) 做下面兩件事 1 輸出做好事的人 2 將本題的有解標(biāo)志置為1 其中 sum 3 為條件判斷語句中的條件 根據(jù)其真假使程序分支 例3 1的解要用到分支語句 即需要判斷當(dāng)四句話中有3句為真時(shí) 我們要將該人判定為做好事者 請看如下程序段 10 下面我們畫出分支程序的NS流程圖 這種圖直觀清晰 一目了然 圖3 4 11 if 表達(dá)式 語句1 else語句2 如果表達(dá)式為真 執(zhí)行語句1 否則執(zhí)行語句2if 表達(dá)式 語句塊1 else 語句塊2 12 一般格式if 表達(dá)式 語句1 如果表達(dá)式為真 執(zhí)行語句1 否則什么都不做 if 表達(dá)式 語句塊1 如果表達(dá)式為真 做語句塊1的內(nèi)容 否則什么都不做 13 舉例 實(shí)現(xiàn)如圖函數(shù) 圖3 5 14 程序名 3 4 cpp 分支程序示例 作者 wuwh 編制時(shí)間 2001年8月 主要功能 實(shí)現(xiàn)符號函數(shù) include 預(yù)編譯命令voidmain 主函數(shù) 主函數(shù)開始intx 0 y 0 聲明x y為整型變量 并初始化為0cout x 從鍵盤輸入整數(shù)送至x中if x 0 如果x 0 將1賦給y y 1 elseif x 0 如果x 0 將0賦給y y 0 else y 1 否則 x 0 將 1賦給ycout 當(dāng)x x 時(shí) y y endl 輸出x y的值 主函數(shù)結(jié)束 15 NS圖 圖3 6 16 NS圖 有了上述了解之后 我們來看解 誰做的好事 的程序框圖 圖3 7 17 現(xiàn)在我們來分析 誰做的好事 的NS流程圖 它是由兩大塊組成的 如圖3 8 圖3 8 第一塊循環(huán)結(jié)構(gòu) 第二塊分支結(jié)構(gòu) 18 第一塊是循環(huán)結(jié)構(gòu) 功能是產(chǎn)生被試對象 依次為A B C D 并測試四句話有多少句為真 如有3句為真 則可確定做好事者 同時(shí)置有解標(biāo)志為1 第二塊為分支結(jié)構(gòu) 功能是判斷是否無解 如為真 則輸出無解信息 這是粗看 再往細(xì)看 第一塊的循環(huán)體又由兩塊組成 如圖3 9 中含兩條賦值語句 中含一條分支語句 19 我們講這一段是希望你掌握NS圖 這對今后的學(xué)習(xí)會(huì)有好處 按照程序框圖很容易寫出程序 如下頁所示 thisman 64 k sum thisman A thisman C thisman D thisman D 圖3 9 sum 3 真 假 輸出該被測試者 有解標(biāo)志置1 20 程序名 3 5 cpp 作者 wuwh 編制時(shí)間 2001年8月 主要功能 誰做的好事 include 預(yù)編譯命令voidmain 主函數(shù) 主函數(shù)開始intk 0 sum 0 g 0 聲明變量為整數(shù)類型 且均初始化為0charthisman for k 1 k 4 k k 1 k既是循環(huán)控制變量 也表示第k個(gè)人 for循環(huán)體開始thisman 64 k sum thisman A thisman C thisman D thisman D if sum 3 如果4句話有3句話為真 則輸出該人 輸出做好事者cout 做好事者為 char 64 k endl g 1 有解標(biāo)志置1 for循環(huán)體結(jié)束if g 1 則輸出無解信息 cout Can tfound endl 主函數(shù)結(jié)束 21 includevoidmain 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 22 程序名 3 6 cpp 作者 wuwh 編制時(shí)間 2001年8月 主要功能 誰做的好事 include 預(yù)編譯命令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)的初始化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 則輸出無解信息 cout Can tfound endl 主函數(shù)結(jié)束 23 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 24 程序名 3 7 cpp 作者 wuwh 編制時(shí)間 2001年8月 主要功能 誰做的好事 include 預(yù)編譯命令voidmain 主函數(shù) 主函數(shù)開始intk 0 g 0 聲明變量為整數(shù)類型 且均初始化為0for k 1 k 4 k k 1 k既是循環(huán)控制變量 也表示第k個(gè)人 for循環(huán)體開始if k 1 k 3 k 4 k 4 3 如果4句話有3句話為真 則輸出該人 輸出做好事者cout 做好事者為 char 64 k endl g 1 有解標(biāo)志置1 for循環(huán)體結(jié)束if g 1 則輸出無解信息 cout Can tfound endl 主函數(shù)結(jié)束 上述程序可以簡化為 25 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 26 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 第四章邏輯判斷與解題思路 28 某地刑偵大隊(duì)對涉及六個(gè)嫌疑人的一樁疑案進(jìn)行分析 A B至少有一人作案 A E F三人中至少有兩人參與作案 A D不可能是同案犯 B C或同時(shí)作案 或與本案無關(guān) C D中有且僅有一人作案 如果D沒有參與作案 則E也不可能參與作案 試編一程序 將作案人找出來 邏輯表達(dá)式 29 1 邏輯與 運(yùn)算符為 圖4 1 為了解這道題 我們要研究邏輯運(yùn)算符與邏輯表達(dá)式 如圖電路A 表示開關(guān)A合上 B 表示開關(guān)B合上 A B 表示燈亮 30 1表示真 0表示假 這是邏輯變量的取值 非真即假 31 2 邏輯或 運(yùn)算符為 圖4 2 如圖電路A 表示開關(guān)A合上 B 表示開關(guān)B合上 A B 表示燈亮 32 1表示真 0表示假 33 3 邏輯非 運(yùn)算符為 兩隊(duì)比賽籃球 變量A表示A隊(duì)到場 A表示A隊(duì)不到場 變量B表示B隊(duì)到場 B表示B隊(duì)不到場 這場球賽能夠賽成 得兩隊(duì)都到場 假定 能賽成 用邏輯變量C表示 則C A B 34 賽不成當(dāng)然用 C表示 D C D表示賽不成則D A B理解為A不到場或B不到場 球賽無法進(jìn)行 35 思路 1 案情分析 將案情的每一條寫成邏輯表達(dá)式 第一條用CC1表示 第二條用CC2表示 36 CC1 A和B至少有一人作案令A(yù)變量表示A作案 B變量表示B作案 顯然這是或的關(guān)系 有CC1 A B 37 CC2 A和D不可能是同案犯可以分析為 A如果是案犯 D一定不是案犯 寫成A D D如果是案犯 A一定不是案犯 寫成D A A和D都不是案犯 寫成 A D 這三者之間是或的關(guān)系 因此有CC2 A D 38 CC2 A D 39 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 我們寫出CC3的真值表 40 CC3 A E A F E F 41 CC4 B和C或同時(shí)作案 或都與本案無關(guān)第一種情況 同時(shí)作案 B C 第二種情況 都與本案無關(guān) B C 兩者為或的關(guān)系 因此有CC4 B C B C 42 CC5 C D中有且僅有一人作案CC5 C D D C 43 CC6 如果D沒有參與作案 則E也不可能參與作案 分析這一條比較麻煩一些 可以列出真值表再歸納 44 CC6 D E 以上是案情分析 已經(jīng)化成了計(jì)算機(jī)可解的邏輯表達(dá)式 45 6個(gè)人每個(gè)人都有作案或不作案兩種可能 因此有種組合 從這些組合中挑出符合6條分析的作案者 定義6個(gè)整數(shù)變量 分別表示6個(gè)人A B C D E F 枚舉每個(gè)人的可能性讓0表示不是罪犯 讓1表示就是罪犯 2 采取枚舉方法 枚舉什么呢 枚舉組合 46 47 寫一個(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 48 for F 0 F 1 F F 1 cout A B C D E F endl 循環(huán)體 49 for E 0 E 1 E E 1 for F 0 F 1 F F 1 cout A B C D E F endl 循環(huán)體 50 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 循環(huán)體 51 for A 0 A 1 A A 1 for B 0 B 1 B B 1 循for C 0 C 1 C C 1 環(huán)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 52 53 為了給出每個(gè)人是否為罪犯的信息 程序中定義了一個(gè)二維數(shù)組 charinfo 2 9 不是罪犯 是罪犯 有兩個(gè)字串 每串最多有9 1個(gè)英文字符 info為數(shù)組名 54 char是說 info數(shù)組的元素為字符 2 為下標(biāo) 表示有兩個(gè)字符串 每個(gè)字符串最多有9 1個(gè)字符 因?yàn)橛⑽淖址家粋€(gè)字節(jié) 而漢字占兩個(gè)字節(jié) 故四個(gè)漢字要占8個(gè)英文字符的地方 每一字串后面自動(dòng)跟一個(gè)空字符 0 因此可以看出 第0號字符串info 0 的內(nèi)容為 不是罪犯 第1號字符串info 1 的內(nèi)容為 是罪犯 55 在輸出時(shí)用cout A info A endl 如果A為0 則輸出A 不是罪犯如果A為1 則輸出A 是罪犯參考程序4 1 cpp 案情分析 56 程序名 3 4 cpp 作者 wuwh 編制時(shí)間 2001年8月 主要功能 案情分析 includevoidmain void 案情分析 A和B至少有一人作案 cc1 A B A和D不可能是同案犯 cc2 A 定義二維數(shù)組 給出是否罪犯信息 57 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 58 測試6句話都為真時(shí) 才輸出誰是罪犯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é)束 59 討論 60 大家參與討論的題 五位跳水高手將參加十米高臺(tái)跳水決賽 有好事者讓五個(gè)人據(jù)實(shí)力預(yù)測比賽結(jié)果 A選手說 B第二 我第三 B選手說 我第二 E第四 C選手說 我第一 D第二 D選手說 C最后 我第三 E選手說 我第四 A第一 決賽成績公布之后 每位選手的預(yù)測都只說對了一半 即一對一錯(cuò) 請編程解出比賽的實(shí)際名次 61 思路 1 首先是將五個(gè)人的預(yù)測寫成邏輯表達(dá)式 讓關(guān)系運(yùn)算符 的含義是 是 讓數(shù)字1 2 3 4 5分別表示名次第一 第二 第五 讓整型變量A B C D E分別表示每個(gè)選手所得名次 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 62 2 考慮到每個(gè)人說的話是一對一錯(cuò) 即一真一假 比如A說的 B 2 A 3 應(yīng)該是11 0 10 1 1 63 我們可以歸納出要同時(shí)滿足五個(gè)人所說的話都符合一半對一半錯(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è)條件值都加在一起 64 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 65 3 只有等于5時(shí)才都符合每個(gè)人所說的話 這僅只是符合題意的一個(gè)必要條件 同時(shí)還得考慮A B C D E的取值不得有相同者 可以考慮 是一個(gè)條件 66 4 仍然可以用枚舉的方法 讓變量A B C D E在1 5中取值 形成滿足上述條件的A E的組合 即是所求 這時(shí)可用循環(huán)結(jié)構(gòu) 如下所示 67 68 作業(yè) 1請你自己完成這個(gè)程序 2思考如何提高效率 3思考還有什么其它解法 69 結(jié)束