|
|
我在写老师布置的数据结构作业，题目是这样的
1、问题描述
假若有n个正常人和n个精神病患者准备过河，但只有一条能容纳c个人的小船，为了防止精神病人侵犯正常人，要求无论在何处，正常人的人数不得少于精神病患者的人数（除正常人人数为零），且假定两种人都会划船，试设计一个算法，确定他们是否能渡过河去，若能，则给出一只小船来回次数最少的最佳方案。
2、基本要求
输入：正常人人数（即精神病患者人数）n。小船一次最多载客人数c。
输出：若问题无解，则显示渡河失败信息，否则，输出一组最佳答案，用三元组（x1,x2,x3）表示渡河过程中的状态。并用箭头输出这些状态之间的迁移。
其中：x1表示当前岸上的正常人人数，x2表示当前岸上的精神病人人数，x3表示小船的位置（0表示目的岸，1表示起始岸）。
3、算法思想：
（1）算法思想
1）建立空队列，将起始状态入队列
2）取出对头元素，根据“基本要求”产生各种可能的状态，由判断合法条件：x1==0或x1==n或x1==x2判断各种状态的可达、合法性，将可达、合法的状态入队列。如果所入队列状态为目标状态，则搜索成功，转3）
3）按目标状态<-.......<-起始状态的顺序将渡河过程输出，成功退出。
4）若没有产生出目标状态，则失败退出。
（2）数据结构
用双链表作为队列
typedef struct node
{
int a,b,c,no,prec;
struct node *pre;
struct node *next;
}qu;
typedef struct
{
qu *front,*rear;
}op;
4、运行结果
以正常人和精神病患者人数都为2，小船一次最多载人人数为2为例，程序运行结果为：
x1 x2 x3 no prec
2， 2， 0， 8， 7 （目标状态）
1， 1， 1， 7， 6
2， 1， 0， 6， 5
2， 1， 1， 5， 2
0， 2， 0， 2， 1
2， 2， 1， 1， 0 （起始状态）
x1表示当前岸上正常人人数，x2表示当前岸上精神病人人数，x3表示小船位置，no表示状态编号，prec表示当前状态的前趋。
以上就是题目，我写了一个程序，想来想去都没问题了，编译连接也没问题，但是运行以后windows就跳出一个窗口，说 NTVDM CPU 遇到无效的指令。
cs:0000 IP:0077 OP:f0 37 05 12 02
天那
不明白怎么回事了，望各位救救我啊~~~~~~~~~~~~~~~
不胜感激！！！
我写的程序如下：
- #include <stdio.h>
- #include <stdlib.h>
- #include <math.h>
- typedef
- struct node
- {
- int a;
- int b;
- int c;
- int no;
- int prec;
- struct node *next;
- struct node * pre;
- }
- qu;
- typedef
- struct
- {
- qu *front;
- qu * rear;
- }
- op; /*以上定义了两个结构体，分别作为链节点 和 指示首尾的标志*/
- /*正常人人数（即精神病人数）*/
- int n; /*小船最大载客数*/
- int c; /*定义的用来在born（）函数中记录产生多少子状态的全局变量*/
- int sonnum;
- qu *redBox; /*用来放置初始状态*/
- op * flag; /*指示链队列*/
- void enqueue( qu * ); /*三个函数声明（declaration）*/
- qu ** born( qu * ); /*分别代表 入队、衍生、打印*/
- void prt( void );
- int main(void) /*主函数*/
- {
- int bank = 1; /*指示当前岸*/
- int count; /*后面要用到的一个计数变量*/
- qu * seed; /*用来给born（）带去入口参数*/
- qu ** tree; /*用来放置衍生出来的状态*/
- input: /*用户输入数据*/
- printf("\nPlease input the N:");
- scanf("%d", &n);
- printf("\nPlease input the C:");
- scanf("%d", &c);
- if( n<1 || c<=1 ) /*判断是否合法，若非法则重新输入*/
- {
- printf("\nBad data!\nPlease re-input.\n");
- goto input;
- }
- flag->front = (qu *)malloc( sizeof(qu) ); /*建立空队列*/
- flag->rear = flag->front;
- flag->front->pre = NULL;
- flag->front->next = NULL;
- redBox = (qu *)malloc( sizeof(qu) ); /*诞生初始状态*/
- redBox->a = n;
- redBox->b = n;
- redBox->c = 1;
- redBox->no = 1;
- redBox->prec = 0;
- redBox->next = flag->front->next; /*初始状态入队列*/
- redBox->pre = flag->front;
- flag->front->next = redBox;
- flag->rear = redBox;
- if( flag->front->next->a == n /*判断队首元素（非对头）是否目标状态*/
- && flag->front->next->b == n
- && flag->front->next->c == 0
- )
- prt(); /*若是目标状态则打印*/
- seed = flag->front->next; /*用seed先指向队首元素*/
- while( seed != flag->front ) /*队首元素产生子状态入队，子状态再产生子状态入队*/
- { /*如此往复，直到seed指向对头元素*/
- while( seed->c == bank ) /*当前岸相同的连续若干状态*/
- {
- tree = born( seed ); /*产生子状态*/
- for( count=0; count<sonnum; count++ ) /*产生多少状态（由sonnum从born（）中得到）就入几次队列*/
- {
- enqueue( tree[count] ); /*入队*/
- if( flag->front->next->a == n
- && flag->front->next->b == n
- && flag->front->next->c == 0
- )
- prt(); /*判断是否目标状态，是则打印*/
- }
- seed = seed->pre; /*seed向前挪一格*/
- }
- bank = !bank; /*到下一相同岸连续状态区间内，bank改变*/
- }
- printf("\nThere is no way to let them pass the river!\n"); /*若以上没有产生目标状态，提示无结果*/
- getch();
- return 0; /*无结果结束*/
- }
- void enqueue( qu *grayBox ) /*定义入队列函数*/
- {
- grayBox->next = flag->front->next;
- grayBox->pre = flag->front;
- flag->front->next->pre = grayBox;
- flag->front->next = grayBox;
- }
- qu **born( qu *parent ) /*定义衍生函数*/
- {
- qu ** son; /*把son = NULL的话，就不会出现警告了，但是运行窗口就“死”了*/
- qu * grandpa; /*指向当前状态的前趋状态*/
- qu * light; /*搜索用的指针变量*/
- int counter1;
- int counter2;
- int counter = 0; /*三个计数变量，分别代表a，b和产生合法状态数*/
- int num = parent->no; /*当前状态序号，准备给产生子状态编号和前趋号用*/
- int b = !(parent->c); /*产生的子状态都是在当前状态的对岸*/
- light = flag->rear; /*light指向队尾*/
- while( light != flag->front ) /*搜索整个队列，根据当前状态的前趋号找当前状态的父状态节点*/
- {
- if( light->no == parent->prec )
- grandpa = light;
- light = light->pre;
- }
- for( counter1=0; counter1<n; counter1++ ) /*用双重循环产生当前状态可能产生的各种*/
- { /*状态，再用几个if去掉当前状态的父状态*/
- for( counter2=0; counter2<n; counter2++ ) /* 和非法的状态 */
- {
- if( counter1==0 || counter1==n || counter1==counter2 ) /*见基本要求*/
- {
- if( abs( (n-counter1)+(n-counter2)-(2*n) ) <= c ) /*一个岸一次的人数变化应小于等于最大船载数*/
- {
- if( counter1 == grandpa->a && counter2 == grandpa->b ) /*去掉当前状态的父状态*/
- continue;
- son[counter] = (qu *)malloc( sizeof(qu) ); /*产生新状态*/
- son[counter]->a = counter1;
- son[counter]->b = counter2;
- son[counter]->c = b;
- son[counter]->prec = parent->no;
- son[counter]->no = (++num);
- counter++; /*记录产生了多少个子状态*/
- }
- }
- }
- }
- sonnum = counter; /*把总共产生多少个子状态传递给全局变量*/
- /*给main中while循环*/
- return son; /*返回指向子状态的指针数组的首地址*/
- }
- void prt( void ) /*定义打印函数*/
- {
- int temp = flag->front->next->prec; /*获得目标状态前趋号*/
- qu * feet; /*搜索用的指针*/
- feet = flag->front->next; /*先指向对首的目标状态*/
- printf("\nX1 X2 X3 No Prec\n");
- printf("%d %d %d %d %d\n", /*先打印出目标状态*/
- flag->front->next->a,
- flag->front->next->b,
- flag->front->next->c,
- flag->front->next->no,
- flag->front->next->pre
- );
- while( feet != flag->rear->next ) /*根据前趋号来搜索路径*/
- {
- if( feet->no == temp )
- {
- printf("%d %d %d %d %d\n",
- feet->a,
- feet->b,
- feet->c,
- feet->no,
- feet->prec
- );
- temp = feet->prec;
- }
- feet = feet->next;
- }
- exit (0); /*搜索成功退出*/
- }
|
|
IP卡
狗仔卡
发表于 2003-5-18 10:44:59
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主