?? class1.cs
字號:
using System;
/*============================================================================
*Content:
模擬野人過河問題, 問題描述如下:
有三個牧師和三個野人過河，只有一條能裝下兩個人的船，在河的任何一方或者船上，如果
野人的人數大于牧師的人數，那么牧師就會有危險. 你能不能找出一種安全的渡河方法呢？
假設河的兩岸分別是甲岸和乙岸, 剛開始時6個人都在甲岸, 目標狀態是六個人都在乙岸.
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝*/
namespace ConsoleApplication14
{
/// <summary>
/// Class1 的摘要說明。
/// </summary>
///
public struct RIVERSIDE // 岸邊狀態類型
{
public int wildMan; // 野人數
public int churchMan; // 牧師數
};
public struct BOAT // 船的狀態類型
{
public int wildMan; // 野人數
public int churchMan; // 牧師數
};
public class QUESTION
{
public RIVERSIDE riverSide1; // 甲岸
public RIVERSIDE riverSide2; // 乙岸
public int side; // 船的位置, 甲岸為-1, 乙岸為1
public BOAT boat; // 船的狀態
public QUESTION pPrev; // 指向前一渡船操作
public QUESTION pNext; // 指向后一渡船操作
};
// 子函數聲明
//public static int FindNext(QUESTION quest);
//public static int Process(QUESTION quest);
class Class1
{
/// <summary>
/// 應用程序的主入口點。
/// </summary>
[STAThread]
static void Main(string[] args)
{
// savage.cpp : 定義控制臺應用程序的入口點。
QUESTION pHead = new QUESTION();
pHead.riverSide1.wildMan = 3;
pHead.riverSide1.churchMan = 3;
pHead.riverSide2.wildMan = 0;
pHead.riverSide2.churchMan = 0;
pHead.side = -1; // 船在甲岸
pHead.pPrev = null;
pHead.pNext = null;
pHead.boat.wildMan = 0;
pHead.boat.churchMan = 0;
// 遞規調用, 遍歷鏈表
if (Process(pHead))
{
char[] str =new char[256];
Console.WriteLine("\n 野人過河問題, 描述如下: 話說有三個牧師和三個野人過河,只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數大于牧師的人數, 那么牧師就會有危險. 你能不能找出一種安全的渡河方法呢?\n\n");
Console.WriteLine("===========================渡河過程演示(盲目搜索)===========================");
Console.WriteLine(" 甲岸: 野人數|牧師數 渡河方向|載野人|載牧師 乙岸: 野人數|牧師數");
QUESTION pQuest = pHead;
while (pQuest!=null)
{
Console.WriteLine("\t {0}\t {1}\t {2}\t {3}\t {4}\t\t {5}\t {6}", pQuest.riverSide1.wildMan,
pQuest.riverSide1.churchMan, (pQuest.side == -1) ? "--->":"<---", pQuest.boat.wildMan,
pQuest.boat.churchMan,pQuest.riverSide2.wildMan, pQuest.riverSide2.churchMan);
pQuest = pQuest.pNext;
}
Console.WriteLine("===========================================================================");
}
}
/* 回收內存空間
while (pHead)
{
QUESTION pTemp = pHead.pNext;
delete pHead;
pHead=pTemp;
}
pHead = null;
*/
// 渡船過程, 遞規調用函數FindNext(...)
public static bool Process(QUESTION pQuest)
{
// 如果找到一步合適操作，就將其插入結果鏈表末尾
if (FindNext(pQuest))
{
QUESTION pNew = new QUESTION();
pNew.riverSide1.wildMan = pQuest.riverSide1.wildMan + pQuest.boat.wildMan*(pQuest.side);
pNew.riverSide1.churchMan = pQuest.riverSide1.churchMan + pQuest.boat.churchMan*(pQuest.side);
pNew.riverSide2.wildMan = 3 - pNew.riverSide1.wildMan;
pNew.riverSide2.churchMan = 3 - pNew.riverSide1.churchMan;
pNew.side = (-1)*pQuest.side;
pNew.pPrev = pQuest;
pNew.pNext = null;
pNew.boat.wildMan = 0;
pNew.boat.churchMan = 0;
pQuest.pNext = pNew;
if (pNew.riverSide2.wildMan==3 && pNew.riverSide2.churchMan==3)
return true; // 完成
return Process(pNew);
}
// 不能找到合適的渡河操作，就返回當前節點的父節點，即pQuest在結果鏈表中的上級節點，同時刪除pQuest節點
else
{
QUESTION pPrev = pQuest.pPrev;
if (pPrev == null)
return false; // 無解
pPrev.pNext = null;
return Process(pPrev); // 返回其父節點重新再找
}
// return true;
}
// 判斷有否下一個渡河操作, 即根據比較算符找出可以接近目標節點的操作
// 算符共5個: 1野/ 1牧 / 1野1牧 / 2野 / 2牧
public static bool FindNext(QUESTION pQuest)
{
// 基本規則
// 渡船的優先順序: 甲岸運多人優先, 野人優先; 乙岸運少人優先, 牧師優先.
BOAT[] boatState=new BOAT[5];
if (pQuest.side == -1)
{
boatState[0].wildMan = 2;
boatState[0].churchMan = 0;
boatState[1].wildMan = 1;
boatState[1].churchMan = 1;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 0;
boatState[4].wildMan = 0;
boatState[4].churchMan = 1;
}
else
{
boatState[0].wildMan = 0;
boatState[0].churchMan = 1;
boatState[1].wildMan = 1;
boatState[1].churchMan = 0;
boatState[2].wildMan = 0;
boatState[2].churchMan = 2;
boatState[3].wildMan = 1;
boatState[3].churchMan = 1;
boatState[4].wildMan = 2;
boatState[4].churchMan = 0;
}
int i; // 用來控制算符
if (pQuest.boat.wildMan == 0 && pQuest.boat.churchMan == 0) // 初始狀態, 第一次渡河時
i = 0; // 取算符1
else
{
// 如果擴展A節點得到B和C兩個節點，然后假如說在繼續擴展B的時候失敗了，程序就需要返回到A節點，重新擴展，// 這個時候已經用過的算符就不能再用, 避免出現重新回到B節點。另外請注意我們選取算符是優先級的，比如說5
// 個算符中，第3個被用過了，那么第1、2個也肯定被用過了，那么現在就只能使用第4、5個了。
for (i=0; i<5; i++)
if (pQuest.boat.wildMan == boatState[i].wildMan && pQuest.boat.churchMan == boatState[i].churchMan)
break;
i++;
} // end else
if (i < 5)
{
int j;
for (j=i; j<5; j++)
{
int nWildMan1 = pQuest.riverSide1.wildMan + boatState[j].wildMan * pQuest.side;
int nChurchMan1 = pQuest.riverSide1.churchMan + boatState[j].churchMan * pQuest.side;
int nWildMan2 = 3 - nWildMan1;
int nChurchMan2 = 3 - nChurchMan1;
// 判斷本次操作的安全性, 即牧師數量>=野人或牧師數為0
if ((nWildMan1 <= nChurchMan1 || nChurchMan1 == 0) &&
(nWildMan2 <= nChurchMan2 || nChurchMan2 == 0) &&
nWildMan1 >=0 && nChurchMan1 >=0 && nWildMan2 >=0 && nChurchMan2 >= 0)
{
// 本操作是否重復上次操作,注意方向不同
if (pQuest.pPrev != null)
{
if (pQuest.pPrev.boat.wildMan == boatState[j].wildMan &&
pQuest.pPrev.boat.churchMan == boatState[j].churchMan)
continue;
}//end if
break; // 該操作可行, 推出循環
}//end if
}//end for
// 找到合適渡船操作
if (j < 5)
{
pQuest.boat.wildMan = boatState[j].wildMan;
pQuest.boat.churchMan = boatState[j].churchMan;
return true;
}//end if
}//end if
return false;
}
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -