院 系：计 算 机 学 院
实验课程：算法分析与设计实验
实验项目：实验二
（应用已经学习的算法技术或者分析算法性能）
指导老师： 曹霑懋
开课时间：2010 ～ 20##年度第 2学期
专 业：计算机科学与技术 师范类
班 级：09级 2 班
学 生： 程毅
学 号： 20092101056
华南师范大学教务处
实验名称：A.编程实现八皇后问题（验证性实验）
实验目标：使用深度优先搜索算法以及回溯法的思想进行暴力解题
实验任务：用8*8的二维数组去模拟皇后所在的棋盘，然后用1标记该位置可以放皇后，用0来标记该位置不可以放皇后。然后每次有一个合理的八皇后方案，就会counter++，记录摆放的方法，并且输出皇后摆放的坐标。
实验步骤：1.明确实验目标和实验任务
2.理解实验所涉及到深度优先搜索的算法以及回溯法的思想
3.编写程序实现求解八皇后问题。
4.设计实验数据数据并运行程序，记录运行的结果
程序代码:
/***********************************************************************
这个题目我默认第一个皇后放第一行，第二个皇后放第二行，如此类推。
***********************************************************************/
#include<iostream>
using namespace std;
struct chessboard
{
int b[8][8]; //对棋盘的模拟
};
struct location
{
int x,y; //记录皇后放的坐标
};
chessboard visited[9];
location loc[8];
int num; //记录有多少种方法
void print() //输出皇后的方法以及种数
{
int i;
cout<<++num<<ends;
for(i=0;i<=7;i++)
{
cout<<loc[i].x<<ends<<loc[i].y<<ends;
}
cout<<endl;
}
int x1,y1,x2,y2; //用于标记坐标
void visit(int x,int y,int step)
{
int i;
x1=x;
y1=y;
x2=x;
y2=y;
visited[step]=visited[step-1]; //把上一次标记过不能走的坐标传到下一次
for(i=0;i<8;i++)
{
visited[step].b[x][i]=0; //与皇后同行的都标为不能放
visited[step].b[i][y]=0; //与皇后同列的都标为不能放
}
while(x1<8 && y1<8)
{
visited[step].b[x1][y1]=0; //与皇后对角线的标记为不能放
x1++;
y1++;
}
while(x2<8 && y2>=0)
{
visited[step].b[x2][y2]=0; //与皇后对角线的标记为不能放
x2++;
y2--;
}
}
void dfs(int step)
{
int j;
if(step==9)
{
print();
}
else
{
for(j=0;j<8;j++)
{
if(visited[step-1].b[step-1][j])
{
loc[step-1].x=step-1; //放置皇后的位置
loc[step-1].y=j;
visit(step-1,j,step); //进行标记
dfs(step+1); //递归进行下一个
}
}
}
}
int main()
{
num=0; //初始化计数变量num
memset(visited,1,sizeof(visited)); //初始化visited标记数组
dfs(1); //从1开始，1作为步骤参数
return 0;
}
数据测试：
实验名称：B.矩阵链乘问题（验证性实验）
实验目标：用动态规划法去解决矩阵链乘，求链乘的最优解。
实验任务： 用6*6的二位数组去模拟需要填写的二维表，然后按照算法的顺序，按对角线的顺序去填写每一个格子的内容。
实验步骤：1.明确实验目标和实验任务
2.理解实验所涉及到动态规划法的思想
3.编写程序实现求矩阵链乘法的最优解。
4.设计实验数据数据并运行程序，记录运行的结果
程序代码:
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
int td,n=6,d,i,j,k,temp;
int f[6][6];
int a[7]={2,3,5,3,4,10,3};
memset(f,0x7f,sizeof(f));
for(i=0;i<n;i++)
{
f[i][i]=0; //给对角填上0
}
for(d=1;d<6;d++)
{
for(i=0;i+d<6;i++)
{
j=i+d; //对角线上i，j关系
for(k=i+1;k<=j;k++)
{
temp=f[i][k-1]+f[k][j]+a[i]*a[k]*a[j+1];
if(f[i][j]>temp)
{
f[i][j]=temp;
}
}
}
}
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
if(i<=j) cout<<setw(6)<<f[i][j]<<ends;
else cout<<" ";
}
cout<<endl;
}
return 0;
}
数据测试：
实验名称：C.归并排序与快速排序平均时间比较（验证性实验）
实验目标： 1.比较两种算法在平均情况下哪一个更快
2.加深对时间复杂度概念的理解
实验任务： 1. 用C/C++语言编程实现归并排序算法6.3 和快速排序 算法6.6。对于快速排序，SPLIT中的划分元素采用三者A(low)， A(high)，A((low+high)/2)中其值居中者。
2. 随机产生20组数据（比如n=5000i，1≤i≤ 20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行快速排序和归并排序算法，并计录各自的运行时间（以毫秒为单位）。
实验步骤：1.明确实验目标和实验任务
2.理解实验所涉及到动态规划法的思想
3.编写程序实现求矩阵链乘法的最优解。
4.设计实验数据数据并运行程序，记录运行的结果
程序代码:
合并排序：
#include<iostream>
#include<ctime>
using namespace std;
//copy函数将b[0]至[high-low+1]拷贝到a[low]至a[high]
//数组b只是一个辅助数组
template <class T>
void copy(T a[],T b[],int low,int high)
{
int i,size;
size=high-low+1;
for(i=0;i<size;i++)
{
a[low]=b[i];
low++;
}
}
template <class T>
void merge(T a[],T b[],int low,int mid,int high)
{
int a1h=low, //指向第一个数组的开头
a1t=mid, //只想第一个数组的结尾
a2h=mid+1, //指向第二个数组的开头
a2t=high, //指向第二个数组的结尾
b1=0, //指向数组b的元素
j;
for(j=0;j<high-low+1;j++)
{
if(a1h>a1t) //如果第一个数组拷贝完地话，就去拷贝第二个数组
{
b[b1]=a[a2h];
b1++;
a2h++;
continue;
}
if(a2h>a2t) //如果第二个数组拷贝完的话，就去拷贝第一个数组
{
b[b1]=a[a1h];
b1++;
a1h++;
continue;
}
if(a[a1h]<a[a2h]) //如果两个数组都没有拷贝完，那么就比较两个组之间的元素
{ //把小的拷贝进b
b[b1]=a[a1h];
b1++;
a1h++;
continue;
}
else
{ //同上
b[b1]=a[a2h];
b1++;
a2h++;
continue;
}
}
}
//对数组a进行合并排序，拆分
template <class T>
void mergesort(T a[],int low,int high)
{
int mid;
T *b=new int [high-low+1];
if(low<high)
{
mid=(low+high)/2; //取中点
mergesort(a,low,mid); //让左半边进行合并排序
mergesort(a,mid+1,high); //让右半边进行合并排序
merge(a,b,low,mid,high); //左右合并到辅助数组b中
copy(a,b,low,high); //把b拷回到a
}
}
int main()
{
int a[20],i,j;
srand((unsigned)time(NULL));
for(i=0;i<20;i++)
{
a[i]=rand()%105+1;
}
cout<<"排序之前"<<endl;
for(i=0;i<20;i++)
{
cout<<a[i]<<ends;
}
cout<<endl;
mergesort(a,0,19);
cout<<"排序之后"<<endl;
for(j=0;j<20;j++)
{
cout<<a[j]<<ends;
}
cout<<endl;
return 0;
}
数据测试：
快速排序
#include<iostream>
#include<ctime>
using namespace std;
template <class T>
int quickpass(T a[],int low,int high)
{
int down,up;
down=low; //指向数组的头部
up=high; //指向数组的尾部+
a[0]=a[low]; //把数组的第一个数作为参考值
while(down<up)
{
while((down<up) && (a[up]>=a[0])) //从数组尾部向头部扫描，寻找比参考值小的数
{
up--; //指针向头部移动
}
if(down<up)
{
a[down]=a[up]; //找到了，且指针没有重合，就把扫描到的值填入到空出来的地方
down++;
}
while((down<up) && a[down]<=a[0]) //从数组头部向尾部扫描，寻找比参考值打得数
{
down++; //指针向尾部移动
}
if(down<up)
{
a[up]=a[down]; //找到了，且指针没有重合，就把扫描到得值填入空出来的地方
up--;
}
}
a[down]=a[0]; //最后把参考值填入到空出来的地方
return down; //返回参考值当前位置
}
template <class T>
void quicksort(T a[],int low,int high)
{
int mid;
if(low<high)
{
mid=quickpass(a,low,high); //对数组进行一趟处理
quicksort(a,low,mid-1); //递归处理左半部分
quicksort(a,mid+1,high); //递归处理右半部分
}
}
int main()
{
int a[21],i;
srand((unsigned)time(NULL));
cout<<"排序之前"<<endl;
for(i=1;i<21;i++)
{
a[i]=rand()%105+1;
cout<<a[i]<<ends;
}
cout<<endl;
quicksort(a,1,21);
cout<<"排序之后"<<endl;
for(i=1;i<21;i++)
{
cout<<a[i]<<ends;
}
cout<<endl;
return 0;
}
数据测试：
实验小结：
首先是八皇后问题。关于八皇后问题，主要是先对回溯法进行理解。毕竟理解不了回溯法，就无法写递归程序。在做的时候简化了一下过程。把第一个皇后就放第一排，第二个皇后放第二排，而不是随机放的，降低了代码难度和复杂度。另外在回溯的时候，要做好标记，包括放下皇后的时候也要做好标记，标记好不能放的地方。
接下来是两个排序的问题。关于排序，其实很简单，就是按照书上的伪代码翻译成C++代码就可以了，加上一个产生随机数的头文件以及函数，基本上就可以交工了，代码完成毫无压力。
矩阵链乘法也挺简单的，由于有了最长公共子序列的一些经验，所以做起来也很方便。问题就是，输出矩阵的时候，一开始老是对不齐。后来突然发现自己可以用setw来控制格式，真是脑残。矩阵链乘法其实也挺简单的。