マトリックスチェーン最適代価計算(本に写したものを知らない)

3086 ワード

 #include <iostream>
#include <initializer_list>
#include <utility>
#include <typeinfo>
#include <vector>
#include <iterator>
enum MValue:unsigned long { MAXVALUE=1000000 };
template<typename T=long>
class MatrixChainOrder{ // . 
 private:
  std::vector<std::vector<T>> M;
  std::vector<std::vector<T>> S;
  std::vector<T> chains;
  public:
   template<typename U=long>
   MatrixChainOrder(const std::initializer_list<U>& il)noexcept(true); //([&theIl]()->bool { (theIl.size()==0)?true:false});
   ~MatrixChainOrder()noexcept(true);
   void chainOrder();
   void print();
};
template<typename T>
template<typename U>
MatrixChainOrder<T>::MatrixChainOrder(const std::initializer_list<U>& il)noexcept(true)
                    :chains(il)
{
 int temp=chains.size();
 std::vector<T> tempVec(temp); // temp vector; 
 for(int i=0; i<temp; ++i){
  this->M.push_back(tempVec);
  this->S.push_back(tempVec);
 }
}
template<typename T>
MatrixChainOrder<T>::~MatrixChainOrder()noexcept(true)
{
 int temp=M.size();
 for(int i=0; i<temp; ++temp){
  M[i].clear();
  S[i].clear();
 }
 
 M.clear();
 S.clear();
 std::cout<<"destroy it"<<std::endl;
}
template<typename T>
void MatrixChainOrder<T>::chainOrder()
{
 int n=this->chains.size();//n . :A(x,y),A1(x1,y1), chains={x*y*x1*y1}; 
 /*
  Ai........Aj, . k   i<=k<j; 
 M[i][j]=M[i][k]+M[k+1][j]+x*x1*y1;
 */
 int j;
 int q;//a temporary value.
 if(typeid(T)==typeid(long int) || typeid(T)==typeid(double)){
  
  std::cout<<"success to enter"<<std::endl;
  for(int i=0; i<n; ++i){
   this->M[i][i]=0;//M[1][1], M[2][2], M[3][3]; M chains i-i . 
  }
  
  for(int l=2; l<n; ++l){// chains . n=6; 
   for(int i=0; i<n-l+1; ++i){//l=2,i=5,4,3...1; 
    j=i+l-1;//j 6,5,4,3,2,1....
     M[i][j]=MAXVALUE;
     for(int k=i; i<j; ++i){//k=0,1,2,...5;  2...4;  ....
      q=M[i][k]+M[k+1][j]+chains[i-1]*chains[k]*chains[j];// i-j . 
      if(q < M[i][j]){
       M[i][j]=q;
       S[i][j]=k;// . 
      }
     }
   }
  } 
 }
}
 
 template<typename T>
 void MatrixChainOrder<T>::print()
 {
  std::ostream_iterator<T> out(std::cout, "  ");
  std::cout<<"print M:"<<std::endl;
  if(M.empty()){
   std::cout<<"chains are less than 1"<<std::endl;
  }else{
   
   for(auto tempM: this->M){
    
    for(auto tempT:tempM){
     *(out++)=tempT;
    }
   }
   
   std::cout<<"
"<<"print S:"<<std::endl;    for(auto tempS: this->S){     for(auto tempT:tempS){      *(out++)=tempT;     }    }   }  }    int main()  {      MatrixChainOrder<> myChains( {30l, 35l, 35l, 15l, 15l, 5l, 5l, 10l, 10l, 20l, 20l, 25l} );   myChains.chainOrder();   myChains.print();   return 0;  }