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

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

delete[] ptr[i]; ptr[i] = NULL; }

delete[] ptr; ptr = NULL;

return dis; }

int main(void) {

string str1 = \ string str2 = \

int r = edit(str1, str2);

cout << \ 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(\ {

memset(map,MaxInt,sizeof(map)); for(i=1;i<=n;i++)

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

scanf(\

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

ans=prim();

printf(\ }

return 0; }

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

实验六 贪心策略应用提高

学号：

姓名： 班级：

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

一、实验目的

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

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

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

二、实验内容