1、摘要：人帶著貓、雞、米過(guò)河，船除需要人劃之外，至多能載貓、雞、米三者 之一，而當(dāng)人不在場(chǎng)時(shí)貓要吃雞、雞要吃米，試通過(guò)數(shù)學(xué)建模，運(yùn)用計(jì)算機(jī)給出 一個(gè)安全渡河方案，并使渡河次數(shù)盡量少。一、問(wèn)題分析：此問(wèn)題是從狀態(tài)向量A經(jīng)過(guò)奇數(shù)次運(yùn)算向量B變?yōu)闋顟B(tài)向量A(0,0,0,0)的狀態(tài)。轉(zhuǎn)移過(guò)程為什么是奇數(shù)次？我們注意到過(guò)河有兩種，奇數(shù) 次的為從左岸到右岸，而偶數(shù)的為右岸回到左岸，因此得到下述轉(zhuǎn)移過(guò)程，所 以最后應(yīng)該是過(guò)河完成時(shí)狀態(tài)轉(zhuǎn)移數(shù)為奇數(shù)次。二、模型假設(shè)：假設(shè)船除了載人之外，至多只能載貓、雞、米三者之一。當(dāng)人不在場(chǎng)時(shí)，貓一定會(huì)吃雞、雞一定會(huì)吃米。我們將人，貓，雞，米依次用四維向量中的分量表示，當(dāng)一物在

2、左岸時(shí)，相 應(yīng)的分量記為1，在右岸時(shí)記為0如向量(1,0,1,0)表示人和雞在左岸，貓和 米在右岸，并將這些向量稱(chēng)為狀態(tài)向量。例如(1,1,1,1)表示它們都在左岸， (0,1,1,0)表示貓，雞在左岸，人，米在右岸；由于問(wèn)題中的限制條件，有些 狀態(tài)是允許的，有些狀態(tài)是不允許的。凡問(wèn)題可以允許存在的狀態(tài)稱(chēng)為可取狀 態(tài)。A向量定義為狀態(tài)變量。比如A (1,0丄0)是一個(gè)可取狀態(tài)向量，但A(0,0丄1)1 2是一個(gè)不可取狀態(tài)向量。此外，B向量定義為運(yùn)載變量。把每運(yùn)載一次也用一個(gè) 四維向量來(lái)表示。如B (1,1,0,0 )表示人和貓?jiān)诖希u和米不在船上，這自然1是可取的運(yùn)載，因?yàn)榇奢d兩物，而B(niǎo)

3、 (1,0,1,1)則是不可取運(yùn)載，依此規(guī)律類(lèi)推。2三、模型建立：由上可知，可取狀態(tài)向量 A 共有 10 個(gè)，即(1,1,1,1)(o,o,o,o)(1,1,1,0)(0,0,0,1)(1,1,0,1)(0,0,1,0)(1,0,1,1)(0,1,0,0)(1,0,1,0)(0,1,0,1)可取運(yùn)載 B 有 4 個(gè) ：（1,1,0,0）、 （1,0,1,0）、 （1,0,0,1）、 （1,0,0,0）。四、算法設(shè)計(jì)：1、規(guī)定A和B的每一分量相加時(shí)按二進(jìn)制法則進(jìn)行，這樣一次渡河就是一 個(gè)可取狀態(tài)和一個(gè)可取運(yùn)載相加，在判斷和向量是否屬于可取狀態(tài)即可。2、可以將可取狀態(tài)及可取運(yùn)載分別編成矩陣。共分為

4、五個(gè)m文件，一個(gè)主 文件 xduhe.m 數(shù)，四個(gè)子文件分別為：2.1、duhe （L,B,M,s）函數(shù)：用來(lái)實(shí)現(xiàn)渡河總思路。思路為：將起始矩陣 A 分別與可取運(yùn)載相加（使用 二進(jìn)制法則），判斷相加后的矩陣 C 是否是（0，0，0，0），如果是，則渡河成 功。否則，用fuhe（C,M）函數(shù)判斷C是否是可取狀態(tài)，如果是，則打印并將C 與初始矩陣合并成新矩陣，繼續(xù)調(diào)用 duhe.m 函數(shù)。2.2、fuhe(C,M)函數(shù):判斷和矩陣C是否屬于矩陣M,如果是，則返回1,否則返回0.2.3、Panduan (S)函數(shù)：判斷 S 矩陣中是否有兩個(gè)相同的狀態(tài)，即行向量。如果有，則返回 0，否則 返回 1.2

5、.4、print(K,C,s)函數(shù)：打印相應(yīng)的狀態(tài)。五、程序：1、xduhe.m 文件：clear;clc;A=1,1,1,1;B=1,0,1,0;1,1,0,0;1,0,0,1;1,0,0,0;M=1,1,1,0;0,0,0,1;1,1,0,1;0,0,1,0;1,0,1,1;0,1,0,0;1,0,1,0;0,1,0,1; duhe(A,B,M,1);2、duhe.m 文件：function duhe(L,B,M,s);h,l=size(L);for k=s:hfor i=1:4C=mod(L(k,:)+B(i,:),2);if C=0,0,0,0print(B(i,:),C,s);fpr

6、intf(渡河成功nn);break;else if fuhe(C,M)=1print(B(i,:),C,s);S=L;C;if Panduan(S)=1 duhe(S,B,M,s+1);elsefprintf(此渡河方案不可行nn);endendendendend3、fuhe.m 文件：function y=fuhe(C,M) y=0;for i=1:8if(C=M(i,:)y=1;break;endend4、Panduan.m 文件： function z=Panduan(S)z=1;m,n=size(S);for p=1:mfor q=(p+1):mif S(p,:)-S(q,:)=0,

7、0,0,0z=0;break;endendend5、print.m 文件：function print(K,C,s)fprintf(第門(mén)次渡河:s);if K(1)=1fprintf(人,);endif K(2)=1fprintf(貓,);endif K(3)=1fprintf(雞,);endif K(4)=1fprintf(米);endif C(1)=0fprintf（從左岸到達(dá)右岸n）; elsefprintf（從右岸回到左岸n）; end六、計(jì)算結(jié)果：在 matlab 在 matlab 中運(yùn)行，結(jié)果如下：第1弦渡河:丈，雞，從左岸到達(dá)右岸 第2後渡河:人 從右厚回到左岸第3魏渡河:人，淘

8、 從左岸到達(dá)右岸 第Q護(hù)渡河:兒喙從右岸回到左岸 第曰哀渡河:丈：，雞,從左岸到達(dá)右岸 此渡河方案不可行此渡河方案不可行第1弦渡河:丈，雞，從左岸到達(dá)右岸 第2後渡河:人 從右厚回到左岸第3魏渡河:人，淘 從左岸到達(dá)右岸 第Q護(hù)渡河:兒喙從右岸回到左岸 第曰哀渡河:丈：，雞,從左岸到達(dá)右岸 此渡河方案不可行此渡河方案不可行第壷渡河:兒 第引久渡詞 第T鑲渡河:人， 第漱渡河:人 此渡河方案不可行J J 5 J 米貓聘雞從左岸到達(dá)右岸 從右岸回到左岸 從左岸到達(dá)右倖 從右岸回到左岸第5次渡間炭才貓，城左岸到達(dá)右岸 第臨次渡河；人，貓,從右岸回到左岸 此渡河方案不可行第宮欲渡河:人，米，從右岸回到

9、左岸 此渡河方秦不可行第丁涂渡河：.匚 範(fàn) 乩左岸到達(dá)右岸此渡河方案不可行第疔沃渡洵:人，米，從右岸回到左詳此渡河方累不可行第漱:渡河:k,從右岸凹到左徉第議潦可:兒晦從左岸到達(dá)右岸渡冋成功敘徐渡河:餐 從右岸回到左岸 此渡河方案不可行笫了次渡河:人* K從左岸到達(dá)右陣 第4浹渡河:k 喙 從右岸回至I左岸 些第5次渡河:人，囑 從左岸到達(dá)右岸笫叮次渡河米 第丁次渡河:兒池 第E碾渡河:人J雞 此渡河方秦不可行從.右岸回到左岸 狀芒岸到達(dá)y岸 炊右岸回到左岸第呂次渡河；：人，貓從右岸回到左岸 此渡河方案不可行此渡河方案不可行第臨次渡河:人從右岸回到左岸 第祗濃河哄誤城左岸到達(dá)右岸 渡河成功第也次渡河：Lk,米，從.右岸回到左岸此渡河方案不可行第3次渡河扌卷，從左岸到達(dá)右岸 此渡河方案不可行七、結(jié)果分析：從運(yùn)行結(jié)果可以看出，共有兩種運(yùn)送方案： 人先帶雞過(guò)河，然后人再回來(lái)，把米帶過(guò)河，然后把雞運(yùn)回河岸，人再把貓 帶過(guò)河，最后人回來(lái)把雞帶過(guò)去。人