商仆过河问题代码(C#版)
//代码名称：商仆过河问题
//使用语言：C#
//编译环境：Windows10 、Visual Stdio 2013
//测试环境：Window7、Windows8、Windows10测试均通过
//目录
//变量声明
//主函数
//调用的函数
// 01画头函数
// 02起始值start输入
// 03迭代的算法
// 04输出每种正确方法的数组
// 05输出计算过程信息
// 06检查状态变量是否合法方法
// 07判断状态向量是否重复
// 08产生合法运载向量的合法
//************************************************程序开始************************************************
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.T asks;
namespace ConsoleApplication5
{
class Program
{
#region 所有的静态变量
static int Boat_Capacity; //船载人数静态变量
static int Person_Capacity; //商人和仆人的人数上限
static Status[] YZ; //运载向量集合
static Int64 MethodNum = 0; //统计产生方法所用的步骤数
static Int64 MethodNumSum = 0; //统计产生的方法个数
static Int64 CalculatorNum = 0; //统计计算次数
static Int64 Step = 50; //初始开始步骤值
static ArrayList MinArray=new ArrayList(); //记录最小步骤方法的数据数组
struct Status //定义商仆结构体
{
public int _Trader; //商人数
public int _Servant; //仆人数
}
#endregion
//************************************************主函数************************************************ static void Main(string[] args)
{
Head(); //画头
Start(); //初始值导入
Status zt; zt._Trader = Person_Capacity; zt._Servant = Person_Capacity; //初始化商人和仆人数
ArrayList ztArr = new ArrayList(); //初始化运载状态数组
ztArr.Add(zt);
System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
//时间对象
timer.Start(); //计时开始
Recursion_Filter(zt, ztArr, 0, true); //迭代开始
timer.Stop(); //计时结束
Console.WriteLine("----------------------------------------------------------------");
Console.Write("计算完毕！");
Console.WriteLine("程序耗时: {0}", timer.Elapsed);
Console.WriteLine("计算时间由您计算机性能决定，您用时多少呢？O(∩_∩)O");
Console.WriteLine("----------------------------------------------------------------");
Console.Write("输入[exit]退出程序：");
string exitStr="";
do
{
exitStr=Console.ReadLine();
}
while (exitStr != "exit");
} //end main 主函数结束
//************************************************调用的函数************************************************
#region 01画头函数
static void Head()
{
Console.WriteLine("＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝");
Console.WriteLine("＝欢迎使用过河问题计算程序！＝");
Console.WriteLine("＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝");
}
#endregion
#region 02起始值start输入
static void Start()
{
Console.Write("请输入商人/仆人的人数上限：");
Person_Capacity = Convert.ToInt32(Console.ReadLine());
Console.Write("请输入船载人数上限(建议值:{0})：", (Person_Capacity+1)/2);
Boat_Capacity = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("您输入的商/仆人数上限为：{0}，船载人数为：{1}", Person_Capacity, Boat_Capacity);
YZ = Prouduce_YZ_Variable(Boat_Capacity);
Console.WriteLine("运载向量为以下{0}种：", YZ.Length);
for (int i = 0; i < YZ.Length; i++)
{
Console.Write("({0},{1}) ", YZ[i]._Trader, YZ[i]._Servant);
if ((i+1) % 10 == 0) Console.WriteLine();
}
Console.WriteLine("输入尽可能接近最优步骤的[预估值]可以大大提高运算效率，减少运算时间");
Console.WriteLine("如果限制后计算不出结果，请将预估值改宽松一些再计算");
Console.Write("请输入最优步骤估计范围(默认为50,不输入则采用默认值) Step<=");
try
{
Step = Convert.ToInt32(Console.ReadLine());
Console.WriteLine("您输入的预估范围为Step<={0}", Step);
}
catch
{
Console.WriteLine("将采用默认范围Step<={0}", Step);
}
Console.WriteLine("按任意键开始计算...");
//System.Timers.Timer;
Console.ReadKey();
Console.WriteLine("程序开始计算(若程序无反应是数据量较大，请耐心等待)...");
}
#endregion
#region 03迭代的算法
static void Recursion_Filter(Status ZT_Initial, ArrayList ZTArray_Initial, int n,bool OnlyMin) //(起始状态向量) {
ArrayList ZTArray = new ArrayList();
for (int i = 0; i < YZ.Length; i++)
{
ZTArray = ZTArray_Initial;
CalculatorNum++;
Status ZT; //定义状态变量
Status YZ_Time; //定义此时的运载向量
YZ_Time._Trader = YZ[i]._Trader * (int)Math.Pow(-1, n); //此时运载向量的值
YZ_Time._Servant = YZ[i]._Servant * (int)Math.Pow(-1, n);
ZT._Trader = ZT_Initial._Trader - YZ_Time._Trader; //此时的状态向量
ZT._Servant = ZT_Initial._Servant - YZ_Time._Servant;
//状态合法且不重复的
if (Check_This_ZT(ZT._Trader, ZT._Servant, Person_Capacity) && !Check_This_ZT_Repeat(ZT,ZTArray,n) )
{
if (ZT._Trader == 0 && ZT._Servant == 0 ) //达到最终目标
{
MethodNum++;//统计方法数量
if ((ZTArray.Count+1) { Step = ZTArray.Count+1; //统计最小步骤 MinArray = (ArrayList)ZTArray.Clone(); } if (MethodNum > 1) { MethodNumSum = MethodNumSum + MethodNum; Step--; MethodNum = 0; } Console.Clear(); Head(); OutPrintInformation(); Console.WriteLine("----------------------------计算区域----------------------------"); OutPrintArray(ZTArray); continue; } else //没达到最终目标 { if (n >=(Step - 1) && OnlyMin) continue;//【优化】只算最优值的判断 ZTArray.Add(ZT); Recursion_Filter(ZT, ZTArray, ++n,OnlyMin); } } else //状态直接不合适的 { continue; } n--; //For循环完成说明调回上一层，n-1 ZTArray.RemoveAt(ZTArray.Count - 1); } //end for } //end Recursion_Filter #endregion #region 04输出每种正确方法的数组 static void OutPrintArray(ArrayList MethodArray) { Status[] ZT_Array = (Status[])MethodArray.T oArray(typeof(Status)); for (int j = 0; j < ZT_Array.Length; j++) { string ztstr; if (j % 2 == 0) ztstr="去"; else ztstr="回"; Console.Write("({0,2},{1,2})-{2}->", ZT_Array[j]._Trader, ZT_Array[j]._Servant,ztstr); if ((j+1) % 5 == 0) Console.WriteLine(); } Console.Write("( 0, 0)"); Console.WriteLine(""); } #endregion #region 05输出计算过程信息 static void OutPrintInformation() { Console.WriteLine("正在计算(请不要点击画面或进行其他操作)..."); Console.WriteLine("当前程序计算{0}次，已产生{1}种步骤的方法", CalculatorNum, MethodNumSum/2); Console.WriteLine("当前最优步骤数为{0}步，最优解为：", Step+1); } #endregion #region 06检查状态变量是否合法方法 static bool Check_This_ZT(int a, int b, int N) { bool check = true; if (a == N && b == N) check = false; if (a == N && (b >= 0 && b <= N)) ; else if (a == 0 && (b >= 0 && b <= N)) ; else if (a == b && (a > 0 && a < N)) ; else check = false; return check; } #endregion #region 07判断状态向量是否重复 static bool Check_This_ZT_Repeat(Status ZT, ArrayList ZTArray, int n) { bool check = false; Status[] ZTArr = (Status[])ZTArray.ToArray(typeof(Status)); for (int i = 0; i < ZTArr.Length;i++ ) { if (i % 2 == (n + 1) % 2) { if (ZTArr[i]._Servant == ZT._Servant && ZTArr[i]._Trader == ZT._Trader) { check = true; break; } } } return check; } #endregion #region 08产生合法运载向量的合法 static Status[] Prouduce_YZ_Variable(int M) { ArrayList YZList = new ArrayList(); for (int i = 0; i <= M; i++) { for (int j = 0; j <= M; j++) { int sum = i + j; if (sum > 0 && sum <= M) { if (i >= j || (i < j && i == 0)) { Status Produce_YZ = new Status(); Produce_YZ._Trader = i; Produce_YZ._Servant = j; YZList.Add(Produce_YZ); } //end if } //end if } } //end for Status[] YZ_Array = (Status[])YZList.ToArray(typeof(Status)); return YZ_Array; } //end Prouduce_YZ_Variable #endregion } //end class } //end namespace //************************************************程序结束************************************************ 郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限：2012/6/21 指导教师签名： 课程负责人签名： 年月日 郑州轻工业学院 本科 数据结构课程设计总结报告 设计题目：农夫过河 学生姓名： 系别：计算机与通信工程学院 专业：计算机科学与技术 班级：计算机科学与技术 学号： 指导教师： 2012年6 月21 日 一，设计题目 问题描述： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二，运行环境（软、硬件环境） VC6.0 Windows7系统 三，算法设计的思想 对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径，这样做只能搜到一种合理方法，因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四，算法的流程图 要写算法的流程图，必须要先很了解自己的函数结构，我先在纸上手动的把整个过程在纸上画一遍，了解它的大体流程，然后把各个函数给分开，下面是我自己根据我的代码中画的各个函数画的流程图，希望老师满意。 主函数的流程图： 商人过河问题 /*************************************************** *M个商人与每人各带的一个仆人过河问题 *船每次至多运N个人，至少要有一人划船 *在任一岸，当商人数<仆人数时,仆人就杀人越货 *过河由商人安排运送人员及数目 *找出安全渡河的全部方法并打印(原问题中M=3，N=2) *2010-10-10 20时许（纪念伟大的双十） * LYP ***************************************************/ /****************************************************************** *本题为多步决策 *若考虑只针对人数为 M = 3 对，每次过河人数最多 N = 2 *可以证明路径中必须经坐标中(3,1)过至(1,1)点(过诃时)， *后返回至(2,2)点，再过诃至(0,2)点(只剩2个仆人) *可以先考虑(3,3)到(3,1)点 *再经(0,2)至(0,0),完成过诃(由图形的对称性关系,可以直接将(3,1)至(3,1)路径翻转,更改对应标号即可) *当然也可以用动态规划求解 *本代码不限定M,N值,可通过修改宏M,N的值,求其他商人(仆人)数与最大过河人数的全部路径 *******************************************************************/ /********************************************************************* * *商人数x < 仆人数y时遭杀人越货，过河失败 *对应可行域为: *x = 0, y = 0…M; elements[]中编号0…M *0 < x < M, y = x; elements[]中编号M+1…2M-1 *x = M, y = 0…M； elements[]中编号2M…3M *图像上表示如下:(共 3*M+1 个点),过河即从3M点到0点 *过河为左下方1/4圆区域 *返回为右上方1/4圆区域 老和尚背了一个美女过河，最后终于忍不住了, 说....... 2017-02-11 启示：学会体谅他人并不困难，只要你愿意认真地站在对方的角度和立场看问题。 4、有个老木匠即将退休，老板舍不得他，要他再建一座房子再走。老木匠虽答应，但心已不在工作上，用的是差料，出的是粗活。当房子建好，老板说这就是他退休的礼物。没想到建的竟是自己的房子，他既羞愧又后悔。 启示：其实，人生每一件事都是为自己而做，要做就做到最好。 5、老鼠掉进了半满米缸，意外让它喜不自禁。确定没有危险后，它一顿猛吃，吃完便睡。就这样，它在米缸里吃了睡、睡了吃。美好的日子总是很快地溜过去，米缸快要见底时，它终究摆脱不了大米的诱惑。最后，米吃完了，它才发现，跳出去只是梦想，一切都无能为力。 启示：我们的生活看似平坦，其实到处都是危机。 6、第一天，小白兔去钓鱼，一无所获。第二天，它又去钓鱼，还是如此。第三天它刚到，一条大鱼从河里跳出来，大叫：你要是再敢用胡萝卜当鱼饵，我就扁死你。 启示：你给的都是你自己“想”给的，而不是对方想要的，活在自己世界里的付出，不值钱! 7、一个朋友是医生，一次癌症手术，打开后发现切不了，只好再缝上。去和病人解释情况，那病人农村来的，听不懂术语，坚持认为手术过了，病就好了。只好让其出院，一年后回访，真好了，癌细胞真消失了。朋友原是医学博士，后来接着读心理学博士去了。 启示：乐观的心态是最好的手术。 8、那年，他坐在咖啡店等朋友，一位女孩走过来问：你是通过王阿姨来相亲的吗?他抬头打量一下她，正是自己喜欢的类型，心想何不将错就错，于是忙答应道：对，请坐。……结婚当天，他坦白当时自己不是去相亲的。老婆笑，说：我也不是去相亲，只是找个借口和你搭讪…… 启示：机遇来了，毫不犹豫，抓住它! 9、两只老虎，一只在笼子里，一只在荒野中。两只老虎认为自己所处环境不好，互相羡慕对方。它们决定交换身份，开始时十分快乐。但不久，两只老虎都死了：一只饥饿而死，一只忧郁而死。 启示：有时，人们对自己的幸福熟视无睹，总是把眼睛看向别人的幸福。其实，你所拥有的正是别人所欣羡的。 10、女生公开投票选班花，相貌平平的小梅发表演说：如我当选，再过几年，在座姐妹可以向自己先生骄傲的说，我上大学时候，比班花还漂亮!结果，她全票当选! 启示：说服别人支持你，不一定要证明比别人都优秀，而是让别人觉得,因为有你，他们变得更优秀更有成就感。 商人过河数学模型 专业信息与计算科学 班级 113010102 姓名罗彪 学号 11301010229 一、问题重述 3名商人各带一名随从乘船渡河，一只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。商人们怎样才能安全过河呢？ 二、问题分析 商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。 三、模型假设 1.每个商人和随从都会划船； 2.只有一条船，且每条船上最多只能乘坐两个人； 3.所有商人与随从之间没有矛盾，不会出现两人不愿意坐一条船的现象； 4.船在渡河的过程中不受外界环境的影响。 四、模型的建立与求解 1.模型建立 k x ~第k 次渡河前此岸的商人数，k y ~第k 次渡河前此岸的随从数 k x , k y =0,1,2,3; k =1,2,… … k S =(k x , k y , c k )~过程的状态， 其中k x , k y , c k 分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中c 取值1表示即将向彼岸运行，为0表示即将向此岸运行 S ~ 允许状态集合，S={(x , y )| x =0, y =0,1,2,3; x =3 ,y =0,1,2,3; x =y =1,2} k u ~第k 次渡船上的商人数 k v ~第k 次渡船上的随从数 k d =(k u , k v )~决策，D={(u , v )| 21≤+≤v u ,k u , k v =0,1,2} ~允许决策集合 k =1,2,… … 因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态 k S 随决策k d 的变化规律是 1+k S =k S +k )1(-k d ~状态转移律 求k d ∈D(k =1,2, …n), 使k S ∈S, 并按转移律由1S =(3,3,1)到达状态 1+n S =(0,0,0(1))。 2.模型求解 本模型使用MATLAB 软件编程求解，运行结果如下 >> chouxiang 输入商人数目:3 农夫过河问题状态图及程序 一、问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？ 二、算法选择 求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。 广度优先： u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。u 要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中， 然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。 u 由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。 三、算法的精化 要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。 四、算法的实现 完成了上面的准备工作，现在的问题变成： 从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。 1、三个人三只狼，要用一艘船从一边运到另一边。一次最多能运两个，返回时船不能为空船，当无论哪一边狼比人多时，狼把人吃掉，平等时不会吃。 2、三个猎人带着一只黑熊，和两只棕熊过河，船很小，每次只能载两人或两熊或一人一熊过河，三个猎人都会划船，黑熊是猎人训练过的，也回划船，但熊的数量一旦超过人的数量，熊就会吃人，怎样可以安全过河？ 3、三个大人分别带一个小孩过河。一艘船，只能载两个单位的人，如果小孩和别的大人在一起而离开自己的大人，就有危险。问如何安全过河？ 4、有一个猎人和一只狼，还有一个男人和一个女人，还有男人养的两只狗和女人养的两只猫，要过一条河，河上只有一条船，船上只能载两人(或者是一个人和一只动物)，如果猎人不在，狼就会咬死所有的人和动物，如果女人不在，男人就会打死两只猫，如果男人不在，女人就会打死两只狗，而且，只有猎人、男人、女人会开船，请问怎么过？【答案】 1、猎人和狼过，猎人回 2、猎人和一只狗过，猎人和狼回 3、男人和一只狗过，男人回 4、男人和女人过，女人回 5、猎人和狼过，男人回 6、男人和女人过，女人回 7、女人和一只猫过，猎人和狼回 8、猎人和一只猫过，猎人回 9、猎人和狼过，OK~~~~ 5、一个猎人，带了一条狗；一个男人，带了两个儿子：一个女人，带了两个女儿；他们要过河，现有一条船，每次过河只能带两个单位（两个人或一人一狗），且只有男人，女人，猎人会划船。 1．猎人不在，狗会咬任何人；2．男人不在，女人会打儿子；3．女人不在，男人会打女 儿；问；如何过河 【答案】男人女人（过河）→男人（返回）→男人儿子（过河）→男人女人（返回）→男人儿子（过河）→男人（返回）→男人女人（过河）→女人（返回）→猎人狗（过河）→男人（返回）→男人女人（过河）→女人（返回）→女人女儿（过河）→男人女人（返回）→女人女儿（过河）→女人（返回）→男人女人（过河） 6、在渡河中，有一个父亲，一个母亲，两个儿子，两个女儿，一个爷爷，一只狗，条件是：一只船只能载两个人；挣船的一定是大人；母亲不在，父亲会打死女儿；父亲不在，母亲会打死儿子；爷爷不在，狗就咬死所有人。而且只有爷爷，父亲和母亲能划船。【答案】1)爷爷带狗先过河的对面，然后爷爷把狗放下自己回来； 2)爷爷再带儿子A过河，将儿子A放下，把狗带回来； 3)爸爸带儿子B过河，将儿子B放下，自己回来； 4)爸爸带妈妈过河，上岸后，妈妈自己回来； 5)爷爷再带狗过河，爷爷和狗都上岸，爸爸回来； 6)爸爸和妈妈再过河，妈妈自己回来； 7)妈妈带女儿A过河，妈妈和女儿A都上岸，爷爷带狗回来； 8)爷爷带女儿B过河，女儿B上岸后，爷爷自己回来； 9)爷爷再带狗过河就可以了。 7、一家六口去旅行（爸爸、妈妈，两个儿子，两个女儿），在路上遇上了歹徒。幸好被一个警察所救，警察逮捕了歹徒。警察和他们正好同路，就带着歹徒一起回去。在回去的路上有一条河，河上有一个竹排，只能坐两个人。 但是：一，警察如果不和歹徒在一起，歹徒就会伤害其他人（但歹徒不会逃跑）二，母亲和儿子在一起时，如果没有父亲在场，母亲会教训儿子 三，父亲和女儿在一起时，如果没有母亲在场，父亲会欺负女儿 四，只有警察，父亲和母亲三个人会开船 八个人要如何顺利渡过这条河呢？ 英伦阳光幼儿园幼教部集教活动计划 执行教师：刘丽 2016年11月9日活动名称《青蛙过河》 活动目标1、学习立定跳远和助跑跨跳的动作技能 2、提高跑、跳的能力，锻炼体能，发展肢体动作的灵活性和协调性 3、在难度逐步提高的游戏中，主动参与，大胆尝试，挑战自我 活动准备绳子-“尾巴”若干、鳄鱼装饰1-2个、平衡木、沙包若干、筐1-2个 活动重难点活动重难点： 重点：指导幼儿双脚用力蹬地，学习向前摆动双臂助力的技巧，两脚同时起跳同时落地 难点：进行助跑跨跳的动作 活动过程一、小蝌蚪变变变 1．我们一起把绳子围成一个大大的、圆圆的池塘，来做“小蝌蚪变变变”的游戏吧。 2．教师边示范边讲解这一热身运动的动作，幼儿观察并跟随教师模仿练习。动作如下：(1)身体趴在地上，双手合放在背上，利用上身的扭动移动身体；(2)蝌蚪长出两条后腿：身体趴在地上，用两条腿连续蹬地并扭动身体前进；(3)蝌蚪长出两条前腿：四肢匍匐爬行；(4)变成青蛙起跳：模仿青蛙跳跃的动作，做全身运动。 二、青蛙跳田埂 1．现在小蝌蚪变成了青蛙。你们知道青蛙有什么本领吗?青蛙不仅会唱歌，还会蹦蹦跳。大家一起来学学青蛙跳田埂。 2．教师用平衡步道作田埂(一块一块间隔、两块两块间隔等)，设置活动路线，通过不断增加高度和宽度来提高活动难度。幼儿可选择不同难度的场地进行练习。教师指导要点如下： (1)要求幼儿从同一方向进行跳跃活动。起跳时，用力蹬地，向前上摆臂；落地时，屈腿全蹲，保持平衡。 (2)根据幼儿的活动情况变化难度，也可根据情况运用自己的肢体动作给幼儿增加难度。注意观察个别能力较弱幼儿的活动情况，并给予适当的鼓励和帮助。 (3)活动场地（红色的圆圈）做小池塘，请小青蛙自主掌控休息时间。(通过本环节，全体幼儿熟练掌握了立定跳远的动作方法，大部分幼儿能够进行助跑跨跳的动作练习，部分幼儿能够利用助跑跨跳的方式跳过较远的距离。) 3．幼儿自由活动，教师巡回观察，通过增加难度和语言指导(如“看看别人是怎么跳的”“怎样跳才正确”“现在步道变宽了，你怎样跳过去”等)，使幼儿的跳跃动作自然地由立定跳远转变为助跑跨跳。教师在活动中要注意观察幼儿的活动量，适时集中请个别幼儿展示动作，并讲解动作要领和安全保护知识，在重点部分示范动作并带领幼儿集体练习。 三、青蛙过小河 1．青蛙越长越大，本领也越来越大。对面田里有许多害虫，现在青蛙要跳过这条小河去捕捉害虫。这条河有的地方宽，有的地方窄，你们看看能从哪里跳过去。如果游来了鳄鱼，你敢不敢从鳄鱼身上跳过去? 2．教师将“尾巴”在地上摆成一条宽窄不等的小河，让幼儿根据自己的活动能力跳过小河，巩固前面游戏中掌握的动作方法，并利用所学动作完成一定的目标，进一步锻炼体能。 第一次活动：幼儿自由跳过小河，教师引导幼儿看看自己能跳过多宽的河面，是用什么方法跳过去的。要求注意安全，避免冲撞。 第二次活动：教师通过增设河面变宽等情景，提高跳小河的难度。幼儿分散活动，教师巡回观察，注意指导个别能力较弱的幼儿大胆尝试。第三次活动：教师胸前贴上鳄鱼图片做鳄鱼，双膝微屈仰卧河中，幼儿依次跳过河捉到害虫——沙包，再从鳄鱼身上跳回来，将害虫放到指定的筐里。 3．幼儿依次游戏，教师根据幼儿的能力，通过改变自己膝盖的高度来调节幼儿跳跃的难度。 四、青蛙回池塘 1. 今天所有的青蛙都很能干，学会了立定跳远和助跑跨跳，跳田埂，过小河，捉害虫，掌握了很多本领。大家累了吧，我们再回到池塘，休 商人过河functionjueche=guohe %程序开始需要知道商人和仆人数； n=input（' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; ifnn>n n=input（'' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; end %决策生成 jc=1;% 决策向量放在矩阵 d 中，jc 为插入新元素的行标初始为 1 ； for i=0:nnn for j=0:nnn if（i+j<=nnn）&（i+j>0）% 满足条D={（u,v） |1<=u+v<=nnn,u,v=0,1,2} d（ jc,1:3）=[i,j ，1] ；%生成一个决策向量立刻扩充为三维； d（ jc+1,1:3）=[-i,-j,-1];% 同时生成他的负向量； jc=jc+2;% 由于生成两个决策向量，则jc 要向下移动两个；end end j=0; end% 状态数组生成 kx=1;% 状态向量放在 A 矩阵中，生成方法同矩阵生成； for i=n:-1:0 for j=nn:-1:0 if((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))%(i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n ))为可以存在状态的约束条件 A(kx,1:3)=[i,j,1];% 生成状态数组集合D' A(kx+1,1:3)=[i,j,0]; kx=kx+2; end end j=nn; end; % 将状态向量生成抽象矩阵 k=(1/2)*size(A,1); CX=zeros(2*k,2*k); a=size(d,1); for i=1:2*k for j=1:a c=A(i,:)+d( j,:); x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))); 课程设计第五题 1．题目探讨农夫过河的问题 2.设计思路 （1）农夫由A到B的情况 （1）带走一个动物后，另外的两个物是不是可以相吃 （2）会不会把刚带回来的又带到对岸去 （3）最后一次带的情况比较的特殊，判断最后一次走后是不是所有的都不在了对岸 （2）农夫从B到A的情况 （1）对岸是不是只有一个物体 （2）对岸是不是有两个物体，若是有两个物体的话他们的处理方式不一样，1。两个物体会相克的，则把羊带走，2如果不是的话那么农夫就空着手回去。 3．应该注意的问题 （1）。在最后的一次带走羊的时候，应该加如一个新的判段 （2）。以及在带回羊的时候，我们要对其进行一个标记，不然的话我们就很容易进行死循环里面 （3）以及每一次从A带东西去B的时候，我们都要对他的位置进行标记下 4．咸受 在对一个问题分析的时候，我们应该先把每一种情况给分析出来，要把问题分析得分面一些，最好是不要落下任何的一种情况，这样我们就可以对每一种情况编写相应的代码了。5．源代码 static int sum(int[] a) { int sum = 0; for (int i = 0; i < a.Length; i++) { sum = sum + a[i]; } return sum; } static void Main(string[] args) { string[] wu = new string[4] { "农夫", "狼", "羊", "白菜" }; int[] a = new int[4] { 3, 1, -1, 1 }; int[] b = new int[4] { 0, 0, 0, 0 }; Console.WriteLine(" 关于农夫过河的问题"); int weizhi = 0; do { if (a[0] == 3) { 数学模型实验—实验报告6 学院：工商学院专业：电气二类（计算机）姓名：辛文辉尚磊张亨 学号：___ 2012484019 2012484091 2012484055 ____ 实验时间：__ 3.18 ____ 实验地点：b3 一、实验项目： Matlab程序设计 安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。 此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。 二、实验目的和要求 a.了解Matlab程序设计有关基本操作 b.掌握有关程序结构 三、实验内容 允许的状态向量 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 允许的决策向量: 0 1 0 2 0 3 0 4 0 5 0 6 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 5 0 5 1 6 0 过河步骤： 第1步：0商5仆过河，0商1仆返回 第2步：5商1仆过河，1商1仆返回 第3步：3商3仆过河，1商1仆返回 第4步：3商3仆过河，1商1仆返回 第5步：3商3仆过河，完成 过河过程中状态变化： 步骤此岸商此岸仆方向彼岸商彼岸仆 1 11 6 ==> -8 -3 中国游客亲历惊呼：越南美女真多可惜养不起(第1页) 中国游客亲历惊呼：越南美女真多可惜养不起来源:东方财富网|2015-07-23 01:45:00 导读： 越南女人追求金钱是第一位，她们想嫁国外改变她们自身的生活环境。越南女人如果感觉男人不好，她们就想逃跑出去，不管是她们国内还是国外都是一个样，不会给对方说什么活，就是让对方找不到人;对于花钱来说，挣钱之后基本上都想花完，之后再上班再挣钱，存钱的想法基本为0，这是对于中国人来说最难容忍的事。 本人在越南胡志明市附近乡下之处呆了一个月左右，所见如下：1、越南女人追求金钱是第一位，她们想嫁国外改 变她们自身的生活环境。 2、越南女人如果感觉男人不好，她们就想逃跑出去， 不管是她们国内还是国外都是一个样，不会给对方说什么活，就是让对方找不到人; 3、对于花钱来说，挣钱之后基本上都想花完，之后再 上班再挣钱，存钱的想法基本为0，这是对于中国人来说最难容忍的事; 4、越南女人对于婚姻来说，很厌终老，特别是对于贫困的人来讲，更是不可能一起生活。嫁于国外的60%以上的基本上会逃离原来的伴，又回到她们原来的国内，再继续找人。 5、南越胡志明附近的人家，不是太贫困，因这里的气候原因，有大量的水果和河流，可以打鱼为生，所以吃鱼天天有，很正常的事，自己买点青菜之类就可以了，这都非常便宜。吃的可能比国内有些地方还好，一餐饭有四到五个菜左右。 6、以目前的越南水平来说，吃饭是没有问题，但存钱基本上不可能，大城市消费很高工资相对低，1500元人民币来说，基本上是高工资，个别是例外; 7、越南女人非常听父母的话，把所有的钱都给家里，这是她们的共性，所以找越南老婆的人如果没有给她们钱，基本上都会跑路，莫明奇妙的消失; 8、越南女人生活在南方的，所生的女孩基本上都非常漂亮可爱。 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A 我们的参赛报名号为（如果赛区设置报名号的话）：J2202 __________ 所属学校（请填写完整的全名）：江西环境工程职业学院 参赛队员（打印并签名）：1. ___________________________________ 2. ___________________________________________ 3. ___________________________________ 指导教师或指导教师组负责人（打印并签名）：教练组_____________________________ 日期：2012年8月9日赛区评阅编号（由赛区组委会评阅前进行编号）： 编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）: 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 商人过河 摘要 本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。 对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律, 最后利用平而坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。 但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了 dijkstm算法,得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。 最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。 关键词渡河问题状态集合决策集合平面坐标dijg算法 过河智力题 过河智力题在一条河边有猎人、狼、男人领着两个小孩，一个女人也带着两个小孩。条件为：如果猎人离开的话，狼就会把所有的人都吃掉，如果男人离开的话，女人就会把男人的两个小孩掐死，而如果女人离开，男人则会把女人的两个小孩掐死。 这时，河边只有一条船，而这个船上也只能乘坐两个人(狼也算一个人)，而所有人中，只有猎人、男人、女人会划船。则问，怎样做才能使他们全部度过这条河? 答案 第一步：猎人与狼先乘船过去，放下狼，回来后再接女人的一个孩子过去。 第二步：放下孩子将狼带回来，然后一同下船。 第三步：女人与她的另外一个孩子乘船过去，放下孩子，女人再回来接男人; 第四步：男人和女人同时过去，然后男人再放下女人，男人回来下船，猎人与狼再上去。 第五步：猎人与狼同时下船，然后，女人再上船。 第六步：女人过去接男人，男人划过去放下女人，回去接自己的一个孩子。 第七步：男人放下自己的一个孩子，猎人和狼上船，回去接男人的另外一个孩子。 第八步：猎人放下狼，接上男人的第二个小孩过去。 第九步：猎人放下小孩，再回去接回狼; 过桥智力题小明一家过一座桥，过桥时是黑夜，所以必须有灯。现在小明过桥要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的妈妈要8秒，小明的爷爷要12秒。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30秒就会熄灭。问：小明一家如何过桥? 答案： 1、小明和小明弟弟过桥，需要花费3秒(小明弟弟慢，花3秒)，计t1 = 3秒，总用时tc=3秒; 2、小明回来，需要花费1秒，记t2=1秒，总用时tc=4秒; 3、小明爷爷和小明妈妈一起过桥，需要花费12秒，记t3=12，总用时tc=16秒; 4、小明弟弟回来，需要花费3秒，记t4=3秒，总用时tc=19秒; 5、小明和小明爸爸一起过桥，需要花费6秒，记t5=6秒，总用时tc=25秒; 6、小明回来，需要花费1秒，记t6=1秒，总用时tc=26秒; 7、小明和小明弟弟一起过桥，需要花费3秒，记t7=3秒，总用时tc=29秒; 这样，在第3步，小明爷爷和妈妈过桥后留下，第5步，小明爸爸过桥后留下，第7步，小明和小明弟弟过桥后，一家人成功在30秒内过桥。 关于过河的智慧故事一位信徒遇到了前所未有的困难， 商人过河的数学模型及编程解决 摘要：M对商仆过河，一只船最多载N人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法） 一．问题提出： 有M对商仆乘船过河，一只船最多载N人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？ 二．假设： 商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。 三．参数： 1．设（x，y）是状态向量，表示任一岸的商人和仆人数，并且x，y分别要大于等于0，小于等于M。 2．设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。 3．设用s表示所有的可取状态向量的集合。 4．设用d表示所有运载向量的集合。 5．设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（sk 属于s）；dk：表示第k步可取转移向量（dk属于 d）； 四．问题分析： 商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。 我们以3名商人为例 设第k次渡河前此岸的商人数为x k，随从数为y k，k=1，2，…，x k，y k =0，1，2，3，将二维向量S k = （x k，y k）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为： 课程设计题目：农夫过河 一．问题描述 一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。过河有以下规则： (1)农夫一次最多能带一样东西（或者是狼、或者是羊、或者是白菜）过河； (2)当农夫不在场是狼会吃羊； (3)当农夫不在场是羊会吃掉白菜。 现在要求为农夫想一个方案，能将3样东西顺利地带过河。从出事状态开始，农夫将羊带过河，然后农夫将羊待会来也是符合规则的，然后农夫将羊带过河仍然是符合规则的，但是如此这般往返，搜索过程便进入了死循环，因此，在这里，采用改进的搜索算法进行搜索。 二．基本要求 (1)为农夫过河问题抽象数据类型，体会数据模型在问题求解中的重要性； (2)要求利用数据结构的方法以及Ｃ＋＋的编程思想来完成问题的综合设 计； (3)在问题的设计中，使用深度优先遍历搜索方式，避免死循环状态； (4)设计一个算法求解农夫过河问题，并输出过河方案； (5)分析算法的时间复杂度。 三．概要设计 (1)数据结构的设计 typedef struct // 图的顶点 { int farmer; // 农夫 int wolf; // 狼 int sheep; // 羊 int veget; // 白菜 }Vertex; 设计Vertex结构体的目的是为了存储农夫、狼、羊、白菜的信息，因为在遍历图的时候，他们的位置信息会发生变化，例如1111说明他们都在河的北岸，而0000说明他们都在河的南岸。 t ypedef struct { int vertexNum; // 图的当前顶点数 Vertex vertex[VertexNum]; // 顶点向量（代表顶点） bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 }AdjGraph; // 定义图的邻接矩阵存储结构 存储图的方法是用邻接矩阵，所以设计一个简单的AdjGraph结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。 (2)算法的设计 深度优先遍历基本设计思想：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的1/12边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 程序中的深度优先遍历算法如下： void dfsPath(AdjGraph *graph, int start, int end) // 深度优先搜索从u到v的简单路径 //DFS--Depth First Search { int i = 0; visited[start] = true; //标记已访问过的顶点 if (start == end) 日本女生的名字.txt骗子太多，傻子明显不够用了。我就是在路上斩棘杀龙游江过河攀上塔顶负责吻醒你的公主。日本女生的名字2009-03-21 12:34あ AI あい爱 AIKO あいこ爱子 AINA あいな爱奈 AIMI あいみ爱美 AIRI あいり爱理 AOI あおい葵 AKANE あかね茜 AKI あき亜纪/秋 AKIKO あきこ亜希子/亜希子/亜纪子/安喜子/安纪子/秋子 AKINA あきな秋奈 AKIRA あきら晶 AKIHA あきは秋叶 AGURI あぐり亜栗 AKO あこ亜子 ASAKA あさか浅香/朝香 ASAGI あさぎ（本意为“浅黄色”） ASAKO あさこ安佐子/浅子 ASAMI あさみ朝美/麻美/亜佐美 ASUKA あすか明日香/（男子名时译为“飞鸟”） ASUMI あすみ阿澄 AZUMI あずみ安昙 ATSUKO あつこ温子/厚子/敦子 ATSUMI あつみ敦美 ADO あど AMARI あまり AMI あみ亜美 AMIKA あみか AMIRU あみる AYA あや亜矢 AYAKA あやか绫香/彩香 AYAKO あやこ亜矢子/绚子/绫子/彩子/苑子 AYANA あやな AYANO あやの绫乃/绫野 AYAME あやめ（本意为“菖蒲”） AYUKO あゆこ鮎子/歩子 AYUMI あゆみ歩美/亜由美 AYUMU あゆむ歩 ARI あり有/亚理 ARISA ありさ亜理纱/阿丽莎(直译) AN あん安 ANJI あんじ ANJYU あんじゅ安寿 ANZU あんず杏子 ANNA あんな安奈/（外国人名时为“安娜”） い IORI いおり伊织 IKUE いくえ育恵/郁恵/郁江 IKUKO いくこ育子/郁子/ IKUMI いくみ伊久美/育美/郁美 IZUMI いずみ泉/泉美 ITSUMIいつみ逸美 IRUMI いるみ う UNO うの宇野/鹈野 URARA うららえ EIKO えいこ映子/栄子/永子/瑛子/英子 EMI えみ栄美/絵美/恵美/江美 EMIKO えみこ栄美子/栄美子/絵美子/恵美子/江美子/笑子/笑美子EMIRI えみり恵美理 ERI えり恵理/恵里 ERIKA えりか恵里香 ERIKO えりこ英里子/絵里/絵里子/恵利子/恵理子/恵里/江利子/江里子ERISA えりさ恵理沙/絵梨沙 ERINA えりな絵理奈 ERIN えりん絵凛 ERU える（还好不是ERO... = =） ERUMI えるみ ERENA えれな（外国人名“爱莲娜”） EREN えれん（外国人名“艾琳”）お OTOHA おとは音叶/音羽 OTOME おとめ乙女 か行 KAORI かおり薫理/香织/香里 KAORU かおる薫 KAZAMI かざみ风见 KAZUE かずえ一恵/和恵，和江 KAZUKO かずこ佳寿子/和子 KAZIKI かずさ和纱 KAZUNA かずな和奈/和菜 KASUMI かすみ霞/香澄 KAZUMI かずみ一美/和美 KATSUMIかつみ胜美 KANA かな加奈/香奈 KANAE かなえ香奈恵/香苗 摘要：M对商仆过河，一只船最多载N人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法） 一．问题提出： 有M对商仆乘船过河，一只船最多载N人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？ 二．假设： 商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。 三．参数： 1．设（x，y）是状态向量，表示任一岸的商人和仆人数，并且x，y分别要大于等于0，小于等于M。 2．设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。 3．设用s表示所有的可取状态向量的集合。 4．设用d表示所有运载向量的集合。 5．设用表示从此岸到彼岸，作减；用表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（sk 属于s）；dk：表示第k步可取转移向量（dk属于d）； 四．问题分析： 商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。 我们以3名商人为例 设第k次渡河前此岸的商人数为x k，随从数为y k，k=1，2，…，x k，y k =0，1，2，3，将二维向量S k =（x k，y k）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为： 目录 引言 (2) 1 问题描述 (3) 基本要求 (3) 2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性； (3) 2.2设计一个算法求解农夫过河问题，并输出过河方案； (3) 3 概要设计 (3) 3.1数据结构的设计。 (3) 3.1.1农夫过河问题的模型化 (3) 3.1.2 算法的设计 (4) 4、运行与测试 (6) 5、总结与心得 (7) 附录 (7) 参考文献 (13) 引言 所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到北岸。一条小船只能容下他和一件物品, 只有农夫能撑船。问农夫怎么能安全过河, 当然狼吃羊, 羊吃白菜, 农夫不能将这两种或三种物品单独放在河的一侧, 因为没有农夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。 1 问题描述 一个农夫带一只狼、一棵白菜和一只羊要从一条河的南岸过到北岸，农夫每次只能带一样东西过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃白菜，请为农夫设计过河方案。 基本要求 2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性； 2.2设计一个算法求解农夫过河问题，并输出过河方案； 3 概要设计 3.1 数据结构的设计。 3.1.1农夫过河问题的模型化 分析这类问题会发现以下特征: 有一组状态( 如农夫和羊在南, 狼和白菜在北) ; 从一个状态可合法地转到另外几个状态( 如农夫自己过河或农夫带着羊过河) ; 有些状态不安全( 如农夫在北, 其他东西在南) ; 有一个初始状态( 都在南) ; 结束状态集( 这里只有一个, 都在北) 。 问题表示: 需要表示问题中的状态, 农夫等位于南P北( 每个有两种可能) 。可以采用位向量, 4 个二进制位的0P1 情况表示状态, 显而易见, 共24= 16种可能状态。从高位到低位分别表示农夫、狼、白菜和羊。0000( 整数0) 表示都在南岸, 目标状态1111( 即整数15) 表示都到了北岸。有些状态0011,0101, 0111, 0001, 1100, 1001 是不允许出现的, 因为这些状态是不安全状态。根据上述条件可以画出系统的状态图如图1 所示。 图1 系统状态转换图 其中双向的箭头表示状态可逆, 即农夫可以带 着某种东西过去, 也可以带着该东西回来。箭头上的字母表示农夫所携带的东西: f( farmer) , w(wolf) , g(goat) , c( cabbage) 分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。现在的问题转化为: 找一条合法路径( 相邻状态之间的转移合法) , 从开始状态到某个结束状态, 途中不经过不安全状态。农夫过河数据结构
商人过河问题
老和尚背了一个美女过河
商人过河数学模型
农夫过河问题状态图及程序
过河问题
中班户外活动教案及反思《青蛙过河》
商人过河问题matlab程序
C# 关于农夫过河的问题
商人过河实验报告
中国游客亲历惊呼：越南美女真多可惜养不起(第1页)
商人过河优化模型.docx
过河智力题
最新商人过河的数学模型及编程解决
农夫过河问题
日本女生的名字
商人过河的数学模型及编程解决Word版
数据结构课程设计报告(农夫过河)