课程设计(**)
题目名称三人三鬼过河问题。
课程名称 c语言程序课程设计。
学生姓名宁亚民。
学号 1141303090
系 、专业信息工程系、信息大类。
指导教师李仲生。
2024年 12月 20 日。
目录。1问题描述2
2实验目的2
2.1实验要求2
3实验思路2
3.1程序流程图3
4实验程序4
5测试分析10
6实验总结13
参考文献13
1题目与要求。
人鬼过河问题。
河的一边有三个人和三个鬼，河中有一小船，每次最多能乘坐2个人或鬼，而且至少要有一个人或鬼船才能行驶。请设计一种算法，把人和鬼都送到对岸。注：
不论是在河边、船上，如果人鬼数量相同，则鬼和人能和谐相处，鬼不吃人，否则，鬼吃掉人。要求算法能给出整个运送过程，包括每次船行驶的方向（是驶向对岸还是返回），船上的人和鬼数量。
2实验目的。
本次课程设计的主要目的是综合运用所学的c语言和数据结构知识解决一个比较实际的简单问题，侧重对c语言和数据结构等相关内容的综合应用，使学生能进一步熟悉掌握c语言和数据结构的基本语法，进一步提升编程能力并逐步培养编程思维，进而不断提高学生解决问题的能力，并为以后的语言学习打下良好的基础。
2.1实验要求。
1.要求我们独立完成课程设计的主要内容；
2. 按照实验课表安排进行，不得无故旷课；
3．按照选题规则确定课程设计题目，不可随意更换，但可在完成规定的任务之后，根据个人兴趣选做其它题目；
4．严格按照报告格式撰写课程设计报告；
5．程序实现方式可以自选，可采用任意组合方式完成。
3实验思路。
人鬼过河问题实际上可以考虑为状态之间的迁移，或者是构建一个有向图，然后在图中寻找可行的路径。
我们把当前岸边作为左岸，河的对岸作为右岸。
那么状态包含两个因素，一个是左岸上人鬼的数量(右岸人鬼的数量可以由左岸人鬼数量计算得出)，另一个是船在左岸还是在右岸。
迁移表现为从人鬼从左岸渡船到右岸，或者人鬼从右岸渡船到左岸。
因为鬼多于人的时候会吃人，所以不是任意的人和鬼的数量的组合都是合理的状态。
程序中首先找到所有合理的状态，然后再找到所有状态到状态可行的迁移，最后深度搜索所有迁移，寻找到从开始状态到结束状态间的可行路径。
程序的输出也是按照这个步骤，分成了三个部分，分别是可行状态、可行迁移，可行路径。
h-human人。
g-ghost鬼。
b-boat船。
lb-left boat船在左边。
rb-right boat船在右边。
3.1程序流程图。
安全过河流程图。
4实验程序。
#include <>
#include <>
#include <>
#define lboat '*
#define rboat '
typedef struct hgb_struct
hgb;
int arr_len;
int state_count;
hgb *state; /arr_len];
int *transfer; /arr_len][arr_len];
int stack_sp;
hgb *stack; /arr_len];
#define transfer_ref(i, j) (transfer[i * arr_len + j])
#define stack_init() stack_sp = 0)
#define stack_push(hgb) (stack[stack_sp++]hgb))
#define stack_pop() stack[--stack_sp])
#define stack_top(hgb) (stack[stack_sp - 1])
#define stack_find(hgb, result) for(result = stack_sp - 1; result >=0; result--)
#define state_find(hgb, result) for(result = state_count - 1; result >=0; result--)
int search(hgb hgb, int n)
else
printfn");
stack_pop();
return -1;
else
state_find(hgb, index);
stack_push(hgb);
for(i = 0; i < state_count; i++)
stack_pop();
return 0;
void human_ghost(int human_ghost_count, int boat_capacity)
int i, j;
int hl, gl, hr, gr;
int tmp;
int result;
stack = null; /arr_len];
state = null; /arr_len];
transfer = null; /arr_len][arr_len];
arr_len = 2 * human_ghost_count + 1) *human_ghost_count + 1));do
state = hgb *)malloc(arr_len * sizeof(hgb));
if(state ==null) break;
stack = hgb *)malloc(arr_len * sizeof(hgb));
数据结构课程设计
课程设计说明书 题目哈夫曼编码问题的设计和实现。课程名称数据结构课程设计。院 系 部 中心。专业。班级。学生姓名。学号。设计地点。指导教师。设计起止时间 2008 年6月 2日至 2008 年 6月 6 日。目录。1 问题描述 2 1.1 题目内容 2 1.2 基本要求 2 1.3 测试数据 2 2...
数据结构课程设计
数据结构 课程设计。实验报告。学院 信息工程学院。班级 姓名 学号 指导老师 题目2 一元多项式的计算。1 实验目的。1 掌握链表的灵活运用 2 学习链表初始化和建立一个新的链表 3 知道怎样去实现链表删除结点操作与插入结点 4 理解链表的基本操作 包括数据域数据的相加 并能灵活运用。2 实验内容。...
数据结构课程设计
班级 信计 1102 姓名 李娜娜。学号 1108060209 设计日期 2013.07.15 西安科技大学计算机学院 1.实验题目 编制一个演绎扫雷游戏的程序。2.问题描述。做一个n x m的扫雷游戏，每个方格包含两种状态 关闭 closed 和打开 opened 初始化时每个方格都是关闭的，一个...