問題タブ [catalan]

過去数時間、この質問を解こうとしましたが、理解できません。これを計算するには一種の数学的計算が必要であることは知っていますが、正確に計算する方法はわかりません。私は完全に迷っているので、このコードが意味をなさないことを知っています。解決策に近づくためのヒントや助けをいただければ幸いです。

教授に尋ねると、3 つの異なる組み合わせに対して 26^3 などのアルファベットを使用した順列/組み合わせに似ているというヒントを教えてくれましたが、これはあまり役に立ちませんでした。

私が知っていること：

1. 文字列で指定された入力には 796 文字があり、796 文字がバランスの取れた括弧形式になる可能性のあるすべての方法を見つける必要があります。

2. '(' で始まり ')' で終わる必要があるため、各ケースに 2 つの括弧が必要です。したがって、「()()(xc)(cvs)」となる可能性があります。したがって、バランスをとる必要があるため、数学的計算には 1 文字あたり 2*(何か) が含まれる必要があることを意味します。

3. charすべてのケースを再帰的に見つけるには、remainder(%) 演算子を使用する必要がありますが、aではなく?を使用する場合はどうすればよいintですか?

私が知らないこと：

1. 各ケースをどのように分析しますか? 入力を計算するための単純な式がなければ、長い時間や大量のコードが必要になることはありませんか?

2. 多くのifステートメントまたは再帰が必要ですか?

質問：

Σ = {), (} とする. L ⊆ Σ* を適切にバランスの取れた括弧の文字列の集合とする. たとえば (())() は L にあり、(()))( は L にはない. L は次のように再帰的に定義されます。

ε ∈ L

文字列 x ≠ ε は、x が (y)z の形式である場合にのみ L に含まれます。ここで、y と z は L に含まれます。

n は、0 から 999 までの特定の 3 桁の数字です。

f(n) mod 997 を計算する

役に立つかもしれないいくつかの事実: n1、n2 が N(自然数) のメンバーである場合、

(n1 x n2) mod 997 および (n1 + n2) mod 997

n = 796 (これは私に固有のもので、この場合はこれが指定された入力になります)

したがって、「f(796) mod 997 = ?」を計算する必要があります。プログラムを使用して。この場合、この質問には単純に Java を使用します。

コード：

次の問題のバックトラッキングソリューションで生成された結果の数である誰かが私に答えることができるかどうか疑問に思っていました:

n 対の括弧が与えられた場合、整形式の括弧のすべての組み合わせを生成する関数を作成します。

たとえば、n = 3 の場合、解セットは次のようになります。

"((()))"、"(()())"、"(())()"、"()(())"、"()()()"

stackoverflow に関連する投稿があります: Java でバランスの取れた括弧を生成する

有効な括弧の数を計算する前に生成できる数式があるかどうかは疑問です。例:
- f(n):
- f(1) = 1
- f(2) = 2
- f(3) = 5
など。

ありがとうございました。

n 個の括弧シーケンスは、n 個の "("s および n ")" で構成されます。

有効な括弧のシーケンスは、次のように定義されています。

隣接する括弧「()」が空になるまで消去を繰り返す方法を見つけることができます。

たとえば、「(())」は有効な括弧です。2 番目と 3 番目の位置のペアを消去して「()」にしてから、空にすることができます。")()(" は有効な括弧ではありません。2 番目と 3 番目の位置のペアを消去すると、")(" になり、それ以上消去できなくなります。

これで、有効な n 個の括弧のシーケンスがすべて揃いました。辞書順で k 番目に小さいシーケンスを見つけます。

たとえば、次のすべての有効な 3 つの括弧のシーケンスを辞書順で示します。

ソース: https://code.google.com/codejam/contest/4214486/dashboard#s=p3

注: コンテストは現在終了しており、ソリューションをダウンロードできます。

C++ STL で利用可能な next_permutation() を使用して、小さい入力 ( k < 10 ^{6 ) について解決しました。}このためのサブ問題を定式化することはできません。カタロニア語の番号を使用してこれを解決しようとしましたが、成功していないようです。学習に役立たないので、解決策を見たくありません。サブの問題を特定するのを手伝ってください。

次の関数は、カタロニア語の n 番目の数字を生成します。この関数の正確な時間複雑度関数は何ですか、または自分でそれを見つけるにはどうすればよいですか?

注: これがカタロニア語の数値を計算する最悪の方法であることはわかっています。

次のデータ型定義があるとします。

ノードの量などの長さでソートされたすべての可能なツリーを含む無限リストを生成する関数を書きたいと思います。

次のコードは、必要なことをほぼ実行しますが、毎回追加のノードを挿入して右側のツリーを下るだけですが、両側を交互に切り替える必要があります。

実行中

与えます：

しかし、それは次のようなものでなければなりません:

平衡二分木と不平衡二分木を扱う。

私はカタロニア語の関数を見ていますが、高さh未満の木を数えている可能性があると思うので、どこにも有益ではありません。たとえば、高さが2の場合、高さ1もカウントされます（おそらく高さ0も）と思います。

私はPythonに完全に慣れておらず、そのことについてプログラミングするのは初めてであり、最大1兆までのすべてのカタロニア語の数字を出力するプログラムを作成する必要があることを前置きさせてください。プログラムの基本は書いてありますが、なぜ正しい数値が得られないのか理解できないようです。また、トレンドをグラフ化しようとすると、プログラムに遭遇します。事前に感謝します。ここに私が持っているコードがあります:

私はPythonが初めてです。これは宿題ですが、Java の経験が少ないので大変です。コードは、再帰的な定義を使用して最初のカタロニア語番号を出力することになっています。

編集：

私の現在のコードは次のようになります。残っている唯一の問題は、このコードで取得したすべての C(n) 番号を savetxt() メソッドを使用して txt に入れることです。

この最後の問題が解決されたら、回答で提案されている他のバージョンをいくつか試します（最初にゼロの配列を埋めるなど）。

これは、Cracking the Coding Interview (^第5版)の問題 9.6 です。

括弧の n 対のすべての有効な組み合わせを出力するアルゴリズムを実装します 。
例
入力: 3
出力:"((())), (()()), (())(), ()(()), ( )()()"

これが私が実装したアルゴリズムです（Javaで）

これにより、正しい出力が生成されます。インタビュアー (少なくとも Amazon) は、ソリューションの時間と空間の複雑さを質問するのが大好きです。時間の複雑さについては、アルゴリズムがO(n)で実行され、再帰関係があることを示すことができました。スペースの複雑さの分析に問題があります。これは再帰的なソリューションなので、少なくともO(n)である必要がありますが、再帰呼び出しごとに、n で区切られたセットも生成しています。n 回の再帰呼び出しのために総スペースはO(n)になりますか、それとも再帰呼び出し n ごとにバインドされた n のサイズが設定されているため、O(n ² )になりますか?