董凌-5.5.txt

这是很不错的计算机算法

#include<stdio.h>
#include<iostream.h>
#include<fstream.h>

    long int bestresult(int *p,int n)  //连乘最优解函数

	{
	    long int **m,temp;                    //定义存储矩阵
     	m =new long int* [n+1];          //M的长度为N+1，从M[0]到m[n]
	    for(int rows=0;rows<n+1;rows++)
		m[rows]= new long int[n+1];

	
	    int i,r,j,t,k;
	    for(i=1;i<=n;i++)
	  	m[i][i]=0;                      //m矩阵对角线赋初值 
    
    	for(r=2;r<=n;r++)               //对每一条对角线循环
	     for(i=1;i<=n-r+1;i++)	         
		 {
		   j=i+r-1;
           m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];   //求得在第一个矩阵处断开的特征值  
		   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;
		   }
		 }
	   
	    temp=m[1][n];
	   	for(i=0;i<n+1;i++)//释放数组m所占内存    
	    delete[] m[i];  
	    delete[] m;
     
		 return temp;
	}

	
	int main()
	{
	    long int result;
        int n,*p;     //定义连乘的矩阵数,矩阵维数                
    	ifstream fin("input.txt");
    	if(fin.fail())
		{
	    	cout<<"read error"<<endl;
	        return -1;
		}

	   

    	fin>>n;                  //输入联乘矩阵数量
    	
		if(!(p=new int[n+1]))
		{
          cout<<"insufficient memory!"<<endl; //分配不成功，退出
          return -1;
		}
    
	
	    for(int i=0;i<=n;i++)
			fin>>p[i];                      //输入各个矩阵的维数
     
	     fin.close();                       //关闭输入文件
	
	     result=bestresult(p,n);           //求结果


     
     	ofstream out("output.txt");
        
		out<<result;
        
		out.close();

	     delete []p;
	    	return 0;
	
	}