邏輯推演程序設(shè)計范文
本站小編為你精心準(zhǔn)備了邏輯推演程序設(shè)計參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。
問題1：從前，一個農(nóng)夫帶一只狼，一只羊和一顆白菜過河(注意該狼已被農(nóng)夫馴服，但還是會吃羊)。他要將所有東西安全的帶到河的對岸。不幸的是河邊只有一條小船，只能裝下農(nóng)夫和他的一樣?xùn)|西，并且農(nóng)夫必須每次都隨船過河，因為只有他能撐船。在無人看管的情況下狼要吃羊，羊要吃白菜，因此，農(nóng)夫不能在河的某邊岸上單獨留下狼和羊，也不能單獨留下羊和白菜。問農(nóng)夫如何才能使三樣?xùn)|西平安過河。——農(nóng)夫過河
問題2：公安人員審問四名嫌疑犯。已知四人中僅有一名是竊賊還知道這四個人中每人要么是誠實的，要么總是說謊的。在回答公安人員的問題時：
甲說：“乙沒有偷，是丁偷的。”
乙說：“我沒有偷，是丙偷的。”
丙說：“甲沒有偷，是乙偷的。”
丁說：“我沒有偷。”
請根據(jù)這四人的答話判別誰是盜竊者。——竊賊說謊要解決上面兩個問題需通過合理假設(shè)與邏輯推演將問題簡化，通過正確的表達(dá)邏輯關(guān)系來駕馭程序設(shè)計。
二、邏輯推演在程序設(shè)計中的運用
1、委派任務(wù)問題
某任務(wù)需要在A，B，c，D，E這五人中物色人員去完成，但派人受限于下列條件：
(1)若A去，則B跟去；(2)D，E兩人中必有人去；(3)B，C兩人中必有人去，但只去一人；(4)c，D兩人要么都去，要么都不去；(5)若E去，則A，B都去。問這五個條件如何表示?
分析：求一個邏輯判斷類問題的關(guān)鍵是寫出正確的邏輯表達(dá)式。C語言中提供了豐富的算術(shù)和邏輯操作符，可以借助它們將問題化繁為簡。將題設(shè)條件用程序語言描述清楚后計算機就可以依此窮舉。
第一種方法
用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)系。窮舉每個人去或不去的各種可能，代入表達(dá)式中進(jìn)行推理運算，使上述各表達(dá)式值均為真的情況就是正確結(jié)果。
第二種方法
用位操作。令A(yù)，B，C，D，E都為邏輯型值true或false。則：
條件1可以表示為：A—B，它等價于!AttB。
條件2可以表示為：DIIE。
條件3可以表示為：(B＆＆!c)B&＆c)，推演為!B：c。
條件4可以表示為：(!CIID)&＆(clID!)，更簡單的形式是c==D。
條件5可以表示為：!EII(A&&B)。
如果將每個人的去與不去看成是5位整數(shù)的其中1位，其中A對應(yīng)最高位，E對應(yīng)最低位，那么所有可能的調(diào)派方案為從全部不派的00000到全部派去的11111之間變化。顯然，共有32種方案。全部遍歷的循環(huán)為：for(inti_0；i<32；i++)。其中每個i對應(yīng)一個二進(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ù)求解模式，把這五個條件表示成否定的形式：否定條件1為(!AIIB)=A&＆B，否定條件2為!(DJIE)，否定條件3為B==C，否定條件4為c!=D，否定條件5為E&＆!fA＆＆B)。在將A——E的式子代入條件表達(dá)式，即可編程求解。
2、竊賊說謊問題
來看文章開始時提到的問題2：用A，B，c，D分別代表四人，變量的值為1代表該人是竊賊。已知：四人中僅有一名竊賊，且這四個人中的每個人要么說真話，要么說假話，而由于甲乙丙三人都說了兩句話：××沒偷，××偷了”，故不論該人是否說謊，他提到的兩人之中必有人是小偷。故在列條件表達(dá)式時，可以不關(guān)心誰說謊，誰說實話。這樣，可以列出下列條件表達(dá)式：
甲說：“乙沒有偷，是丁偷的。”B+D=I
乙說：“我沒有偷，是丙偷的。”B+C=I
丙說：“甲沒有偷，是乙偷的。”A+B=I
丁說：“我沒有偷。”A+B+C+D=I
其中丁只說了一句話，無法判定真假，表達(dá)式反映了四個人中僅有一名是竊賊的條件。有了條件表達(dá)式，運用程序設(shè)計中的窮舉法就可以輕松求解。
3、農(nóng)夫過河問題(邏輯推演方法與BFS、DFS相結(jié)合的實例)
用一個四位二進(jìn)制數(shù)來分別表示白菜、羊、狼、和農(nóng)夫的過河狀態(tài)0表示在原始岸邊，即尚未過河；1表示在目的岸邊，已經(jīng)過河。將過河對象定義為枚舉enum類型，bitset<4>類型定義為bitvee(這里用到了c++標(biāo)準(zhǔn)函數(shù)庫STL)。枚舉類型定義過河者時，是按照白菜、羊、狼、和農(nóng)夫的次序分別定義的。這種次序中前三者的順序可以隨意，但農(nóng)夫farmer必須在最后，目的是便于在試探隨農(nóng)夫過河的對象時逐序進(jìn)行所有的東西都不能帶過河時，最后才選擇讓農(nóng)夫單獨過河。
enumWader
{
cabbage,／／默認(rèn)為1
goat，／／默認(rèn)為2
wolf,／／默認(rèn)為3
farmer，／／默認(rèn)為4J；
typedefbitset<4>bitvec；
過河的對象必須與農(nóng)夫在河的同一側(cè)，設(shè)計函數(shù)withFarmer來判斷。如果當(dāng)前state下，過河對象與農(nóng)夫的狀態(tài)參數(shù)一致，則返回真，表示二者在河的同一側(cè)。
此外，不論農(nóng)夫每次過河帶的東西如何，首先都應(yīng)該判斷這樣過河是否安全，即在無人看管的情況下，狼和羊，羊和白菜都沒有在河的同側(cè)，函數(shù)is_sMe完成判斷。當(dāng)農(nóng)夫與羊不在河的同側(cè)時，羊與白菜、或羊與狼在同側(cè)都是不安全的，返回false；其他情況則是安全的，
為了防止發(fā)生狀態(tài)的往復(fù)，即農(nóng)夫?qū)⒁粋€東西帶過去又帶回來的情況發(fā)生，也為了記錄過河的狀態(tài)過程，對所有可能的狀態(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ù)對應(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)換為實際的過河方案即可。
三、總結(jié)
程序設(shè)計是將人的思維轉(zhuǎn)化為機器語言的過程，程序抽象程度越高，與人的思維方式就越類似。邏輯推演是建立在思維之上的，是有依據(jù)的推演，將邏輯推演的思想融人程序，在一定程度上可以實現(xiàn)程序的智能化。隨著程序設(shè)計語言的發(fā)展，邏輯推演的應(yīng)用一定會越來越廣。
