algorithm - 最小要素を見つけるための再帰アルゴリズム

Question

最小要素を見つけるための再帰アルゴリズムを書きたいと思います。葉が要素を表し、内部ノードが比較後の最小要素である二分木を描画します。

アルゴリズムへの入力は次のとおりです。

5 3 1 9 8 7 6 10

二分木 :

出力: 1

この二分木を何とか組み込んだアルゴリズムを見つける必要があります。最初に要素のペアを比較し、問題を n/2 に縮小し、次に n/4 .. に縮小し、n が 1 になると答えが得られます。

Answer 1

ツリー内の最小値を見つける関数は次のとおりです。

function smallest(tree)
    if isEmpty(tree)
        return infinity
    return min( tree.value,
                smallest(tree.leftKid),
                smallest(tree.rightKid) )

しかし、私はあなたの質問を理解していません。入力が配列の形式の場合、ツリーを構築する必要はありません。ペアごとに値を比較しながら配列をウォークスルーし、各ステップで最小値を維持し、最後に最小値を出力します。

Answer 2

分割統治を使用します。

「部分配列」の最小M(i, j)要素を とし[i...j]ます。次にM(i, j) = min(M(i, k), M(k + 1, j))、もしi < j（適切な を見つけるのはあなたに任せますk）。

さらに、ケースの世話をする必要がありますi = j。

Answer 3

擬似コード:

mydata = [5 3 1 9 8 7 6 10];
n = 8;
while n > 1
  for ii = 2 to n Step 2
    mydata[ii/2]=min(mydata[ii-1],mydata[ii]);
  next ii
  n = n/2;
wend