商人过河问题/****************************************************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圆区域*点成中心对称分布，对称的点过河、返回时点的分布情况互为相同/\ y：仆人|| 编号:M* * M\ \3M| | .* * * .* * * 2\M+2\2M+2* * * 1\M+1\2M+1-*------------------*--------> 0\ \2M|0 M x：商人|**********************************************************************/#include <stdio.h>#include <stdlib.h>#include <time.h>#define M 3/* M为商人仆人对数*/#define N 2/* N为渡河时船的最大容量*/#define STACK_Vol 30/* 栈的容量*/#define DEBUG 0/* 调试时用的宏，用于查看unit中可到达的各点编号*/enum status{ NO, YES};/* 标记elements中的go_flag(back_flag)*//* 以NO=0标记过河(返回)时没到过该点,YES=1标记过河(返回)到过该点*/struct Element{int* go; /* 存储过河时可以到达的点的动态空间指针，以-1标记结束*/int* back; /* 存储返回时可以到达的点的动态空间指针，以-1标记结束*/enum status go_flag; /* 以NO=0标记为未曾从该点过河,YES=1为曾从该点过河*/enum status back_flag; /* 以NO=0标记为未曾从该点返回,YES=1为曾从该点返回*/}elements[3 * M + 1];/*********************************************************************** *******************对可行域的点对行编号，全局变量，已被自动初始化为NULL和0*考虑到N一般较小，每点到达的点也较少，所以进行初始化并存储在动态分配的空间中*只考虑较小的N，对较大的N( >= 4)，解题为平凡的，程序空间时间复杂度较大，不用本程序求解*********************************************************************** *****************/struct Stack{int array[ STACK_Vol + 1]; /* 存储经过的路径,注意:最多为30步*/int mark[ STACK_Vol + 1]; /* 存储经过对应点的链表中下次要走的元素标号*/ int top; /* 栈顶指针,指向使用的空间*/}stack;/*************************** 找出路径要用到的运算栈***************************/int path_ok; /* 记录找到路径数量*/int up_bound = 3 * M; /* 数组中最大点的下标(上界*/void unit( void); /* 初始化各点的可到达的点*/void path( void); /* 找出无环路的过河路径*/void print_path( int *); /* 打印出过河的路径*/void delete_link( void); /* 释放动态分配的内存*/int main(){clock_t start, finish;double duration; /* 测量一个事件持续的时间*/start = clock(); /* 取初始时刻时间*/unit();path();if( path_ok < 1)printf(" 没有可行路径!!!\n");delete_link();finish = clock(); /* 取完成时刻时间*/duration = (double)(finish - start) / CLOCKS_PER_SEC;printf( "\n\nProgramme Execute Time:\t%.3f seconds\n", duration );getchar();return 0;}void unit( void){int *p1, *p2;int head, rear;int vert, level, diag, sum; /* 记录垂直、水平、斜向方向上所能到的点的个数*/ int i; /* 循环变量*//* 0为目标点，不进行初始化*//* up_bound为出发点，只考虑过河情况*/level = N - M;/* level < 0，商人无法全部过河;* = 0，商人刚好全部过河，后只能从M点原样返回(无其他返回点)，所以不考虑该点;* > 0，商人全部过河外可以有仆人过河*/vert = M > N ? N : M;diag = N >> 1;if( level < 0)level = 0;sum = vert + diag + level + 1;if( sum > 1){elements[up_bound].go = p1 = ( int *) malloc( sum * sizeof( int));for( i = 1; i <= level; i++)*p1++ = M - i;for( i = 1; i <= vert; i++)*p1++ = up_bound - i;for( i = 1; i <= diag; i++)*p1++ = (M << 1) - i;*p1 = -1;}//iffor( head = 1, rear = up_bound - 1; head < M; head++, rear--){/* 先计算head过河时的情况:只有仆人过河;对应的rear为返回时的情况:只商人返回*/vert = head > N ? N : head;sum = vert + 1;if( sum > 1){elements[head].go = p1 = ( int *) malloc( sum * sizeof( int));elements[rear].back = p2 = ( int *) malloc( sum * sizeof( int));if( p1 == NULL || p2 == NULL){fprintf( stderr, " 动态分配内存失败!\n\n");delete_link();exit( EXIT_FAILURE);}//iffor( i = 1; i <= vert; i++){*p1++ = head - i;*p2++ = rear + i;}//for(i)*p1 = *p2 = -1;}//if/* 再计算head返回时的情况*//* 只仆人返回*/vert = M - head;if( vert > N)vert = N;/* 商人返回一个或全部时的情况*/if( N >= M){ /* 商人可以全部返回*/level = 2 + N - M;if( head + N - M > M)level = 2 + M - head;}else if( N >= head)level = 1;elselevel = 0;/* 仆人商人返回至等数量,但不包括开始时的情况*/diag = ( N - head) >> 1;if( diag < 0)diag = 0;else if( head + diag >= M)diag = M - head - 1;sum = vert + level + diag + 1;if( sum > 1){elements[head].back = p1 = ( int *) malloc( sum * sizeof( int)); elements[rear].go = p2 = ( int *) malloc( sum * sizeof( int));if( p1 == NULL || p2 == NULL){fprintf( stderr, " 动态分配内存失败!\n\n");delete_link();exit( EXIT_FAILURE);}//iffor( i = 1; i <=vert; i++){*p1++ = head + i;*p2++ = rear - i;}if( level == 1){*p1++ = head + M;*p2++ = rear - M;}else if( level > 1){*p1++ = head + M;*p2++ = rear - M;vert = (M << 1) - 1; /* 临时挪用存储数值*/for( i = 1; i < level; i++){*p1++ = head + vert + i;*p2++ = rear - vert - i ;}}for( i = 1; i <= diag; i++){*p1++ = head + M + i;*p2++ = rear - M - i;}*p1 = *p2 = -1;}//if}//for(head)/* 单独计算 head = M 的情况*//* 返回时，head = M 的点只能返回出发点(且只可能从出发点过河到此点)。