数据结构上机实验（五）递归
班级：学号：姓名：
上机时间：地点：
一、实验目的
1.理解递归的定义和递归模型。
2.掌握递归设计的一般方法，能用递归算法解决一些较复杂应用问题。
二、实验内容
1．编写程序求解皇后问题
要求：（1）皇后的个数n由用户输入，其值不能超过20；
（2）采用递归方法求解。
2．编写一个程序求解背包问题
三、实验过程
1．了解常用函数所在的头文件
stdlib.h
stdlib 头文件里包含了C语言的一些函数
该文件包含了的C语言标准库函数的定义
stdlib.h里面定义了五种类型、一些宏和通用工具函数。
类型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX 和MB_CUR_MAX等等；常用的函数如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、srand()、exit()等等。
具体的内容你自己可以打开编译器的include目录里面的stdlib.h头文件看看。
conio.h
conio.h不是C标准库中的头文件。
conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，主要是一些用户通过按键盘产生的对应操作，比如getch()函数等等。
&表示引用传递。
在函数参数表中，出现带&这个的形参，表示引用传递。
2．程序实现（以下代码仅起参考作用）
（1）求解皇后问题
#include <stdio.h>
#include <stdlib.h>
const int N=20; //最多皇后个数
int q[N]; //存放各皇后所在的行号
int cont=0; //存放解个数
void print(int n) //输出一个解
{
cont++;
int i;
printf(" 第%d个解：",cont);
for (i=1;i<=n;i++)
printf("%d ",q[i]);
printf("\n");
}
int find(int i,int k) //测试第k列的i行上能否摆放皇后
{
int j;
j=1;
while (j<k) //j=1～k-1是已放置了皇后的列
{
if ((q[j]==i) || (abs(q[j]-i)==abs(j-k)))
//第j列皇后是否在i行或(q[j],j)与(i,k)是否同对角线
return 0;
j++;
}
return 1;
}
void place(int k,int n) //第k个皇后放到第k列上
{
if (k>n)
print(n); //所有皇后放置结束
else
for (int i=1;i<=n;i++) //在第k列上穷举每一个位置
if (find(i,k))
{
q[k]=i;place(k+1,n);
}
}
void main()
{
int n; //n存放实际皇后个数
printf(" 皇后问题(n<20) n=");
scanf("%d",&n);
if (n>20)
printf("n值太大,不能求解\n");
else
{
printf(" %d皇后问题求解如下：\n",n);
place(1,n);
printf("\n");
}
}
（2）求解背包问题
#include <stdio.h>
#define N 100
int limitw; //限制的总重量
int totv; //全部物品的总价int maxv;
int option[N],cop[N];
struct
{
int weight;
int value;
} a[N];
int n; //物品种数次void find(int i,int tw,int tv)
{
int k;
if (tw+a[i].weight<=limitw)
{
cop[i]=1;
if (i<n-1)
find(i+1,tw+a[i].weight,tv);
else
{
for (k=0;k<n;k++)
option[k]=cop[k];
maxv=tv;
}
cop[i]=0;
}
if (tv-a[i].value>maxv)
if (i<n-1)
find(i+1,tw,tv-a[i].value);
else
{
for (k=0;k<n;k++)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}
void main()
{
int k,w,v;
printf("物品种数:");
scanf("%d",&n);
for (totv=0,k=0;k<n;k++)
{
printf(" 第%d种物品(重量,价值):",k+1);
scanf("%d,%d",&w,&v);
a[k].weight=w;
a[k].value=v;
totv+=v;
}
printf("背包所能承受的总重量:");
scanf("%d",&limitw);
maxv=0;
for (k=0;k<n;k++)
cop[k]=0;
find(0,0,totv);
printf("最佳装填方案是:\n");
for (k=0;k<n;k++)
if (option[k])
printf(" 第%d种物品\n",k+1);
printf("总价值=%d\n",maxv);
}
3．运行结果（包括程序如何使用，输入数据和输出结果）及分析四、实验体会。