0

私たちはデータ構造のクラスで分割統治アルゴリズムを使い始めていますが、何をすべきかを完全に理解するのに苦労しています。以下は、基本的に配列を合計するプログラムを作成するように求めていますが、基数が 4 になるまで分割して征服する必要があります。チャンクを一緒に。どこから始めればよいかさえわかりません。少しだけ説明と理解が必要です。先生はあまり役に立ちませんでした。配列には、1000 未満の 2 のべき乗の数の行が含まれています。

問題 n 個の整数の配列を合計するための分割統治アルゴリズムを書きなさい。このアルゴリズムの基本ケースは、副問題のサイズが 4 以下の場合です。この場合、反復ループを使用して副問題の整数を合計します。次のことを行う必要があります。

4

2 に答える 2

3

プログラミング言語については少し考えずに、抽象的にどのようなアプローチになるかを考えてみましょう。


20スタックの紙があり、それぞれに1つの番号が付いている部屋にいると想像してみてください。あなたはすべての数字の合計をまとめる作業を喜んで行いますが、1つずつ進むには永遠に時間がかかることに気づきます。だから、あなたは友達を呼んで、あなたはそれぞれ10スタックをお互いに手に入れて作業します。友達に電話することであなたがしなければならなかった仕事の量は半分に減りました。

あなたは両方とも、10スタックの紙ではどこにも行かないことに気付いているので、それぞれが別の友人に手を貸してもらい、4人全員に5スタックずつ残します。リーズナブルですが、それでも圧倒的です。そのため、もう一度、全員が別の友達に電話をかけ、他の友達とスタックを半分にします。つまり、番号が記載された2.5スタックの紙を全員に残します。

これは一人で行うのに妥当な量の作業であることに皆さんは同意しているので、数字を足し合わせて作業することができます。あなた自身にやって来た最後の人々のセットから作業して、あなたが他のみんなの合計を得るまで、そしてあなたがあなた自身のものを持っているまで、誰もが彼らが持っていた数の合計を返します。これら2つを合計して、結果に到達します。

これが分割統治の原則です。作業スタックは作業の一部に分割され、その後、他のメソッドを呼び出して実行します。

これがPythonでの疑似例です。

def sum(*args):
    if len(args) == 0:  # Nothing in my list, so I'm done
        return 0
    elif len(args) == 1:  # One thing in my list, return that
        return args[0]
    else:  # Too much for me to handle; call in the Calvary!
        return args[0] + sum(args[1:])
于 2013-02-18T04:38:42.780 に答える
3

配列 A をそれぞれ配列の半分の 2 つ (またはそれ以上) のサブ配列に分割し、結果の配列をそれ自体に渡して、配列がサイズ 4 になるまで分割を続ける再帰的なメソッドを作成するつもりだと思います。次に、合計を実行して、それらの 4 つのユニットの合計を返すことができます。

于 2013-02-18T04:30:42.540 に答える