int stretch(struct SPQ *ntx) { int fsr , fpr ; //在右岸上的人数 int fsl , fpl ; //在左岸上的人数 int sst , spt ; //出发时在船上的人数 int ssr , spr ; //返回时船上的人数 struct SPQ *newnode; for (sst = 0 ; sst <= 2 ; sst++) //讨论不同的可能性并判断是否符合条 件 { fsr = ntx -> sr; fpr = ntx -> pr;
unopened -> pl = 0; unopened -> sst = 0; unopened -> spt = 0; unopened -> ssr = 0; unopened -> spr = 0; unopened -> loop = 0; printf("题目：设有n个传教士和m个野人来到河边，打算乘一只船 从右岸到左岸去。\n"); printf("该船的负载能力为两人。在任何时候，如果野人人数超过传 教士人数，野人\n"); printf("就会把传教士吃掉。他们怎样才能用这条船安全地把所有人 都渡过河去呢-\n"); printf("\n默认的n、m值皆为3\n"); for(; ;) {printf("\n是否修改？(Y/N)：");
提示：可自左至右顺序扫视字符串s，逐个找出单字（单字
开始位置和单字长度），当该单字的长度比已找到的单字更长
时，就从头至尾扫视字符串t，在从t中找出与该单字长度相
等、字符相同的单字后，登录该单字的开始位置和长度，并回
到s，在其中找一个更长的单字，上述寻找过程直至字符串s扫
视结束，最后输出找到的单字。
22 2 4 4 4 8 3 8 1 1 1 1 2 1 则它的压缩数组为
3 2 3 4 -3 8 3 8 4 1 -2 2 1 4 找最长相同单字 从给定的两个由英文单字（词）组成的字符串s和t中，找出 其中都包含的最长的相同单字（同一字母的大小写视作不同字 符）。约定单字全由英文字母组成，单字之间由一个或多个空 白符分隔。
{ntx = unopened; //从待扩展链表中提取最前面的一个 if(ntx->loop == maxloop) return 0; addtoopened(ntx); //将ntx加入已扩展链表，并将这个节点从待 扩展链表中去掉 flag = stretch(ntx); //对ntx进行扩展, 返回-1,0,1 if(flag == 1) return 1; } }
int stretch(struct SPQ* ntx); void recorder( );
void main( ) { int flag; //标记扩展是否成功 for( ; ; ) { initiate( ); flag = search ( ); if(flag == 1)
{ recorder( ); releasemem( ); showresult( ); goon( ); } else
…
120
提示：计算k!采用对已求得的（k-1）！的结果连续累加 k-1次后求出。例如，4！=24，则计算5！对原来的24再累加4
次24后得到120。为了控制累加的位数，另引入整型变量用于 记录当前（k-1）!的位数。
2 银行卡问题 某银行共发出M张储蓄卡，每张储蓄卡拥有唯一的卡号，
每天每张储蓄卡至多支持储蓄卡持有者的N笔“3;3]中的每一行存放一张储蓄卡 的有关信息，其中：
{unopened -> sr = x; break; } else printf("\n输入值应大于0！\n请重新输入"); }
break; } if(choice=='N') break; } }
int search( ) { int flag; struct SPQ *ntx; //提供将要扩展的结点的指针 for( ; ; )
fsl = ntx -> sl; fpl = ntx -> pl; if ((sst <= fsr) && (( 2 - sst) <= fpr))//满足人数限制 { spt = 2 - sst;
fsr = fsr - sst; fpr = fpr - spt; if((fpr == 0) && (fsr == 0)) //搜索成功
这个问题还可以拓展为m个野人和n个传教士，而船一次可 以装下r个人的情况。
#include <stdio.h> #include <stdlib.h> #define maxloop 100 //最大层数 #define pristnum 3 //传教士默认值 #define slavenum 3 //野人默认值 struct SPQ { int sr,pr; //船运行一个来回后河右岸的野人、传教士的人数
2．算法分析与设计
3．参考程序
4．运行结果 图 是由本程序计算出的3个传教士和3个野人的安全渡河
方案。
图14-1 野人渡河问题的解答
5．总结与体会
附：野人渡河程序
3个野人和3个传教士来到河边，打算乘一只船从右岸到左 岸去。该船的负载能力为两人。在任何时候，如果野人人数超 过传教士人数，野人就会把传教士吃掉。他们怎样才能用这条 船安全地把所有人都渡过河去呢？
选作题：
1大数阶乘 对给定的n(n≤100)，计算并输出k!(k=1,2, ……,n)的全部有 效数字，因k!的值可能很大，故采用一维数组存计算结果。设 数组的每个元素存储k!的一位数字，并约定从低位到高位依次 存于数组的第一个位置、第二个位置、……。例如，5！ =120，在数组a中的存储形式为：
a[2] a[1] a[0]
5 寻找长整数
设A的个位数a[0]为指定的数p（取值分别为2，3，4，…，
9，）。若将A的个位数字移到其他各位数字之前，则其数
值为原数值的A的p倍。例如，p为4，则A为102564（各位
数字分别存入a[5],a[4],
…,a[0]之中），有
102564*4=410256。
寻找从 a[0]=p出发，用p乘已确定的位数的数值可推出其前1
的数字，逐位进行，直到用P乘a[n-1]等于a[0]，递推计算结
束，A即为：
a[n-1]a[n-2] … …a[0]
数据结构与算法
课程设计报告
专业班级： 学号： 姓名：
日期：
实例 报数问题
1．问题描述 设有n个人围坐一圈并按顺时针方向1-n循环报数。若从第1 个人开始报数，凡是报的数字是7的倍数（如14、49）或其中 包含7（如17、71），则此人出圈，再从他的下一个人继续报 数，如此进行下去，直到只有一个人为止。 设计程序，要找到那个能留到最后的人的原始位置号与最 后应该报的数字。
2、当输入一棵二叉树的前序序列和中序序列（或后序序列 和中序序列），请设计自动生成二叉树的程序。
要求：在程序中以简单图形的方式输出该二叉树。 2、 对一个项目数是n(10<n<15)的工程，构造对应的AOV
网，然后设计程序求拓扑序列，求出关键路径。 要求：项目数n与各项目的时间与前期项目关系可动态输 入（在设计阶段可在程序中暂时给定）。
int sl,pl; //船运行一个来回后河左岸的野人、传教士的人数 int ssr,spr; //回来(由左向右时)船上的人数 int sst,spt; //去时(由右向左时)船上的人数 int loop; //本结点所在的层数 struct SPQ *upnode ,*nextnode; //本结点的父结点和同层的下一个 结点的地址 } spq; int loopnum; //记录总的扩展次数 int openednum; //记录已扩展节点个数 int unopenednum; //记录待扩展节点个数 int resultnum; struct SPQ *opened; struct SPQ *oend; struct SPQ *unopened; struct SPQ *uend; struct SPQ *result; void initiate( ); void releasemem( ); void showresult( ); void addtoopened(struct SPQ *ntx); int search( ); void goon( );
{ printf("无法找到符合条件的解"); releasemem( ); goon( ); } } } void initiate( ) { int x; char choice; uend = unopened = (struct SPQ*)malloc(sizeof(spq)); if(uend==NULL) { printf("\n内存不够! \n"); exit(0); } unopenednum=1; openednum=0; unopened -> upnode = unopened; //保存父结点的地址以成链表 unopened -> nextnode = unopened; unopened -> sr = slavenum; unopened -> pr = pristnum; unopened -> sl = 0;
{ newnode = (struct SPQ*) malloc (sizeof(spq)); if(newnode==NULL) { printf("\n内存不够！\n"); exit(0); } newnode -> upnode = ntx; //保存父结点的地址以成链表 newnode -> nextnode = NULL; newnode -> sr = 0; newnode -> pr = 0; newnode -> sl = opened -> sr; newnode -> pl = opened -> pr; newnode -> sst = sst; newnode -> spt = spt; newnode -> ssr = 0; newnode -> spr = 0; newnode -> loop = ntx -> loop + 1; oend -> nextnode = newnode; oend = newnode; openednum++; return 1; } else if ((fpr - fsr) * fpr >= 0) //判断是否满足传教士人数大于或等 于野人人数 {fsl = fsl + sst; fpl = fpl + spt; for (ssr = 0 ; ssr <= 1 ; ssr++) //返回 { int ffsl , ffpl;