<<算法设计与分析>>实验指导书实验一、回溯法一、实验目的掌握回溯法求解问题的思想，学会利用其原理求解相关问题。
二、实验内容及要求1、八皇后问题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。
该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
高斯认为有76种方案。
1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
要求对用C实现的回溯法进行验证，并使其能扩展到任意的皇后数的情况，同时对源程序给出详细的注释。
三、实验步骤1. 理解算法思想和问题要求；2. 编程实现题目要求；3. 上机输入和调试自己所编的程序；4. 验证分析实验结果；5. 整理出实验报告。
四、实验源代码1、八皇后问题（回溯法实现）#define QUEENNO 8#define MAXNO 32#include <stdio.h>#include <stdlib.h>int X[MAXNO];char D[MAXNO][MAXNO];int count=0;void initiate(int n);void nqueen(int n);void display(int n);main(){int queenno=QUEENNO;initiate(queenno);nqueen(queenno);printf("共有%d个解,解已经保存在D盘文件result.txt中\n",count); }void initiate(int n){int i;for(i=0;i<n;i++)X[i]=-1;return;}void nqueen(int n){ int k;X[0]=0;k=0;while(k>=0){X[k]++;while(X[k]<=n&&!place(k)){X[k]++;}if(X[k]<=n){ if(k==n-1) display(n);else {k++;X[k]=0;}}else{ k--;}}}int place(int k){int i;i=0;while(i<k){if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))return 0;i++;}return 1;}void display(int n){FILE *fw;int i,j;count++;fw=fopen("D:\\result.txt","a");for(i=0;i<n;i++)for(j=0;j<n;j++)D[i][j]='o';for(i=0;i<n;i++)D[i][X[i]-1]='*';fprintf(fw,"%d\n",count);fprintf(fw,"-------------------------\n");for(i=0;i<n;i++)for(j=0;j<n;j++){if(j==n-1)fprintf(fw,"%c \n",D[i][j]);else fprintf(fw,"%c ",D[i][j]); }fprintf(fw,"-------------------------\n");fclose(fw);return;}实验二：分治法（2学时）问题陈述:对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法.解题思路:将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序.程序代码:#include <iostream.h>const int N=100;void ScanTarget(int target[], int n, int head[], int tail[]);int CountHead(int head[]);void MergeSort(int a[], int head[], int tail[], int m);void MergePass(int x[], int y[], int s, int a[], int b[], int m);void Merge(int c[], int d[], int l, int m, int r);void main(){char a;do{int target[N],head[N],tail[N];int i=0,n,m;for(; i<N; i++){head[i]=-1;tail[i]=-1;}cout<<"请输入要排序的总数:"<<endl;cin>>n;cout<<"请输入要排序的数列:" <<endl;for(i=0; i<n; i++)cin>>target[i];ScanTarget(target,n,head,tail);m=CountHead(head);MergeSort(target,head,tail,m);cout<<"排序后:"<<endl;for(i=0; i<n; i++)cout<<target[i]<<" ";cout<<endl;cout<<"是否继续(y/n):"<<endl;cin>>a;}while(a!='n' && a!='N');}void ScanTarget(int target[], int n, int head[], int tail[])//扫描待排数组；{int i,j=0,k=0;head[k]=0;k++;for(i=1;i<n;i++){if(target[i-1]>target[i]){tail[j++]=i-1;head[k++]=i;}}tail[j]=n-1;}int CountHead(int head[])//求长度；{int i(0);while(head[i]!=-1){i++;}return i;}void MergeSort(int a[], int head[], int tail[], int m){int b[N];int s=1;while(s<m){MergePass(a,b,s,head,tail,m);s+=s;MergePass(b,a,s,head,tail,m);s+=s;}}void MergePass(int x[], int y[], int s, int a[], int b[], int m){int i=0;while(i <= m-2*s){Merge(x,y,a[i],b[i+s-1],b[i+2*s-1]);i=i+2*s;}if(i+s < m){Merge(x,y,a[i],b[i+s-1],b[m-1]);}else{for(int j=i; j<m; j++)for(int k=a[j]; k<=b[j]; k++)y[k]=x[k];}}void Merge(int c[], int d[], int l, int m, int r){int i,j,k;i=l;j=m+1;k=l;while((i<=m) && (j<=r)){if( c[i] <= c[j] )d[k++]=c[i++];else d[k++]=c[j++];}if( i>m ){for(int q=j; q<=r; q++)d[k++]=c[q];}else{for(int q=i; q<=m; q++)d[k++]=c[q];}}时间复杂度:通常情况下用自然合并排序所需要的合并次数较少。
