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