問題タブ [clrs]

CLRS を研究していて、シャッフル アルゴリズムに問題があることがわかりました。これは均一にランダムな順列を生成しますか?

私の主張: いいえ、そうではありません。なぜなら、4 行目により、n^n 通りの順列が可能になるからです。そして、n で割り切れないのです! これは、異なる順列の数です。

私の推論が正しいか確認していただけますか？

このソリューションの問題の決定木の例はありますか。

質問に応じて決定木を描きたいと思います（ほとんどの人が理解できるように）。しかし、この決定木の描き方がわかりません。例として、このアルゴリズムの表現に葉が使用されているかわかりません

質問2

n 個の赤と n 個の青の水差しが与えられたとします。すべて形状とサイズが異なります。青い水差しと同様に、赤い水差しはすべて異なる量の水を保持します。さらに、すべての赤いジャグには、同じ量の水が入る青いジャグがあり、その逆も同様です。

あなたの仕事は、同じ量の水を保持する赤と青の水差しのペアに水差しのグループを見つけることです. これを行うには、次の操作を実行できます。1 つは赤でもう 1 つは青の水差しのペアを選び、赤の水差しに水を入れてから、水を青の水差しに注ぎます。この操作により、赤または青のジャグがより多くの水を保持できるかどうか、または同じ容量であるかがわかります。このような比較には 1 時間単位かかると仮定します。あなたの目標は、グループ化を決定するための最小数の比較を行うアルゴリズムを見つけることです。2 つの赤い水差しや 2 つの青い水差しを直接比較しないでください。

1. Θ(n2) 比較を使用して水差しをペアにグループ化する決定論的アルゴリズムを説明してください。2. この問題を解くアルゴリズムが行う必要のある比較回数の Ω(nlgn) の下限を証明してください。

この問題を解決するには、一致を判断するのに十分な情報が得られるまで、アルゴリズムで一連の比較を実行する必要があります。決定木の観点からアルゴリズムの計算を見ることができます。すべての内部ノードには、比較する 2 つのジャグ (1 つは赤、もう 1 つは青) のラベルが付けられており、3 つの発信エッジ (赤のジャグは小さい、同じサイズ、または青いジャグよりも大きい) があります。葉は水差しのユニークなマッチングでラベル付けされています。第 8 章の解決策: 線形時間での並べ替え 8-17 決定木の高さは、一致を判断するためにアルゴリズムが行わなければならない最悪の場合の比較回数に等しくなります。そのサイズを制限するために、最初に n 個の赤と n 個の青の水差しの可能な一致の数を計算しましょう。比較を開始する前に、赤色の水差しに 1 から n までのラベルを付け、青色の水差しにも 1 から n までのラベルを付けると、アルゴリズムのすべての結果は、セット {(i,π(i)) : 1 ≤ i ≤ n として表すことができ、π は {1,..., n}} の順列であり、赤い水差しのペアが含まれています。 (第 1 コンポーネント) と青い水差し (第 2 コンポーネント) が一致します。すべての順列 π は異なる結果に対応するため、正確に n! 異なる結果。これで、決定木の高さ h を制限できます。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。これには、一致する赤の水差し (最初のコンポーネント) と青の水差し (2 番目のコンポーネント) のペアが含まれています。すべての順列 π は異なる結果に対応するため、正確に n! 異なる結果。これで、決定木の高さ h を制限できます。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。これには、一致する赤の水差し (最初のコンポーネント) と青の水差し (2 番目のコンポーネント) のペアが含まれています。すべての順列 π は異なる結果に対応するため、正確に n! 異なる結果。これで、決定木の高さ h を制限できます。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。分岐係数が 3 のすべてのツリー (すべての内部ノードに最大で 3 つの子がある) は、最大で 3 時間の葉を持ちます。決定木には少なくとも n! 子供の場合、3h ≥ n となります。≥ (n/e) n ⇒ h ≥ n log3 n − n log3 e = (n lg n) . したがって、問題を解決するアルゴリズムは (n lg n) 比較を使用する必要があります。

CLRSに従ってCでヒープソートアルゴリズムを実装していました。ただし、ソートされた出力を取得できません。見て、私のコードの何が問題なのか教えてください。機能maxheapとbuildmaxheap働き。コードの何が問題なのかわかりません。

コードは、配列要素をヒープソートすることになっています。heapsort()関数にエラーがあると感じ、正常maxheapにbuildmaxheap動作します。

私が得ている最終的な出力は

しかし、期待される出力は

コード：

CLRS は、i が p と r の間の確率変数である場合に交換A[r]するように指示します。A[i]ただし、クイックソート関数のピボットとして変数をランダムに選択し、値を交換した場合、時間の複雑さはどうなりますか?

アルゴリズムのパフォーマンスは、本に記載されているものよりも悪くなりますか?

ここにコードがあります

したがって、問題は次のとおりです。「2つのn要素配列AおよびBに格納されている2つのnビット2進整数を加算する問題を考えてみてください。2つの整数の合計は、(n+1)要素にバイナリ形式で格納する必要があります。配列 C. 問題を正式に記述し、2 つの整数を加算するための疑似コードを記述してください。」

この問題に対する私のpythonコードは次のとおりです。

また、計算を行った後に逆にすることができる左側の最下位桁を取得しました。

何が間違っているのかわかりません助けてください！

CLRS から有限オートマトンとの文字列マッチングを学んでいます。いくつかの演習問題を解いています。演習問題 32.3-1 については、

パターン P = aabab の文字列照合オートマトンを構築し、テキスト文字列 T = aaababaabaababaab に対するその操作を示します。

以下は私の遷移関数です。

私の遷移関数は正しいですか? そして、最後の行を埋めるにはどうすればよいですか? どんな助けでも

セグメント化されたツリーの遅延伝播アルゴリズムには、私には不明な点があります。以下のコードによると、クエリ間隔が完全にオーバーラップすると、更新値が親ノードに追加され、子は遅延更新用にマークされます。しかし、添付の画像でわかるように、範囲 0,1 に対して +4 の更新が行われると、結果は両方のツリーでまったく異なります! (左の画像: 遅延伝播なし)。

問題は、0,1 からの合計を求めるクエリが +4 更新後に呼び出された場合はどうなるかということです。