さいてきにじゅんさく
3674 ワード
#include <iostream>
#include <type_traits>
#include <vector>
#include <initializer_list>
#include <typeinfo>
enum:int { MAXVALUE=999 };
template<typename T=double, typename Ty=double, typename Type=double>
class BestTree{
private:
T** root;// .
Ty** e;// .
Type** w;// .
std::vector<Ty> p;
std::vector<Type> q;
int pLength;
public:
template<typename X=double, typename Y=double>
BestTree(const std::initializer_list<X>& _p, const std::initializer_list<Y>& _q);// _p , _q .
~BestTree();
void OptimalBST();
void Subtree();
};
template<typename T, typename Ty, typename Type>
template<typename X, typename Y>
BestTree<T, Ty, Type>::BestTree(const std::initializer_list<X>& _p, const std::initializer_list<Y>& _q)
:p(_p),
q(_q)
{
std::cout<<"test"<<std::endl;
if(typeid(T)!=typeid(X) || typeid(Ty)!=typeid(Y) || typeid(Type) != typeid(Y)){ // .
throw std::bad_cast();
}
std::cout<<"test"<<std::endl;
this->pLength=_q.size();
root=new X*[pLength];// [pLenght][pLenght];
for(int i=0; i<pLength; ++i){
root[i]=new X[pLength];
}
for(int i=0; i<pLength; ++i){
for(int j=0; j<pLength; ++j){
this->root[i][j]=T(0);
}
}
e=new Y*[pLength+1];// 。
w=new Y*[pLength+1];// T,Ty Y .
for(int i=0; i<pLength+1; ++i){
e[i]=new Y[pLength];
w[i]=new Y[pLength];
}
typename std::initializer_list<Y>::iterator iterB=_p.begin();
//typename std::initializer_list<Y>::iterator iterE=_p.end();
for(int i=0; i<pLength+1; ++i){
for(int j=0; j<pLength; ++j){
w[i][j]=T(0);
e[i][j]=T(0);
}
}
for(int m=1; m<pLength+1; ++m){
e[m][m-1]= *(iterB+m-1);
w[m][m-1]= *(iterB+m-1);
}
std::cout<<"success"<<std::endl;
}
template<typename T, typename Ty, typename Type>
void BestTree<T, Ty, Type>::OptimalBST()
{
std::cout<<"enter"<<std::endl;
for(int l=1; l<this->pLength+1; ++l){ // 1 <= i <= j <= n .
for(int i=1; i<this->pLength-l+1; ++i){
int j=i+l-1; //j 1, 2, 3, 4....
this->e[i][j]=MAXVALUE; // . e[i][i]=MAXVALUE;
this->w[i][j]=w[i][j-1]+p[j]+q[j]; // w[i][i-1].
for(int k=i; k<j+1; ++k){ // i=2 .
T t=e[i][k-1]+e[k+1][j]+w[i][j]; // i-j k .( .)
if(t < e[i][j]){
e[i][j]=t;
root[i][j]=k;
}
}
}
}
}
template<typename T, typename Ty, typename Type>
void BestTree<T, Ty, Type>::Subtree()
{
for(int i=0; i<pLength; ++i){
for(int j=0; j<pLength; ++j){
std::cout<<this->root[i][j]<<" ";
}
std::cout<<std::endl;
}
}
template<typename T, typename Ty, typename Type>
BestTree<T, Ty, Type>::~BestTree()
{
if(root != nullptr && w != nullptr && e != nullptr){
for(int i=0; i<pLength; ++i){
delete[] root[i];
}
delete[] root;
for(int i=0; i<pLength+1; ++i){
delete[] w[i];
delete[] e[i];
}
delete[] w;
delete[] e;
}
p.clear();
q.clear();
}
int main()
{
BestTree<> myTree( {double(-1), 0.15, 0.1, 0.05, 0.1, 0.2}, {0.05, 0.1, 0.05, 0.05, 0.05, 0.1});
// double(-1), . vector<int> != vector<double>;
myTree.OptimalBST();
myTree.Subtree();
return 0;
}