算法设计与分析 实验报告及答案)

实验报告配套教材：

书名：算法设计与分析
作者：王晓东
出版社：清华大学出版社

实验报告概述：

　　#include<stdio.h> 　　 #define MAX 100 　　int main() 　　 { 　　　　int p[MAX],i,j,k,r,t,n; 　　 int m[MAX][MAX]; //记录从第i到第j个矩阵连乘的最少计算次数 　　 int s[MAX][MAX]; //记录从第i到第j个矩阵连乘的断开位置 　　 printf("输入连乘矩阵的个数:"); 　　 scanf("%d",&n); 　　 for(i=0;i<n;i++) 　　 { 　　printf("输入第%d个矩阵行数:",i+1); 　　 scanf("%d",&p[i]); //读入p[i]的值(注意：p[0]到p[n]共n+1项) 　　 } 　　 printf("输入第%d个矩阵列数:",n); 　　 scanf("%d",&p[n]); 　　 for(i=1;i<=n;i++) //初始化m[i][i]=0 　　 m[i][i]=0; 　　 for(r=1;r<n;r++) //r为i、j相差的值 　　for(i=1;i<n;i++) //i为行 　　{ 　　j=i+r; //j为列 　　m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; //给m[i][j]赋初值 　　s[i][j]=i; 　　for(k=i+1;k<j;k++) 　　{ 　　t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; 　　 if(t<m[i][j]) 　　{ 　　m[i][j]=t; //m[i][j]取最小值 　　 s[i][j]=k; 　　} 　　 } 　　} 　　 printf("最少计算次数:%d\n\n",m[1][n]); 　　 }