N ピリオドではない、異なる通常の括弧シーケンスの数を数えます。

この記事では、組み合わせ論と文字列処理の領域からの興味深い問題、「N 周期ではない別個の規則的なブラケット シーケンスを数える」について詳しく掘り下げていきます。これには、個別の有効なブラケット シーケンスを生成し、N 周期のシーケンスをフィルタリングすることが含まれます。この問題について説明し、ブルート フォース アプローチの C コード実装を提供し、テスト ケースを説明します。

問題ステートメントを理解する

整数 N が与えられた場合、タスクは、N 個の期間ではない、長さ 2N の異なる通常のブラケット シーケンスの数を数えることです。シーケンスが M 回繰り返される文字列 S として表現できる場合 (S の長さが N、M > 1)、シーケンスは N 周期です。

通常の括弧シーケンスは、元の文字の間に文字 '1' と ' ' を挿入することで正しい算術式に変換できる文字列です。たとえば、シーケンス "(())" は通常ですが、") (" と "(()" は異なります。

＃＃＃方法＃＃＃

問題が複雑なため、直接の数学的解決策は実現できない場合があります。代わりに、プログラムによるアプローチを使用して括弧シーケンスを生成し、基準に一致する括弧シーケンスの数を数える必要があります。

再帰関数を使用して、長さ 2N のすべての可能な括弧シーケンスを生成します。シーケンスの生成中に、2 つの重要なパラメーターを追跡します: 括弧のバランス (開き括弧の数は決して少なくなりません)閉じ括弧の数) と開き括弧の数 (N を超えてはなりません)。

N 期間シーケンスを除外するために、生成された各シーケンスをチェックします。シーケンスが長さ N のより小さいシーケンスの繰り返しである場合、カウントから除外します。

C 実装

これは、C の問題を解決するための強引なアプローチです。このメソッドは、考えられるすべてのブラケット シーケンスを生成し、各シーケンスが N 周期であるかどうかを確認し、そうでない場合はカウントを増分します。このソリューションは、指数関数的な時間計算量があり、大きな入力にはうまく拡張できないため、小さな入力サイズに適しています。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃テストケース＃＃＃

N = 3 のテスト ケースを考えてみましょう。このコードは、3 周期ではない長さ 6 の 5 つの異なる通常のブラケット シーケンスをすべて生成します: ((()))、(()())、(() )()、()(())、()()().

＃＃＃結論＃＃＃

この記事では、N ピリオドではないさまざまな規則的なブラケット シーケンスを数える問題を徹底的に解決する方法を紹介します。この方法は小規模な入力を処理できますが、考えられるすべての括弧シーケンスを生成してチェックする必要があるため、この問題は指数関数的に複雑になるため、大規模な入力には適していないことに注意することが重要です。

以上がN ピリオドではない、異なる通常の括弧シーケンスの数を数えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。