4

n 対の括弧のすべての有効な (たとえば、適切に開いたものと閉じたもの) の組み合わせを出力するアルゴリズムを実装します。例: 入力: 3 (例: 3 対の括弧) 出力: ()()()、()(())、(())()、((()))

答えは次のとおりです。

private static void printPar(int count)
{
    char[] str = new char[count*2];
    printPar(count,count,str, 0);
}

private static void printPar(int l, int r, char[] str, int count)
{
    if(l < 0 || r < l)
        return;

    if (l ==0 && r == 0)
    {
        System.out.println(str);
    }
    else
    {
        if (l > 0 )
        {
            str[count] = '(';
            printPar(l-1, r, str, count + 1);
        }

        if (r > 0)
        {
            str[count] = ')';
            printPar(l, r-1, str, count + 1);
        }
    }
}

しかし、誰かが説明が十分に簡単であると主張していますが、私は解決策を完全には理解していません。(このコードは正常に動作します)

私の意見では、このコードは、左括弧がさらにある場合と同じように機能し、次に左括弧を追加します。したがって、（（（）））の条件のみ if (l > 0 ) が r > 0 の前に現れるため、常に左側のすべての条件を最初に処理する必要があります。

しかし、このコードはこの状況 "()(())" をどのように処理するのでしょうか? 私はこのコードをデバッグし、「((()))」を出力した後にそれを見つけます。l =1、r =3、および str="((()))" および count = 2 の状況になりました。これは私には意味がありません。

また、誰かが時間/空間の複雑さとは何かを説明できれば、それは私にとって非常に役立ちます.

前もって感謝します。

4

3 に答える 3

7

の括弧がどのように書かれるかを示すために木を描きましたcount = 3。各ノードは関数呼び出しを表し、そのテキストは、呼び出し関数が追加したものに応じて(またはになります。)葉は、それが印刷される呼び出しです。

このツリーの深さは (明らかに) せいぜい2.countであるため、空間の複雑さはO(count)です。

すべての関数呼び出しは a(または a のいずれかを追加できるため)、時間の計算量は最大で=です。O(2number of function calls)O(22 count)

しかし、呼び出しは条件付きであるため、時間の複雑さは最終的に少なくなります。より具体的には、約 のように見えますが、まだ証明していません。O(22 count/count)

于 2013-10-26T18:57:56.120 に答える
3

r < l にならないため、コードは正常に実行されます。その場合は、その組み合わせを破棄して戻ります。つまり、右ブラケットは左ブラケットの後にのみ配置できます。

破棄された再帰呼び出しも数えると、複雑さの順序は です(2n)!/( n! * n! )。これは n '(' と n ')' の順列の数です。

コードをトレースしようとすると、次のように実行されます。

(
 (
  (
   )
    )
     ) 
      ((()))
  )
   (
    )
     )
      (()())
   )
    (
     )
      (())()
 )
  (
   (
    )
     )
      ()(())
(
 )
  (
   )
    (
     )
      ()()()
于 2013-10-26T18:54:00.650 に答える
3

再帰中、アルゴリズムは残りの左括弧の数 (l)、残りの右括弧の数 (r)、これまでの結果 (str)、および生成された括弧の数 (count) を追跡します。

括弧が残っていない場合は、結果が出力されます。

少なくとも 1 つの左括弧が残っている場合は、それが使用され、関数が再帰的に実行され、現在のプレフィックスで始まるすべての結果が生成されます

次に、少なくとも 1 つの右括弧が残り、少なくとも 1 つの左括弧が閉じられていない場合、右括弧が使用され、関数は再帰します。

しかし、このコードはこの状況 "()(())" をどのように処理するのでしょうか? 私はこのコードをデバッグし、「((()))」を出力した後にそれを見つけます。l =1、r =3、および str="((()))" および count = 2 の状況になりました。これは私には意味がありません。

出力後((()))に関数がパラメーター1、3、((()))、および2で呼び出されるとcount=2、 の唯一の有効な部分が であることを示しstrます((。次に、)パラメーター1、2、(()、および を使用して再帰する前に a を追加し続け3、その結果(()())、次の組み合わせが出力され、その後に()(())、およびが続き()()()ます。

于 2013-10-26T19:05:00.660 に答える