算法设计与分析实验分析报告

算法设计与分析实验报告

————————————————————————————————作者：————————————————————————————————日期：

2

《算法设计与分析》实验报告实验一递归与分治策略应用基础

学号：**************

姓名：*************

班级：*************

日期：2014-2015学年第1学期

第九周

一、实验目的

1、理解递归的概念和分治法的基本思想

2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法

3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。（30分）

2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。（30分）

3、设有n=2k个运动员要进行网球循环赛。设计一个满足要求的比赛日程表。（40分）

提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include "iostream"

using namespace std;

#define N 100

void Perm(int* list, int k, int m)

{

if (k == m)

{

for (int i=0; i

cout << list[i] << " ";

cout << endl;

return;

}

else

{

for (int i=m; i

{

swap(list[m], list[i]);

Perm(list, k, m+1);

swap(list[m], list[i]);

}

}

}

void swap(int a,int b)

{

int temp;

temp=a;

a=b;

b=temp;

}

int main()

{

int i,n;

int a[N];

cout<<"请输入排列数据总个数：";

cin>>n;

cout<<"请输入数据：";

for(i=0;i

{

cin>>a[i];

}

cout<<"该数据的全排列："<

Perm(a,n,0);

return 0;

}

《算法设计与分析》实验报告实验二递归与分治策略应用提高

学号：**************

姓名：*************

班级：*************

日期：2014-2015学年第1学期

一、实验目的

1、深入理解递归的概念和分治法的基本思想

2、正确使用递归与分治策略设计相应的问题的算法

3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

1、Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有一位不同。设计一个算法对任意的n构造相应的Gray码。

2、马的Hamilton周游路线问题。对于给定的m*n的国际象棋棋盘，m和n均为大于5的偶数，且|m-n|<=2，计算m*n的国际象棋棋盘上的一条Hamilton周游路线。

3、对于给定的n个自然数组成的多重集S，计算S的众数及其重数。

提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include "iostream"

using namespace std;

int main()

{

int a[50];

int i,j,maxCount=0,index=0,nCount=0;

int n;

cout<<"输入要输入数字的个数："<>n;

cout<<"输入数字："<

for(i=0;i

{

cin>>a[i];

}

for(i=0;i

{

for(j=0;j

{

if(a[j]==a[i])

nCount++;

}

if(nCount>maxCount)

{

maxCount=nCount;

index=i;

}

nCount=0;

}

cout<

}

《算法设计与分析》实验报告

实验三动态规划策略应用基础

学号：

姓名：

班级：

日期：2014-2015学年第1学期

一、实验目的

1、理解动态规划策略的基本思想。

2、了解适用动态规划策略的问题类型，并能利用动态规划策略设计相应的算法，解决具体问题。

3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。

1、矩阵连乘问题。

2、最长公共子序列问题。

3、流水作业调度问题。

4、最少硬币问题

提交结果：程序设计的源代码及其分析说明和测试运行报告。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include

using namespace std;

const int MAX = 100;

int p[MAX+1],m[MAX][MAX],s[MAX][MAX];

int n;

void matrixChain(){

for(int i=1;i<=n;i++)m[i][i]=0;

for(int r=2;r<=n;r++)

for(int i=1;i<=n-r+1;i++){

int j = r+i-1;

m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];

s[i][j]=i;

for(int k = i+1;k

int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(temp

m[i][j]=temp;

s[i][j]=k;

}

}

}

}

void traceback(int i,int j){

if(i==j)return ;

traceback(i,s[i][j]);

traceback(s[i][j]+1,j);

cout<<"Multiply A"<

int main(){

cin>>n;

for(int i=0;i<=n;i++)cin>>p[i];

matrixChain();

traceback(1,n);

cout<

system("pause");

return 0;

}

《算法设计与分析》实验报告

实验四动态规划策略应用提高

学号：**************

姓名：*************

班级：*************

日期：2014-2015学年第1学期

一、实验目的

1、深入理解动态规划策略的基本思想。

2、能正确采用动态规划策略设计相应的算法，解决实际问题。

3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。

1、编辑距离问题。

2、石子合并问题。

3、租用游艇问题。

提交结果：程序设计的源代码及其分析说明和测试运行报告。

三、设计分析

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include

#include

using namespace std;

int min(int a, int b)

{

return a < b ? a : b;

}

int edit(string str1, string str2)

{

int max1 = str1.size();

int max2 = str2.size();

int **ptr = new int*[max1 + 1];

for(int i = 0; i < max1 + 1 ;i++)

{

ptr[i] = new int[max2 + 1];

}

for(i = 0 ;i < max1 + 1 ;i++)

{

ptr[i][0] = i;

}

for(i = 0 ;i < max2 + 1;i++)

{

ptr[0][i] = i;

}

for(i = 1 ;i < max1 + 1 ;i++)

{

for(int j = 1 ;j< max2 + 1; j++)

{

int d;

int temp = min(ptr[i-1][j] + 1, ptr[i][j-1] + 1);

if(str1[i-1] == str2[j-1])

{

d = 0 ;

}

else

{

d = 1 ;

}

ptr[i][j] = min(temp, ptr[i-1][j-1] + d);

}

}

cout << "**************************" << endl;

for(i = 0 ;i < max1 + 1 ;i++)

{

for(int j = 0; j< max2 + 1; j++)

{

cout << ptr[i][j] << " " ;

}

cout << endl;

}

cout << "**************************" << endl;

int dis = ptr[max1][max2];

for(i = 0; i < max1 + 1; i++)

{

delete[] ptr[i];

ptr[i] = NULL;

}

delete[] ptr;

ptr = NULL;

return dis;

}

int main(void)

{

string str1 = "sailn";

string str2 = "failing";

int r = edit(str1, str2);

cout << "the dis is : " << r << endl;

return 0;

}

《算法设计与分析》实验报告

实验五贪心策略应用基础

学号：

姓名：

班级：

日期：2014-2015学年第1学期

一、实验目的

1、深入理解贪心策略的基本思想。

2、能正确采用贪心策略设计相应的算法，解决实际问题。

3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容

最小生成树问题。

三、设计分析

此算法需要建立辅助数组，来存放U和V-U之间的边，数组按如图所示的方式变化：棕色虚线表示的边是数组中的边，实线表示的边是要加入到最小生成树中的边，该边即将在数组中被删除。

四、算法描述及程序

五、测试与分析

六、实验总结与体会

#include

#include

#define MaxInt 0x3f3f3f3f

#define N 110

int map[N][N],low[N],visited[N];

int n;

int prim()

{

int i,j,pos,min,result=0;

memset(visited,0,sizeof(visited));

visited[1]=1;pos=1;

for(i=1;i<=n;i++)

if(i!=pos) low[i]=map[pos][i];

for(i=1;i

{

min=MaxInt;

for(j=1;j<=n;j++)

if(visited[j]==0&&min>low[j])

{

min=low[j];pos=j;

}

result+=min;

visited[pos]=1;

for(j=1;j<=n;j++)

if(visited[j]==0&&low[j]>map[pos][j])

low[j]=map[pos][j];

}

return result;

}

int main()

{

int i,v,j,ans;

while(scanf("%d",&n)!=EOF)

{

memset(map,MaxInt,sizeof(map));

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

scanf("%d",&v);

map[i][j]=map[i][j]=v;

}

ans=prim();

printf("%d\n",ans);

}

return 0;

}

《算法设计与分析》实验报告

实验六贪心策略应用提高

学号：

姓名：

班级：

日期：2014-2015学年第1学期

一、实验目的

1、深入理解贪心策略的基本思想。

2、能正确采用贪心策略设计相应的算法，解决实际问题。

3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法

二、实验内容