【アルゴリズム】N対の合理的な括弧の組み合わせを印刷する

2526 ワード

タイトル:N対の合理的な括弧の組み合わせを印刷して、例えば入力3出力((())()())()()()()()()()()()())()()()


void PrinAr(char *str,int pos,int left,int right)
{//pos      
    if(NULL == str || left < 0 || right < left) return;
    if(left == 0 && right == 0) 
    {
        cout<<str<<endl;//    
        return ;
    }
    if(left > 0)//        
    {
        str[pos] = '(';
        PrinAr(str,pos+1,left-1,right);
    }

    if(right > left)//        
    {
        str[pos] = ')';
        PrinAr(str,pos+1,left,right-1);
    }

}

void PrinAr(int n)
{
    char *str = new char[2*n+1];
    str[2*n] = '\0';
    PrinAr(str,0,n,n);
    delete []str;
}

思想:間違いなく分治法ですが、具体的には記録する状態を考慮してleft、right、そして書き込む位置Posを全部考えていつ挿入できるかを考えます(':leftが0でなければ、理論的にはずっと挿入できます.これは違反ではありません.いつ挿入できないかを考えます'):ええ、いつ右に挿入できないか考えているでしょう.()のような形をしているのを見つけたら反則したり、挿入したright>挿入したleft、残りのright<残りのleft...だから逆に、残りのright>残りのleftを勝手に挿入することができます

12週目--「最小生成ツリープリムアルゴリズム」

マトリックス求逆アルゴリズム