《算法设计与分析》实验

学号： 姓名：

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

一、实验目的

1.掌握分治法的设计思想并能熟练应用； 2.理解分治与递归的关系。 二、实验题目

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

三、实验程序

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

#include

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;icout<cout<}

{ } 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<<\"要查找的值\"<x=Bisearch(data,0,9);

四、程序运行结果

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

一、实验目的

1.深刻掌握动态规划法的设计思想； 2.熟练应用以上算法思想求解相关问题。

二、实验题目

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

三、实验程序

#include 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;iG.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;icost[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]=G.arcs[i][j]+cost[j]; path[i]=j; }

} }

cout<<\"长度为\"<cout<<\"最短路径为:0\";

while(path[i]<=n-1 && icout<<\"→\"<cout<void main() {

Graph G;

Creat_Graph(G); FPath(G); }

四、程序运行结果

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

一、实验目的

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

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

二、实验题目

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

三、实验程序

#include 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;icost[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]{

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]cout<<\"长度为\"<void main() {

Graph G; Creat_Graph(G); FPath(G); }

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

四、程序运行结果

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

一、实验目的

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

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

二、实验题目

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

三、实验程序

#include 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<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(bestpfor(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;iif(Q[i].df=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\"<{ cout<<\"请输入第\"<>p[i]>>w[i]; }

cout<<\"最优解为(bestx)：\"<四、程序运行结果