ACM程序&算法

   算法设计 动态规划 矩阵连乘问题 收藏

////////////////////////////////////////////////////////////////
//TITLE: 矩阵连乘问题
//EDITOR:小桥流水
//DADE： 2008.11.16
//TOOL:  Microsoft Visual Studio 2008
////////////////////////////////////////////////////////////////
 
#include<iostream>
usingnamespace std;
 
//计算最优值
voidMatrixChain(int *p,intn,int **m,int **s)
{
   for (inti = 1; i <= n;i++)
   {
       m[i][i] = 0;
   }
   for (intr = 2; r <= n;r++)
   {
       for (inti = 1;i <=n-r+1;i++)
       {
           int j = i+r-1;
           m[i][j] =m[i+1][j] +p[i-1]*p[i]*p[j];
           s[i][j] =i;
           for(intk = i+1;k <j;k++)
           {
               int t = m[i][k] + m[k+1][j] +p[i-1]*p[k]*p[j];
               if (t <m[i][j])
               {
                   m[i][j] =t;
                   s[i][j] =k;
               }
           }
       }
   }
}
 
//构造最优解
voidTraceback(inti,intj,int **s)
{
   if (i ==j)
       return ;
   Traceback(i,s[i][j],s);
   Traceback(s[i][j]+1,j,s);
   cout<<"Multiply A"<<i<<","<<s[i][j];
   cout<<"and A"<<s[i][j]+1<<","<<j<<endl;
}
 
intmain()
{
   int N,*P,**M,**S;
   cout<<"输入矩阵的个数N: ";
   cin>>N;
   P = new int [N+1]; //为矩阵的维数分配空间
   M = new int *[N+1];//为二维数组M动态分配空间
   for (inti = 0; i <= N;i++)
   {
       M[i] =new int [N+1];
   }
   S = new int *[N+1]; //为记录最优断开位置的二
   //维数组S动态分配空间
   for (inti = 0; i <= N;i++)
   {
       S[i] =new int [N+1];
   }
 
   for (inti = 0; i <= N;i++)
   {
       cin>>P[i];
   }
  www.zzzyk.com
   MatrixChain(P,N,M,S);
   Traceback(1,N,S);
 
   //释放动态分配的空间
   delete []P;
   for (inti = 0; i <=N;i++)
   {
       delete M[i];
       M[i] =NULL;
   }
   delete []M;
   M = NULL;
   for (inti = 0; i <=N;i++)
   {
       delete S[i];
       S[i] =NULL;
   }
   delete []S;
   S = NULL;
 
   return 0;
}

补充：软件开发 , C++ ,

上一个：仿函数
下一个：图像缩放函数