《算法设计与分析》实验.docVIP

《算法设计与分析》实验报告 学号： 姓名： 实验一 分治法求解**问题 一、实验目的 1.掌握分治法的设计思想并能熟练应用；2.理解分治与递归的关系。 二、实验题目 在有序序列中中,存在序号（≤）=。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为. 三、实验程序 //以(0,2,3,3,5,7,8,10,12,13)为例 #includeiostream using namespace std; void PrintData(int data[],int length) { cout有序序列是：; for (int i=0;ilength;i++) { coutdata[i] ; } coutendl; } int Bisearch(int data[],int begin ,int last) { int mid=(begin + last) /2; if (mid+1 == data[mid]) { return mid; } if ( mid data[mid] ) { Bisearch(data,begin ,mid-1); } else { Bisearch(data,mid+1 ,last); } return 0; } void main() { int x; int data[10]={0,2,3,3,5,7,8,10,12,13}; PrintData(data,10); x=Bisearch(data,0,9); cout要查找的值data[x]endl; } 四、程序运行结果 实验二 动态规划法求解单源最短路径问题 一、实验目的 1.深刻掌握动态规划法的设计思想；2.熟练应用以上算法思想求解相关问题。 二、实验题目 设有一个带权有向连通图，可以把顶点集划分成多个互不相交的子集，使得任一条边的两个顶点分属不同子集，称该图为多段图。采用动态规划法求解多段图从源点到终点的最小代价路径。 三、实验程序 #includeiostream 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.vextex;i++) for(j=0;jG.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;in;i++) { cost[i]=INFINITY; path[i]=-1; } cost[9]=0;