問題タブ [catalan]

2n長さnが約の 2 進数を考えるとしましょう1000。次のプロパティを持つkth数値 (k は によって制限されます) を探しています。10^9

• の金額は、次のように記述できる1's金額と同じです。0's#(1) = #(0)
• この番号のすべてのプレフィックスには、0's少なくとも1's. 次の文を否定した後の方が理解しやすいかもしれませ1'sん0's。

そして、基本的にはそれだけです。明確にするために、いくつかの例 n=2をk=2 見てみましょう2n:

そして、2ndこれら 2 つの要件を満たす数を見つけなければなりません。つまり0011、 が最初のもので、0101が 2 番目のものです。を変更するk=3と、反対のビットの量が同じ数があるため、答えは存在しませんが、 の場合、0110接頭辞があるため、数値は 2 番目の制約を満たさず、最上位ビット011がすべての数値と同じになります。1

では、アルゴリズムを見つけるためにこれまでに何をしたのでしょうか。

私の最初のアイデアは、可能なすべてのビット設定を生成し、それらの 2 つのプロパティがあるかどうかを確認することでしたが、それらをすべて生成するとO(2^(2n))、n=1000.

0011さらに、 for n=2、000111forなどよりも小さいすべての数値をチェックする必要がないことを認識していn=3ます...率直に言って、最上位ビットの半分が「そのまま」残っているものは、これらの数値が#(1) = #(0)条件を満たす可能性がないためです。それを使えばn半分に減らせますが、あまり役に立ちません。2 * forever の代わりに、アルゴリズムを永久に実行しています。それはまだO(2^n)複雑で、大きすぎます。

アルゴリズムのアイデアはありますか？

結論

このテキストは、Andy Jones の投稿を読んだ後の私の考えの結果として作成されました。

まず第一に、Andy の投稿Kasa 2009の次のドキュメントのポイント 6 であるため、使用したコードは投稿しません。あなたがしなければならないのはnr、私が説明したことをそれと見なすことだけkです。Dyck words アルゴリズムのランクを解除すると、答えをより迅速に見つけることができます。ただし、1 つのボトルネックがあります。

それを考慮するとn <= 1000、カタロニア語の数は非常に巨大になる可能性がありC(999,999)ます。いくつかの大きな数の演算を使用できますが、一方で、それを超えて標準の整数を使用するためのちょっとしたトリックを思い付きました。

よりも大きい限り、カタロニア語の数が実際にどのくらい大きいかを知りたくありませんk。そこで、部分和をn x nテーブルにキャッシュするカタロニア語の数字を作成します。

それを生成するのは非常に簡単です:

したがって、これだけを見ることができます：

オーバーフローを引き起こす可能性があります。

この時点で停止し、定義を提供しましょう。

k-flow- 整数の実際のオーバーフローではなく、 の値C(x,y)が より大きいという情報ですk。

私の考えは、上記の式を実行するたびに がC(x,y)よりも大きいkか、合計コンポーネントのいずれかが であるかどうかを確認することです-1。-1マーカーとして機能する代わりに配置した場合、それk-flowは起こりました。k-flow数値が任意の正の数値で合計される場合k-flowed、特に 2 つのk-flowed数値の合計が であることは明らかだと思いk-flowedます。

最後に証明しなければならないことは、実際のオーバーフローが発生する可能性がないことです。a + b実際のオーバーフローは、それらのどれではないかを合計した場合にのみ発生する可能性がありますk-flowedが、合計すると、実際のオーバーフローが発生しました。

もちろん、最大値はa + b <= 2 * k <= 2*10^9 <= 2,147,483,647、この不等式の最後の値が符号付きの int の値であると記述できるため、不可能です。また、私の場合のように、int は 32 ビットであると仮定します。

カタロニア語数は再帰を満たします

もちろん、カタロニア語の数には、二項係数を含む閉じた形式の式があります。また、C_{n-1} だけで C_n を表すこともできます。私が疑問に思っているのは、SML や Haskell などの関数型言語でこの種の畳み込みをどのように実装できるかということです。

http://www.cstutoringcenter.com/problems/problems.php?id=103

クリックしたくない人のために説明すると、基本的に飛び石「-」と兵士「#」があり、兵士は右にしか移動できないと書かれています。兵士が別の兵士の後ろにいる場合、その兵士が先に動くのを待たなければなりません。終了条件は全兵士が終了した時。

2 人の兵士が 5 つの飛び石を移動できる回数。

私は幅優先検索を使用しています.5つの石では数秒以内に実行されますが、10の石では数時間かかり、時間は深さとともに指数関数的に増加します. どうすればこれに対処できますか？

私のコード:

States.java

兵士.java

TestSoldiers.java

終了する方法の総数 (TestSoldiers.java のカウント) の整合性を維持しながら、各状態を 1 回だけ考慮するようにするにはどうすればよいですか?

パラメータを変更したい場合は、新しい State(n,k) です。ここで、n は石の数、k は兵士の数です。

N番目のカタロニア数を計算するコードを書きました。ただし、N=20 以降では正しい結果が返されません。ただし、N<20 の場合の結果は正しいので、何が間違っているのかわかりません。

したがって、N=20 の場合、6564120420 が返されるはずですが、2269153124 が返されます。

誰かが私を正しい方向に向けることができますか?