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