算法分析实验三报告

《算法分析实验三报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》实验报告一、头验内容描述和功能分析.一、算法过程设计.二、程序调试及结果（附截图）四、源代码（附源代码）.一、实验内容描述和功能分析.1•矩阵连乘问题内容描述：给定n个矩车{Al,A2,…，An},射Ai与Ai+1是可乘的，i=l,2，…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序井算矩阵连乘积需要的数乘次数最少。功能分析：输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据，接下来有2比行数据，每组测试数据占2行，每组测试数据第一行是1个整数n,表示有n个

2、矩阵连乘，接下来一行有n+1个数，表示是n个矩阵的行及第n个矩阵的列，它们之间用空格隔开。输出应该有C行，即每组测试数据的输出占一行，它是计算出的矩阵最少连乘积次数。例如：输入：1输出：75003101005502.PebbleMerging内容描述：在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。编程任务：对于给定n堆石子，编程计算

3、合并成一堆的最小得分和最大得分。功能分析：输入由多组测试数据组成。每组测试数据输入的第1行是正整数n,l

4、图）.1•矩阵连乘问题2.PebbleMerging源代码（附源代码）.1•矩阵连乘问题#includeintmain(){inta[50J,b[50J[50J,c[50][50],z,n;inti,r,j,k,t;scanf("%d",&z);while(z—){scanf(H%dH,&n);for(i=0;i<=n;++i)scanf(”％d“,&a[i]);for(i=1;i<=n;++i)b[i][i]=0;for(r=2;r<=n;++r)for(i=1;iv二n・r

5、+1;+4-i){j=i+r-1；b[i][j]=b[i+l][j]4-a[i-l]*a[i]*a[j];c[i][j]=i；for(k=i+1;kvj;++k){t=b[i][k]+b[k+l][j]+a[i・l]*a[k]*a[j];if(tintmain(){intdpminf200][200],mi

6、n[200][200],mins;intdpmax[200][200],max[200][200],maxs;inta[200],i,n,j,k,temp,1;while(scanf(”％d”，&n)!=EOF){for(i=1;i<=n;+4-i)scanf(”％cT，&i]);for(i=1;ivn;++i)a[i4-n]=a[iJ;for(i=1;iv2*n;++i){niin[i][i]=max[i][i]=0;dpmax[i][i]=dpmin[i][i]=a[i];dpmax[i][

7、i+1]=dpmin[i][i+1]=a[i]+a[i+1];min[iJ[i+1]=max[i][i+1]=a[i]+a[i+1];}for(i=1;ivn・1;++i)for(1=1,j=2+i;jv2*n;++j,++1){for(k=1+1;k<=j;++k){if(k==l+1){dpmin[1][j]=dpmin[1][k-1]+dpmin[k][j]+min[l][k・l]+min[k][j];if(l==k・1&&k!=j)min[1][j]=a[1]4-min[k][j];el

8、seif(l!=k・1&&k==j)min[l][j]=min[l][k・l]+a[k];elsemin[1][j]=min[1J[k-1]+min[k][j];dpmax[1][j]=dpmax[1][k-1]+dpmax[k][j]+max[1][k-1]+max[k][j];if(l==k・1&&k!=j)max[1JljJ=a[1J+max[kJ[j];elseif(l!=k-1&&k==j)max[1][j]=max[1][k-1]+a[k];elsemax[1][j]=max[1][