2

配列 a[1..n] のある順序付けられた型 (つまり、x < y は常に定義されています) の要素の配列で、「分割統治」アルゴリズムを使用して配列内の最小値を見つけたいと考えています。

任務の本当の意味とは？

4

6 に答える 6

6

分割統治法は、問題をより小さな部分に分割し、各部分で問題を解決し、結果を組み合わせて全体的な答えを形成することにより、問題を解決するアルゴリズム手法です。問題が十分に単純になると、直接解決できます。

この場合、配列を半分に分割するとどうなるかを考えてみてください。それぞれの半分の最小値がわかれば、全体の最小値がわかりますか? また、配列に要素が 1 つしか残っていない場合、配列の最小値はいくつになるでしょうか? この質問に答えれば、問題に対する再帰的な分割統治アルゴリズムを直接思いつくことができます。

お役に立てれば！

于 2012-04-20T20:03:33.273 に答える
1

分割統治戦略は、次の方法で問題を解決します。

  1. それ自体が同じタイプの問題のより小さなインスタンスであるサブ問題に分割する

  2. これらの部分問題を再帰的に解く

  3. 回答を適切に組み合わせる

良い例はマージソートです！

http://en.wikipedia.org/wiki/Merge_sort

于 2012-04-20T20:04:56.303 に答える
0

http://ankzcode.blogspot.in/2012/11/find-minimum-without-linear-search.html

リンクのコードは同じものを実装しています。

于 2012-11-12T08:11:51.267 に答える
0

  1. 配列の内容がランダムな場合、探している要素が見つかるまで各要素を検索する必要があります。配列が長いほど、検索時間が長くなります。これを「線形探索」と呼びます。

  2. 配列の内容がすでに何らかの順序になっている場合は、この順序を利用して検索を最適化できます (検索時間を短縮できます)。たとえば、電話帳の名前はアルファベット順に並べ替えられます。真ん中の電話帳を開くことができます。探している名前が真ん中の名前よりも「下」の場合は、本の左側で検索を続けます。高い場合は、右半分を検索します。これは「二分探索」または「分割統治」と呼ばれます。

  3. 特定の検索アルゴリズムがどの程度効率的か非効率的かを定量化することは可能です。これは " Asymptotic " または " Big O-Notation " と呼ばれます:

    
    クラス検索アルゴリズム
    ----- ----------------
    データ構造 配列
    最悪の場合のパフォーマンス O(log n)
    最良のケースのパフォーマンス O(1)
    平均ケース パフォーマンス O(log n)
    最悪の場合の空間複雑度 O(1)
于 2012-04-20T20:04:20.863 に答える
0

一般に、「分割統治」とは、問題をより小さな (多くの場合、より単純な) 問題に分割し、それぞれを個別に解決してから、何らかの方法で解決策を組み合わせるという意味です。

特定の例では、配列を何らかの方法で小さな配列に分割し（たとえば、半分に分割する）、小さな配列ごとに最小値を見つけてから、これらのサブ問題の最小のソリューションをソリューションとして選択する必要があります全体的な問題。各サブ問題は、同じ分割統治アプローチを使用して解決できます。限定的なケースは、問題を直接解決できる十分に小さいサイズ (たとえば、1 または 2) の配列です。

于 2012-04-20T20:05:04.360 に答える
0

U は、次のアルゴリズムを使用できます。

getSmallest(int a[])
{
  int n=a.length;
  if(n==1)
    return a[0];
  else
   {
        x=remove first element from a;
        create another array b with a size smaller by 1 than array a
        if(x<getSmallest(b))
            return x;
        else
           return the smallest returned by the recursive call 
   }
}
于 2012-09-17T05:10:04.280 に答える