实验4 回溯法上机
[实验目的]
;
;
。
[实验要求]
按以下实验内容完成题目,并把编译、运行过程中出现的问题以及解决方法填入实验报告中,按时上交。
[实验学时] 2学时。
[实验内容]
一、实验内容
利用回溯法编程求解6-皇后问题,或者子集和问题,并请对自己的程序进行复杂性分析。
二、算法描述
穷举法加上回溯法列举出所有6皇后的解法以及各方案具体内容
三、源程序
#include<>
#define N 15
int place(int k);
int queen(int t);
int n;
int sum=0;
int x[N];
void main()
{
int t;
n=6;
t = queen(1);
printf("6皇后问题一共有%d种解法\n",t);
}
int place(int k)
{
int i;
for(i=1;i<k;i++)
if((k-i)*(k-i)==(x[k]-x[i])*(x[k]-x[i])||x[k]==x[i])
return 0;
return 1;
}
int queen(int t)
{
if(t>n && n>0)
sum++;
else
for(int i=1;i<=n;i++)
{
x[t] = i;
if(place(t))
queen(t+1);
}
return sum;
}
四、程序的复杂度分析
O(n)=t*n
五、程序运行结果及截图
算法实验回溯法上机 来自淘豆网m.daumloan.com转载请标明出处.
