中南大学
算法分析与设计实验报告
班级:物联网****班
学号: ******
姓名: ***
指导老师:沙莎
20##年12月28日
目 录
分治法实验
1.快速排序 ……………………………………………………2
2.归并排序………………………………………………………4
3.最大最小值……………………………………………………7
动态规划实验
多段图……………………………………………………………10
回溯法实验
N皇后……………………………………………………………15
分治法实验
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地求解这些子问题,然后将各子问题的解合并得到原问题的解。
1.快速排序
快速排序是基于分治策略的一个排序算法实现快速排序的分治过程如下:
分解:数组A[p..r]被划分为两个(可能空)子数组A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每个元素都小于等于A(q),而且,小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行计算。
解决:通过递归调用快速排序,对子数组A[p..q-1]和A[q+1..r]排序
合并:因为两个子数组是就地排序的,将它们的合并不需要操作,整个数组
A[p..r]已排序。
实验代码如下:
#include <iostream>
using namespace std;
int num;
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}//交换元素位置
void PrintArray(int *arr)
{
for(int i=1; i<=num; ++i)
cout << arr[i] << " ";
cout << endl;
}
int Partition1(int *arr, int p, int r)
{
int x=arr[r];
int i=p-1;
int j;
for(j=p;j<=r-1;j++)
{
if(arr[j]<=x)
{i=i+1;
swap(arr[i],arr[j]);
}
}
swap(arr[i+1],arr[r]);
return i+1;
}//对子数组A[p..r]进行就地重排
void QuickSort(int *arr, int p, int r)
{
if(p < r)
{
int q = Partition1(arr, p, r);
QuickSort(arr, p, q-1);
QuickSort(arr, q+1, r);
}
}//该过程实现快速排序
int main()
{
int arr[100];
cout << "请输入元素个数:\n";
cin >> num;
cout << "请输入元素大小:\n";
for(int i=1; i<=num; ++i)
cin >> arr[i];
QuickSort(arr, 1, num);
cout << "最后结果:";
PrintArray(arr);
return 0;
}
运行结果如下图所示:
实验收获与体会:
通过证明可以得到该算法在最坏情况下的时间复杂性为T(n)=O(n^2),平均情况下的时间复杂性是O(nlogn),通过该实验对分治法基本思想有了了解。
2.归并排序:
基本操作如下:
分解:将n个元素分成各含n/2个元素的子序列
解决:用合并排序法对两个子序列递归地排序
合并:合并两个已排好序的子序列得到排序结果
在对子序列排序时,其长度为1时递归结束。单个元素被视为是已排好序的。
实验代码如下:
#include<iostream.h>
#include<string.h>
template<class T>
void Merge(T c[],T d[],int l,int m,int r)
{//把c[l:m]和c[m:r]归并到d[l: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];
}
template<class T>
void MergePass(T x[],T y[],int s,int n){
//归并大小为s的相邻的段
int i=0;
while(i<=n-2*s){
//归并两个大小为s的相邻段
Merge(x,y,i,i+s-1,n-1);
i=i+2*s;
}
//剩下不足两个元素
if(i+s<n)Merge(x,y,i,i+s-1,n-1);
else for(int j=i;j<=n-1;j++)
//把最后一段复制到y
y[j]=x[j];
}
template<class T>
void MergeSort(T a[],int n)
{T* b=new T[n];
int s=1;
while(s<n){
MergePass(a,b,s,n);
s+=s;
MergePass(b,a,s,n);
s+=s;
}
}
int main()
{
int n,i,j=0;
double *Input;
cout<<"请输入您要排序的元素个数"<<endl;
cin>>n;
Input=new double[100000];//定义排序数组
cout<<"请输入您要排序的元素:"<<endl;
for(i=0;i<n;i++)
cin>>*(Input+i);
MergeSort(Input,n);//调用排序函数
cout<<"排序后的数组元素为:"<<endl;
for(i=0;i<n;i++)
{
cout<<Input[i]<<" ";
j++;
if(j%10==0)
cout<<endl;
}
delete []Input;//释放内存;
}
运行结果如下图所示:
实验收获与体会:
通过归并排序的实验对分治法在排序中的应用有了更深刻的了解,与快速排序对比,归并排序相对较“稳定”些。
3.最大最小值问题:
每次将问题分成大致相等的两部分,分别在这两部分中找出最大值与最小值,再将这两个子问题的解组合成原问题的解,就可得到该问题的分治算法。
算法描述:
procedure MAXMIN(i, j, fmax, fmin)
global n,A[1:n]
case
{ i=j: fmax←fmin←A[i] /*只有一个元素*/
i=j-1:if A[i] <A[j] then /*两个元素*/
fmax←A[j ] ;fmin←A[i]
else fmax←A[i] ;fmin←A[j]
else:mid← (i+j )/2 /*分成两部分*/
MAXMIN(i,mid,max1,min1)
MAXMIN(mid+1,j,max2,min2)
fmax←max(max1,max2)
fmin←min(min1,min2)
}
如果MAX1和MIN1是I1中的最大和最小元素,MAX2和 MIN2是I2中的最大和最小元素, MAX1和MAX2中的大者就是I中的最大元素MAX, MIN1和MIN2中的小者是I中的最小元素MIN。如果I只包含一个元素,则不需要作任何分割直接就可得到其解。
实验代码如下:
#include "stdio.h"
#define N 100
void maxmin2(int A[],int i,int j,int *max,int *min)
{
int mid,max1,max2,min1,min2;
if (j==i)
{ *max= *min=A[i]=A[j];
return;
}
if(j-1==i)
{
if(A[i]>A[j])
{
*max=A[i];
*min=A[j];
}
else
{
*max=A[j];
*min=A[i];
}
return;
}
mid=(i+j)/2;
maxmin2( A, mid+1, j,&max2,&min2);
maxmin2( A, i,mid,&max1,&min1);
if(max1>max2)
*max=max1;
else
*max=max2;
if(min1>min2)
*min=min2;
else
*min=min1;
}
main()
{
int i,n;
int A[N];
int max,min;
printf("请输入要比较的数据的个数:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入第%d个数",i+1);
scanf("%d",&A[i]);
}
maxmin2(A,0,n-1,&max,&min);
printf("最大值为:%d 最小值为:%d",max,min);
}
运行结果如下图所示:
实验收获与体会:
通过该实验对分治法掌握的更加透彻,明白了分治法发挥的作用。
动态规划实验
对于一个多阶段过程问题,是否可以分段实现最优决策,信赖于该问题是否有最优子结构性质,能否采用动态规划的方法,还要看该问题的子问题是否具有重叠性质。
最优子结构性质:原问题的最优解包含了其子问题的最优解
子问题的重叠性质:每次产生的子问题并不总是新问题,有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素
动态规划一般方法
1.找出最优解的性质,并刻画其结构特征
2.递归地定义最优值(写出动态规划方程)
3.以自底向上的方式计算出最优值
多段图
多段图算法:
Procedure FGRAPH(E,k,n,P)
//输入是按段的顺序给结点编号的,有n个结点的k段图。E是边集,c(i,j)是边<i,j>的成本。P(1:k)是最小成本路径。//
real COST(n),integer(n-1),P(k),r,j,k,n
COST(n)<-0
for j<-n-1 to 1 by -1 do //计算COST(j)//
设r是一个这样的结点,(j,r)E且使c(j,r)+COST(r)取最小值
COST(j)<- c(j,r)+COST(r);D(j)<-r;Repeat //向前对j-1进行决策//
P(1)<-1; P(k)<-n;
for j<-2 to k-1 do // 找路径上的第j个节点//
P(j)<-D(P(j-1));repeat;
end FGRAPH
实验代码如下:
#include <iostream>
using namespace std;
#define MAX 100
#define n 12 //图的总顶点数
#define k 5 //图的段数
int c[n][n];
void init(int cost[]) //初始化图
{
int i,j;
for(i=0;i<13;i++)
{
for(j=0;j<13;j++)
{
c[i][j]=MAX;//初始化每条边长度为MAX
}
}
c[1][2]=9; c[1][3]=7; c[1][4]=3; c[1][5]=2; c[2][6]=4; c[2][7]=2; c[2][8]=1;
c[3][6]=2; c[3][7]=7; c[4][8]=11; c[5][7]=11; c[5][8]=8; c[6][9]=6; c[6][10]=5;
c[7][9]=4; c[7][10]=3; c[8][10]=5; c[8][11]=6; c[9][12]=4; c[10][12]=2;c[11][12]=5;
//给每条边赋值
}
void front(int cost[],int path[],int d[]) //向前递推算法求多段图的最短路径
{
int r,j,temp,min;
for(j=0;j<=n;j++)
cost[j]=0;
for(j=n-1;j>=1;j--)
{
temp=0;
min=c[j][temp]+cost[temp]; //初始化当前路径长度的最小值
for(r=0;r<=n;r++)
{
if(c[j][r]!=MAX)
{
if((c[j][r]+cost[r])<min)//找到最小的r,使 c[j][r]+cost[r]取最小值
{
min=c[j][r]+cost[r];
temp=r;
}
}
}
cost[j]=c[j][temp]+cost[temp];
d[j]=temp;
}//向前对j-1进行决策
path[1]=1;//第一段所取节点
path[k]=n;//最后一段所取节点
for(j=2;j<k;j++)
path[j]=d[path[j-1]];//找到路径上第j个节点
}
void back(int bcost[],int path1[],int d[]) // 使用向后递推算法求多段图的最短路径
{
int r,j,temp,min;
for(j=0;j<=n;j++)
bcost[j]=0;
for(j=2;j<=n;j++)
{
temp=12;
min=c[temp][j]+bcost[temp]; //初始化当前路径长度最小值
for(r=0;r<=n;r++)
{
if(c[r][j]!=MAX)
{
if((c[r][j]+bcost[r])<min) //找到最小的r使c[r][j]+bcost[r]最小
{
min=c[r][j]+bcost[r];
temp=r;
}
}
}
bcost[j]=c[temp][j]+bcost[temp];
d[j]=temp;
}
path1[1]=1;
path1[k]=n;
for(int i=4;i>=2;i--)
{
path1[i]=d[path1[i+1]];
}//找出各段的节点
}
int main()
{
int cur=-1;
int j;
int cost[13],d[12],bcost[13];
int path[k];
int path1[k];
cout<<"\t\t\t\t多段图问题"<<endl;
cout<<"\n\n";
init(cost);
front(cost,path,d);
cout<<"向前递推算法求得的最短路径:\n\n";
for(int i=1;i<=5;i++)
{
if(i==5)
cout<<path[i]<<"";
else
cout<<path[i]<<"->";
}
cout<<"\n";
cout<<endl<<"最短路径:"<<cost[1]<<endl;
cout<<"\n";
cout<<"向后递推算法求得的最短路径:\n\n";
back(bcost,path1,d);
for(j=1;j<=5;j++)
{
if(j==5)
cout<<path[j]<<"";
else
cout<<path1[j]<<"->";
}
cout<<"\n";
cout<<endl<<"最短路径:"<<bcost[12]<<endl;
cout<<"\n";
}
运行结果如下图所示:
实验收获与体会:
通过多段图实验对动态规划的思想有了更深理解,动态规划与分治法类似,基本思想也是将待求解问题分成若干个子问题,但是分解得到的子问题往往不是互相独立的。
回溯法实验
回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。
算法搜索至解空间树的任意一点时,先判断该结点是否满足约束。如果不满足,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。
N皇后:
基本思想:
(1)针对所给问题,定义问题的解空间,使N个皇后不在同行同列,对角线上;
(2)确定易于搜索的解空间结构;
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
实验代码如下:
#include<iostream.h>
#include "math.h"
class QUEEN
{
public:
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n,*x;
long sum;
};
int nQueen(int n)
{
QUEEN x;
x.n=n;
x.sum=0;
int *p=new int [n+1];
for(int i=0;i<=n;i++)
p[i]=0;
x.x=p;
x.Backtrack(1);
delete[]p;
return x.sum;
}
bool QUEEN::Place(int k)
{
for(int j=1;j<k;j++)
if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))
return false;
return true;
}
void QUEEN::Backtrack(int t)
{
if(t>n){sum++;
cout << "n皇后问题的第"<<sum<<"个"<<"可行解的坐标为:"<<endl;
for(t=1;t<=n;t++)
cout <<"( "<<t<<","<<x[t]<<")"<<endl;
cout << "********"<<endl;}
else
for(int i=1;i<=n;i++)
{
x[t]=i;
if(Place(t))
Backtrack(t+1);//递归求解
}
}
int main()
{ int n;
cout <<"***************N 皇后问题*************** "<<endl;
cout << endl;
cout <<"请输入皇后的个数 n: "<<endl;
cin>>n;
cout<<nQueen( n)<<endl;
cout <<"***************N 皇后问题结束*************"<<endl;
}
运行结果如下图所示:
实验收获与体会:
通过该实验对回溯法的思想有了较深的了解,通过亲手实践,加深了记忆与理解,该实验的算法也可以用在类似有关回溯法问题上。
中南大学
实验报告
姓名: 学号: 成绩: 指导教师:
订装实验报告系姓名预定时间实验名称11典型环节的时域响应专业学号实验时间班授课老师实验台号彭涛订装2订装3订装4订装5订装6订装7…
中南大学数据库原理实验报告学生姓名学号专业班级指导教师盛津芳学院信息科学与工程学院完成时间20xx年1月实验一实验二一实验目的12…
中南大学数字信号处理实验报告学生姓名学号指导教师学院专业班级完成时间2目录实验一实验二常见离散时间信号的产生和频谱分析3实验结果与…
机械振动基实验报告机械0814中南大学1机械振动实验报告姓名学号0806081529成绩指导教师隆志力23机械振动实验报告姓名周菁…
机械振动实验报告姓名学号成绩指导教师12机械振动实验报告姓名学号成绩指导教师345机械振动实验报告姓名学号成绩指导教师68
机械振动基实验报告姓名班级学院机电工程学院学号1机械振动实验报告姓名学号成绩指导教师易老师23机械振动实验报告姓名学号成绩指导教师…
GIS课程设计实验报告小组组员钟蕾邢磊张成乃古色拉司宝元班级测绘试验班1101指导老师李光强赵玲1一课程设计数据中南大学校本部CA…
郑州航空工业管理学院计算机科学与应用系课程设计报告操作系统原理操作系统课程设计目录1题目简述22需求分析221设计思想222要求3…