問題タブ [divide-and-conquer]

私はデータ構造とアルゴリズムを学んでいます。私が参照している本 (Sedgwick) では、分割統治戦略を説明するために「最大要素の検索」を使用しています。このアルゴリズムは、配列を途中で 2 つの部分に分割し、2 つの部分の最大要素を (再帰的に) 見つけ、2 つのうち大きい方を配列全体の最大要素として返します。

以下は、尋ねられた演習問題です

配列内の最大要素を見つけるための分割統治プログラム (プログラム 5.6) を変更して、サイズ N の配列をサイズ k = 2^(lg N – 1) の一部とサイズ N – k の別の部分に分割します。 (パーツの少なくとも 1 つのサイズが 2 のべき乗になるように)。

プログラム 5.6 で示したものと同様に、配列サイズが 11 のときにプログラムが行う再帰呼び出しに対応するツリーを描画します。

最初の部分集合のサイズが 2 のべき乗であるため、このような二分木の左部分木は完全な二分木であることがわかります。著者が私がこれから得るべきであることを望んでいる含意は何ですか?

配列を2つのサブ配列に最適に分割して、両方のサブ配列の要素の合計が同じになるようにするにはどうすればよいですか。そうでない場合、エラーが発生します。

例1

与えられた配列

それは次のように分けることができます

と

各サブアレイの合計は最大105です。

例2

配列を等しい合計の2つの配列に分割することはできません。

宿題として、O（n）未満で機能する分割統治法を使用して、1000桁の数値に整数乗算を実装する必要があります。どのアルゴリズムを調べる必要がありますか？

宿題として、大きな整数のべき乗のための分割統治アプローチを実装する必要があります。カラツバの乗算アルゴリズムを知っていますが、両方とも大きな整数であるx ^ yの結果を取得するために、どの分割統治アルゴリズムを適用できますか？

集合Mが与えられた場合、両方ともMに属する数のペア（a、b）があるかどうかを調べ、a + b = xです。ここで、xは以前に指定されたパラメーターです。この問題は、分割統治をO（n * log n）で使用して解決する必要があります。おそらく、問題を2つの半分のサイズのサブ問題に分割してから、結果をO（n）で再結合する必要があります。

与えられた問題の擬似コードまたはそれを解決するためのヒントが欲しいのですが。

多項式の再帰的および非再帰的な分割統治アルゴリズムを探しています。a[0..n-1] を実数配列とし、n は 2 のべき乗です。P(x)=a[0]+a[1]x+a[2]x^2+... を計算します。任意の x に対して +a[n-1]x^n-1。

最初に疑似 C++ コードで私の状況を述べさせてください。

ここで、concat は返されたベクトルを連結します。基本的に、保存された 2 つの関数値の間にわずかな違いしかないような方法で関数をサンプリングしています。

すべての再帰ステップでかなりの量のメモリ割り当て (2 つのサブベクトルを割り当ててから、それらと別の要素を連結) があるように見えるため、上記の方法には満足できません。そのコードは、パフォーマンスに関して重要なアルゴリズムの一部で実行する必要があります。upper - lowerかなり小さい場合は、評価にfそれほど時間はかかりません。

だから私の質問：

• すべての再帰呼び出しで同じデータ構造を使用し、そのベクトルの現在の部分を埋めるだけの巧妙な方法を見つけましたか? (必要な関数評価の数は前もってわからないことに注意してください)。これについての考え：

  • ベクトルの代わりにリストを使用します。しかし、ダブルを格納するだけでは、メモリのオーバーホールは十分ではないと感じています。
  • ベクトルの穴を保持し、どのエントリが埋められるかを示す別のベクトルを維持します。subsample再帰呼び出しの最後で、と の間に穴がないようにエントリをシフトしますnewval。しかし今、2番目のベクトルの追加作業でシフトすることでコピーを切り替えます-おそらく悪い考えです。

• 再帰を完全に取り除く方法はありますか? ただし、正確さのために、上記の分割統治パターンを使用することが重要です。この関数fは上限と下限を多用し、これによってかなりのパフォーマンスが得られます。

ご感想ありがとうございます。

Space_C0wb0y の要求に従って、私の問題を言い換えてみます。おそらく最初の説明はあまり明確ではありませんでした。

特定の間隔でサンプリングする（たとえば、特定のポイントで評価する）関数（数学的な意味で）があります。

間隔が [0,100] であるとします。f(0)=0関数の値が 0と100 であることはわかっていますf(100) = 40。ここで、間隔の中間点である 50 で関数を評価します。たとえば、関数が を返しますf(50)=10。としてf(0)-f(50) <= 10、間隔 [0,50] にこれ以上のサンプルは必要ありません。ただし、間隔 [50,100] についてはさらに計算が必要です。したがって、次の (再帰的な) ステップで を評価しf(75)ます。上記のロジックを再帰的に繰り返します。

最後に、次のような対応するパラメーターを持つ関数値を提供する (2 つの) ベクトルを使用したいと思います。

これらのベクトルを再帰的に構築するための最良の（最もパフォーマンスの高い）アプローチを探しています。

これが物事を明確にすることを願っています。

クライアントからサーバーにUNIXコマンドを送信しようとしている場合は、サーバーがそれを実行するのを待ってから、結果をクライアントに返します。

iveは接続を機能させることができましたが、続行する方法がわかりません。これは私が進むべき方向でさえありますか？

感謝します、ty bando

カンファレンス ワークショップで新しい JDK7 Fork/Join Framework を紹介したいと考えています。このために、私たちは現在、フレームワークで何ができるかという興味深い例を探しています。

並べ替えや行列計算のような明白なものがありますが、人々が取り組みたいと思うもっと興味深いものはありますか? たとえば、Java サイトで画像のぼやけを見つけたり、天気予報などを見つけたりしましたか?

問題を数日で解決できるように、ドメインが複雑すぎないのがよいでしょう。

どんな入力でも大歓迎です。アイデアや経験はありますか？

整数の特定の入力配列に対して、値が重複する可能性のある、空ではない連続したサブ配列を見つけたいと思います。分割統治法を試して、配列の最大連続サブ配列を見つけました。これにより、期待どおりに異なる結果が返されます。以下のコードを見つけてください。

このコードは、結果を2000005400として返します。非再帰バージョンのMCSは、異なる結果、つまり2000010721とその{1-94}からの結果を返します。理由がわかりません。コードにバグがある場合はお知らせください。