算法实验动态规划上机.docVIP

实验3动态规划上机 [实验目的] 1．掌握动态规划的基本思想和效率分析方法； 2．掌握使用动态规划算法的基本步骤； 3．学会利用动态规划解决实际问题。 [实验要求] 按以下实验内容完成题目，并把编译、运行过程中出现的问题以及解决方法填入实验报告中，按时上交。 [实验学时] 2学时。 [实验内容] 一、实验内容 利用动态规划算法编程求解多段图问题，要求读入多段图，考虑多段图的排序方式，求源点到汇点的最小成本路径。并请对自己的程序进行复杂性分析。 二、算法描述 先输入点的个数和路径数以及每段路径的起点、长度、终点，再计算所有路径的值大小，比较输出后最小值。 三、源程序 #define N 2147483647 #includestdio.h #includeiostream.h void main() { int i,pointnum,j; cout输入图中 点的个数:endl; cinpointnum; int **array; //array数组描述多段图 int *array2; //array2记录距离起点的最小路径 int *array3; //array3记录上一点编号 array=new int*[pointnum]; array2=new int[pointnum+1]; array3=new int[pointnum+1]; for(i=0;ipointnum;i++) { array[i]=new int[pointnum]; array2[i]=N; array3[i]=N; } array2[pointnum]=N; array3[pointnum]=N; for(i=0;ipointnum;i++) { for(j=0;jpointnum;j++) { array[i][j]=N; } } cout输入多段图中 路径条数endl; int pathnum; cinpathnum; int a,k; cout依次输入图中每段路径endl起点，长度，终点endl; array2[1]=0; array3[1]=0; for(k=0;kpathnum;k++) { cini; cina; cinj; array[i][j]=a; if(array2[j](a+array2[i])) { array3[j]=i; array2[j]=a+array2[i]; } // coutarray3[j] array2[j]endl; } k=0; i=pointnum; for(;;) { if(array3[i]!=0) { k++; i=array3[i]; } else break; } // coutk; int *array4; array4=new int[k+1]; i=pointnum; for(j=k;j=0;j--) { array4[j]=i; i=array3[i]; if(i==0) break; } i=pointnum; coutendl最短路径endlarray2[i]; coutendl[ ; for(j=0;j=k;j++) { coutarray4[j] ; } cout]endl; } 四、程序的复杂度分析 O（n）= n2=16 五、程序运行结果及截图