美章網(wǎng) 資料文庫 邏輯推演程序設(shè)計(jì)范文

邏輯推演程序設(shè)計(jì)范文

本站小編為你精心準(zhǔn)備了邏輯推演程序設(shè)計(jì)參考范文,愿這些范文能點(diǎn)燃您思維的火花,激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

邏輯推演程序設(shè)計(jì)

一、經(jīng)典邏輯推演問題的引入

問題1:從前,一個(gè)農(nóng)夫帶一只狼,一只羊和一顆白菜過河(注意該狼已被農(nóng)夫馴服,但還是會(huì)吃羊)。他要將所有東西安全的帶到河的對(duì)岸。不幸的是河邊只有一條小船,只能裝下農(nóng)夫和他的一樣?xùn)|西,并且農(nóng)夫必須每次都隨船過河,因?yàn)橹挥兴軗未T跓o人看管的情況下狼要吃羊,羊要吃白菜,因此,農(nóng)夫不能在河的某邊岸上單獨(dú)留下狼和羊,也不能單獨(dú)留下羊和白菜。問農(nóng)夫如何才能使三樣?xùn)|西平安過河。——農(nóng)夫過河

問題2:公安人員審問四名嫌疑犯。已知四人中僅有一名是竊賊還知道這四個(gè)人中每人要么是誠實(shí)的,要么總是說謊的。在回答公安人員的問題時(shí):

甲說:“乙沒有偷,是丁偷的。”

乙說:“我沒有偷,是丙偷的。”

丙說:“甲沒有偷,是乙偷的。”

丁說:“我沒有偷。”

請(qǐng)根據(jù)這四人的答話判別誰是盜竊者。——竊賊說謊要解決上面兩個(gè)問題需通過合理假設(shè)與邏輯推演將問題簡化,通過正確的表達(dá)邏輯關(guān)系來駕馭程序設(shè)計(jì)

二、邏輯推演在程序設(shè)計(jì)中的運(yùn)用

1、委派任務(wù)問題

某任務(wù)需要在A,B,c,D,E這五人中物色人員去完成,但派人受限于下列條件:

(1)若A去,則B跟去;(2)D,E兩人中必有人去;(3)B,C兩人中必有人去,但只去一人;(4)c,D兩人要么都去,要么都不去;(5)若E去,則A,B都去。問這五個(gè)條件如何表示?

分析:求一個(gè)邏輯判斷類問題的關(guān)鍵是寫出正確的邏輯表達(dá)式。C語言中提供了豐富的算術(shù)和邏輯操作符,可以借助它們將問題化繁為簡。將題設(shè)條件用程序語言描述清楚后計(jì)算機(jī)就可以依此窮舉。

第一種方法

用0和1表示執(zhí)行任務(wù)的狀態(tài):1(去),0(不去),則

A==O或A+B=:2’

D-4-E>1

B+C==l

c+D:=0或c+D==2

E==0或A+B+E=3

各表達(dá)式之間是“與”的關(guān)系。窮舉每個(gè)人去或不去的各種可能,代入表達(dá)式中進(jìn)行推理運(yùn)算,使上述各表達(dá)式值均為真的情況就是正確結(jié)果。

第二種方法

用位操作。令A(yù),B,C,D,E都為邏輯型值true或false。則:

條件1可以表示為:A—B,它等價(jià)于!AttB。

條件2可以表示為:DIIE。

條件3可以表示為:(B&&!c)B&&c),推演為!B:c。

條件4可以表示為:(!CIID)&&(clID!),更簡單的形式是c==D。

條件5可以表示為:!EII(A&&B)。

如果將每個(gè)人的去與不去看成是5位整數(shù)的其中1位,其中A對(duì)應(yīng)最高位,E對(duì)應(yīng)最低位,那么所有可能的調(diào)派方案為從全部不派的00000到全部派去的11111之間變化。顯然,共有32種方案。全部遍歷的循環(huán)為:for(inti_0;i<32;i++)。其中每個(gè)i對(duì)應(yīng)一個(gè)二進(jìn)制數(shù),為一種調(diào)派方案。在某一種調(diào)派方案i中:

A為最高位(i&16)>>4或者i>>4(將低位都擠掉)

B為次高位(i&8)>>3

C為中間位(i&4)>>2

D為次低位(i&2)>>l

E為最低位(i&1)

根據(jù)求解模式,把這五個(gè)條件表示成否定的形式:否定條件1為(!AIIB)=A&&B,否定條件2為!(DJIE),否定條件3為B==C,否定條件4為c!=D,否定條件5為E&&!fA&&B)。在將A——E的式子代入條件表達(dá)式,即可編程求解。

2、竊賊說謊問題

來看文章開始時(shí)提到的問題2:用A,B,c,D分別代表四人,變量的值為1代表該人是竊賊。已知:四人中僅有一名竊賊,且這四個(gè)人中的每個(gè)人要么說真話,要么說假話,而由于甲乙丙三人都說了兩句話:××沒偷,××偷了”,故不論該人是否說謊,他提到的兩人之中必有人是小偷。故在列條件表達(dá)式時(shí),可以不關(guān)心誰說謊,誰說實(shí)話。這樣,可以列出下列條件表達(dá)式:

甲說:“乙沒有偷,是丁偷的。”B+D=I

乙說:“我沒有偷,是丙偷的。”B+C=I

丙說:“甲沒有偷,是乙偷的。”A+B=I

丁說:“我沒有偷。”A+B+C+D=I

其中丁只說了一句話,無法判定真假,表達(dá)式反映了四個(gè)人中僅有一名是竊賊的條件。有了條件表達(dá)式,運(yùn)用程序設(shè)計(jì)中的窮舉法就可以輕松求解。

3、農(nóng)夫過河問題(邏輯推演方法與BFS、DFS相結(jié)合的實(shí)例)

用一個(gè)四位二進(jìn)制數(shù)來分別表示白菜、羊、狼、和農(nóng)夫的過河狀態(tài)0表示在原始岸邊,即尚未過河;1表示在目的岸邊,已經(jīng)過河。將過河對(duì)象定義為枚舉enum類型,bitset<4>類型定義為bitvee(這里用到了c++標(biāo)準(zhǔn)函數(shù)庫STL)。枚舉類型定義過河者時(shí),是按照白菜、羊、狼、和農(nóng)夫的次序分別定義的。這種次序中前三者的順序可以隨意,但農(nóng)夫farmer必須在最后,目的是便于在試探隨農(nóng)夫過河的對(duì)象時(shí)逐序進(jìn)行所有的東西都不能帶過河時(shí),最后才選擇讓農(nóng)夫單獨(dú)過河。

enumWader

{

cabbage,//默認(rèn)為1

goat,//默認(rèn)為2

wolf,//默認(rèn)為3

farmer,//默認(rèn)為4J;

typedefbitset<4>bitvec;

過河的對(duì)象必須與農(nóng)夫在河的同一側(cè),設(shè)計(jì)函數(shù)withFarmer來判斷。如果當(dāng)前state下,過河對(duì)象與農(nóng)夫的狀態(tài)參數(shù)一致,則返回真,表示二者在河的同一側(cè)。

此外,不論農(nóng)夫每次過河帶的東西如何,首先都應(yīng)該判斷這樣過河是否安全,即在無人看管的情況下,狼和羊,羊和白菜都沒有在河的同側(cè),函數(shù)is_sMe完成判斷。當(dāng)農(nóng)夫與羊不在河的同側(cè)時(shí),羊與白菜、或羊與狼在同側(cè)都是不安全的,返回false;其他情況則是安全的,

為了防止發(fā)生狀態(tài)的往復(fù),即農(nóng)夫?qū)⒁粋€(gè)東西帶過去又帶回來的情況發(fā)生,也為了記錄過河的狀態(tài)過程,對(duì)所有可能的狀態(tài)進(jìn)行標(biāo)定。四位二進(jìn)制數(shù)的所有可能狀態(tài)為16,都初始化為一1,表示過河過程中尚未出現(xiàn)過;隨著過河過程的不斷進(jìn)行,它被改變?yōu)槠淝耙粻顟B(tài)二進(jìn)制數(shù)對(duì)應(yīng)的整數(shù)值。

于是,農(nóng)夫過河問題經(jīng)過二進(jìn)制化以后,化為從初始狀態(tài)0000出發(fā),經(jīng)過~系列安全狀態(tài)后,如果最后狀態(tài)到達(dá),即path[15]有前驅(qū)狀態(tài),則表示過河成功。問題求解后得到一系--進(jìn)制數(shù),將這一系列二進(jìn)制數(shù)表示的過河狀態(tài)轉(zhuǎn)換為實(shí)際的過河方案即可。

三、總結(jié)

程序設(shè)計(jì)是將人的思維轉(zhuǎn)化為機(jī)器語言的過程,程序抽象程度越高,與人的思維方式就越類似。邏輯推演是建立在思維之上的,是有依據(jù)的推演,將邏輯推演的思想融人程序,在一定程度上可以實(shí)現(xiàn)程序的智能化。隨著程序設(shè)計(jì)語言的發(fā)展,邏輯推演的應(yīng)用一定會(huì)越來越廣。

主站蜘蛛池模板: 亚洲一区二区三区在线网站| 久久久久人妻一区精品色欧美| 玩弄丰满少妇XXXXX性多毛| 国产亚洲欧美日韩俺去了| 14又嫩又紧水又多| 天堂8在线天堂bt| 三极片在线观看| 日本精品少妇一区二区三区| 亚洲人成无码网站| 波多野结衣种子网盘| 办公室啪啪激烈高潮动态图| 这里只有精品视频在线| 国产欧美精品区一区二区三区| 97久久精品午夜一区二区| 小猪视频app下载版最新忘忧草b站| 久久久久亚洲av片无码| 最新国产精品自拍| 亚洲天堂一级片| 波多野结衣和乡下公在线观看| 农村乱人伦一区二区| 色费女人18女人毛片免费视频| 国产成人精品免费视频软件 | bt在线www天堂资源网| 成人网站免费看黄a站视频| 久久久精品波多野结衣AV| 欧美h片在线观看| 亚洲大尺度无码无码专区| 波多野结衣伦理片bd高清在线| 免费在线观看污视频网站| 精品欧美成人高清在线观看2021| 国产乱来乱子视频| 香艳69xxxxx有声小说| 国产无套乱子伦精彩是白视频| 骚包在线精品国产美女| 国产精品资源在线观看| 99久久国产免费福利| 天堂网www中文在线| 免费一级毛片在线播放傲雪网| 老少另类性欧美杂交| 国产乱子伦农村XXXX| 麻豆91在线视频|