int top; void main() { int knapproblem( int, int, int[]); int weight[NUMBER]; /*存放物品质量的数组*/ int n, i; int maxweight; /*包所能承受的最大重量*/ printf(\ scanf(\ printf(\ scanf(\ printf( \ Please input every object's weight :\\n\ for (i=1; i<=n; i++ ) scanf(\if (knapproblem(n, maxweight, weight ) == TRUE ) /*调用背包处理函数*/ { printf(\ printf(\ for ( ;top>0;top-- ) printf(\stack[top],weight[stack[top]]); /*pop stack and print every weight*/ printf(\ } else printf(\} /*main*/
int knapproblem( int n, int maxweight, int weight[] ) /*背包问题处理函数*/ { /*func kanpstack*/ int i=1; top=0; while ((maxweight>0)&&(i<=n)) { if ((maxweight-weight[i]==0) || ((maxweight-weight[i] >0 )&& (i /*Push No.i stack*/ stack[ ++top ]=i; maxweight = maxweight-weight[i]; } if ( maxweight==0) /*能够装入包中*/ { return( TRUE ); } else if (( i==n )&& (top>0)) /*继续试探*/ { i=stack[top]; top=top-1; maxweight = maxweight+weight[i]; } i++; } /*while*/ return( FALSE ); } /*knapproblem*/ 7．划分子集问题的求解。划分子集问题的实际例子很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。 #include \ #define MAX 10 /*元素数目*/ int r[MAX][MAX]; /*存放关系矩阵*/ int n; int result[MAX]; /*存放分组结果*/ void main() { void division( int [MAX][MAX] ); /*声明划分子集函数*/ int i, j; printf(\ scanf(\ printf(\matrix,1 rash, 0 no rash:\\n\/*输入冲突矩阵,1冲突,0不冲突*/ for ( i=1; i<=n; i++ ) for( j=1; j<=n; j++ ) scanf(\ division(r); /*调用子集划分函数*/ for( i=1; i<=n; i++ ) /*输出分组结果*/ printf(\i, result[i]); } void division ( int r[MAX][MAX]) { /*子集划分函数*/ int newr[MAX]; /*记录所有以入组的元素发生冲突的元素信息*/ int cq[MAX]; /*循环队列*/ int i, k; int front, rear; /*循环队列头尾指针*/ int group, pre; for (k=0; k<=n-1; k++ ) /*n个元素依此入队列*/ cq[k]=k+1; for ( k=0; k<=n; k++)/*初始状态,均不冲突*/ newr[k]=0; group=1; pre=0; while (( rear != front ) || (rear != 0 )) { front=(front+1)%n; i=cq[front]; if (i else /*可以分在当前组*/ { result[i]=group; for (k=1; k<=n; k++ ) newr[k]=newr[k]+r[i][k]; /*补充产生冲突的元素*/ } pre=i; } } /*division*/ 8．写出汉诺塔问题的递归和非递归算法。 汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、?、n），这n个圆盘已经按照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘按照如下规则由X柱子移动到Z柱子： (1) 每次只能移动柱子最上面的一个圆盘。 (2) 任何圆盘都不能放在比它小的圆盘之上。 (3) 圆盘只能在X、Y和Z三根柱子之上放置。 /*汉诺塔问题的递归算法*/ void move( from, to ) char from, to; { /*汉诺塔移动过程*/ printf(\输出移动过程*/ }/*move*/ void hanoi( n,x,y,z ) /*递归执行过程*/ char x,y,z; int n; { if ( n==1 ) move( x,z ); else { hanoi( n-1,x,z,y ); move( x,z ); hanoi( n-1,y,x,z ); } }/*hanoi*/ main() { int n; printf(\input the nmmber of diskes:\\n\ scanf(\ printf(\ hanoi( n,'A','B','C' ); } /*汉诺塔问题的非递归算法*/ #include \struct node { char x; char y; char z; int id; }stack[30]; main() { int i=1; int n; char s; printf(\ scanf(\ printf(\ if( n==1 ) printf(\ else { stack[1].id=n; stack[1].x='A'; stack[1].y='B'; stack[1].z='C'; do { while( n>1 ) { n--;