《算法设计与分析》实验

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

学号： 姓名：

实验一 分治法求解**问题

一、实验目的

1.掌握分治法的设计思想并能熟练应用；

2.理解分治与递归的关系。

二、实验题目

在有序序列中(r1,r2,…,rn)中,存在序号i（1≤i≤n）,使得ri=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n).

三、实验程序

//以(0,2,3,3,5,7,8,10,12,13)为例

#include<iostream>

using namespace std;

void PrintData(int data[],int length)

{

}

int Bisearch(int data[],int begin ,int last)

{

if ( mid < data[mid] ) int mid=(begin + last) /2; if (mid+1 == data[mid]) { } return mid; cout<<"有序序列是："; for (int i=0;i<length;i++) { } cout<<endl; cout<<data[i]<<" ";

}

{ } else { } Bisearch(data,mid+1 ,last); Bisearch(data,begin ,mid-1); return 0;

void main()

{

} int data[10]={0,2,3,3,5,7,8,10,12,13}; PrintData(data,10); cout<<"要查找的值"<<data[x]<<endl; int x; x=Bisearch(data,0,9);

四、程序运行结果

实验二 动态规划法求解单源最短路径问题

一、实验目的

1.深刻掌握动态规划法的设计思想；

2.熟练应用以上算法思想求解相关问题。

二、实验题目

设有一个带权有向连通图，可以把顶点集划分成多个互不相交的子集，使得任一条边的两个顶点分属不同子集，称该图为多段图。采用动态规划法求解多段图从源点到终点的最小代价路径。

三、实验程序

#include<iostream>

using namespace std;

#define INFINITY 100

#define MAX 20

typedef struct

{

int vextex,edge;

int arcs[MAX][MAX]; //保存两个顶点之间的边长

}Graph; //图的结构体

void Creat_Graph(Graph &G)

{

int i,j;

G.vextex=10; //顶点数

G.edge=18; //边的数

for(i=0;i<G.vextex;i++)

for(j=0;j<G.vextex;j++)

G.arcs[i][j]=INFINITY; //初始最大

G.arcs[0][1]=4; G.arcs[0][2]=2;G.arcs[0][3]=3; G.arcs[1][4]=9;G.arcs[1][5]=8;

G.arcs[2][4]=6; G.arcs[2][5]=7;G.arcs[2][6]=8; G.arcs[3][5]=4;G.arcs[3][6]=7;

G.arcs[4][7]=5; G.arcs[4][8]=6;G.arcs[5][7]=8; G.arcs[5][8]=6;G.arcs[6][7]=7;

G.arcs[6][8]=5; G.arcs[7][9]=7;G.arcs[8][9]=3;

}

void FPath(Graph G)

{

int i,j;

int n=10;

int cost[10]; //存储子问题表的表格

int path[10]; //存储状态

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

{

cost[i]=INFINITY;

path[i]=-1;

}

cost[9]=0; //因为9到最后一个定点的距离0

for(i=n-2;i>=0;i--)

{

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

{

if(G.arcs[i][j]+cost[j]<cost[i]) //判断条件

{

cost[i]=G.arcs[i][j]+cost[j];

path[i]=j;

}

}

}

cout<<"长度为"<<cost[0]<<"."<<endl;

i=0;

cout<<"最短路径为:0";

while(path[i]<=n-1 && i<n-1)

{

cout<<"→"<<path[i];

i=path[i];

}

cout<<endl;

}

void main()

{

Graph G;

Creat_Graph(G);

FPath(G);

}

四、程序运行结果

实验三 贪心法求解单源点最短路径问题

一、实验目的

1.掌握贪心法的设计思想；

2.分析比较同一个问题采用不同算法设计思想求解的结果。

二、实验题目

设有一个带权有向连通图，可以把顶点集划分成多个互不相交的子集，使得任一条边的两个顶点分属不同子集，称该图为多段图。采用贪心法求解多段图从源点到终点的最小代价路径。

三、实验程序

#include<iostream>

using namespace std;

#define INFINITY 100

#define MAX 20

//图的结构体

typedef struct

{ //顶点信息

int vextex,edge;

int arcs[MAX][MAX]; //保存两个顶点之间的权值

}Graph;

void Creat_Graph(Graph &G)

{

int i,j;

G.vextex=10; //顶点数

G.edge=18; //边的数

for(i=0;i<=G.vextex;i++) //所有权值初始最大

for(j=0;j<=G.vextex;j++)

G.arcs[i][j]=INFINITY;

G.arcs[0][1]=4; G.arcs[0][2]=2; G.arcs[0][3]=3; //边上的权值

G.arcs[1][4]=9; G.arcs[1][5]=8; G.arcs[3][5]=4;

G.arcs[2][4]=6; G.arcs[2][5]=7; G.arcs[2][6]=8;

G.arcs[4][7]=5; G.arcs[4][8]=6; G.arcs[5][7]=8;

G.arcs[6][8]=5; G.arcs[7][9]=7; G.arcs[8][9]=3;

G.arcs[3][6]=7; G.arcs[5][8]=6; G.arcs[6][7]=7;

}

void FPath(Graph &G)

{

int i,j,min;

int n=10;

int cost[10]; //存储所过路径权值

int path[10]; //存储状态

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

{

cost[i]=INFINITY;

path[i]=INFINITY;

}

cost[0]=0; //因为0到0的权值为0

path[0]=0;

i=0;

loop: //选择

i=path[i];

min=G.arcs[i][1];

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

{

if(G.arcs[i][j]<INFINITY && G.arcs[i][j]<min)//判断条件

{

min=G.arcs[i][j]; path[i]=j; }

}

cost[path[i]]=G.arcs[i][path[i]];

if(i<=9)

goto loop;

for(i=0;i<10;i++)

if(cost[i]<INFINITY)

cout<<"长度为"<<cost[0]<<"."<<endl;

cout<<"最短路径为:0";

for(i=0;i<10;i++)

if(path[i]<INFINITY)

cout<<"→"<<path[i];

}

void main()

{

Graph G;

Creat_Graph(G);

FPath(G);

} cost[0]=cost[0]+cost[i];

四、程序运行结果

实验四 回溯法求解0/1背包问题

一、实验目的

1.掌握回溯法的设计思想；

2.掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；

二、实验题目

给定n种物品和一个容量为C的背包，选择若干种物品（物品不可分割），使得装入背包中物品的总价值最大。采用回溯法求解该问题。

三、实验程序

#include<iostream>

using namespace std;

class Knap

{

public:

int Knapsack(int p[],int w[],int c,int n );

void print()

{

for(int m=1;m<=n;m++)

{ cout<<bestx[m]<<" ";}

cout<<endl;

}

int Bound(int i);

void Backtrack(int i);

int c; //背包容量

int n; //物品数

int *w; //物品重量数组

int *p; //物品价值数组

int cw; //当前重量

int cp; //当前价值

int bestp; //当前最优值

int *bestx; //当前最优解

int *x; //当前解

};

int Knap::Bound(int i)

{

int cleft=c-cw;//剩余容量

int b=cp;

while(i<=n&&w[i]<=cleft) //以物品单位重量价值递减序装入物品 {

cleft-=w[i];

b+=p[i];

i++;

}

//装满背包

if(i<=n)

b+=p[i]/w[i]*cleft;

return b;

}

void Knap::Backtrack(int i)

{

if(i>n)

{

if(bestp<cp)

{

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

bestx[j]=x[j];

bestp=cp;

}

return;

}

if(cw+w[i]<=c) //搜索左子树

{

x[i]=1;

cw=cw+w[i];

cp=cp+p[i];

Backtrack(i+1);

cw=cw-w[i];

cp=cp-p[i];

}

if(Bound(i+1)>bestp)//搜索右子树

{

x[i]=0;

Backtrack(i+1);

}

}

class Object

{

public:

int Knapsack(int p[],int w[],int c,int n);

int ID;

float d;

};

int Knapsack(int p[],int w[],int c,int n)

{

int W=0; //为Knap::Backtrack初始化

int P=0;

int i=1;

Object *Q = new Object[n];

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

{

Q[i-1].ID=i;

Q[i-1].d=1.0*p[i]/w[i];

P+=p[i];

W+=w[i];

}

if(W<=c) return P;

float f;

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

for(int j=i;j<n;j++)

{

if(Q[i].d<Q[j].d)

{

f=Q[i].d;

Q[i].d=Q[j].d;

Q[j].d=f;

}

}

Knap K;

K.p = new int[n+1];

K.w = new int[n+1];

K.x = new int[n+1];

K.bestx = new int[n+1];

K.x[0]=0;

K.bestx[0]=0;

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

{

K.p[i]=p[Q[i-1].ID];

K.w[i]=w[Q[i-1].ID];

}

K.cp=0;

K.cw=0;

K.c=c;

K.n=n;

K.bestp=0;

K.Backtrack(1); //回溯搜索

K.print();

delete [] Q;

delete [] K.w;

delete [] K.p;

return K.bestp;

}

void main()

{

int *p,*w;

int c=0,n=0,i=0;

cout<<"请输入背包容量(c)：";

cin>>c;

cout<<"\n请输入物品的个数(n)：";

cin>>n;

p=new int[n+1];

w=new int[n+1];

p[0]=0;

w[0]=0;

cout<<"\n物品的价值(p)和重量(w)数据如下\n"<<endl; for(i=1;i<=n;i++)

{ cout<<"请输入第"<<i<<"个物品的价值(p)和重量(w):"; cin>>p[i]>>w[i];

}

cout<<"最优解为(bestx)："<<endl;

cout<<"最优值为(bestp)："<<endl;

cout<<Knapsack(p,w,c,n)<<endl;

}

四、程序运行结果

本文来源：https://www.bwwdw.com/article/j4u1.html