1

次のアルゴリズムを検討してください

ALGORITHM Find(A[0..n‐1])
    if n ==1 return A[0]
    else temp = Find(A[0..n‐2])
    if temp ≤ A[n‐1] return temp
    else return A[n‐1]

a. What does this algorithm compute?
b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.

このアルゴリズムは A[0]、A[0..3]、A[0..5]、A[0.7]、A[0..8] を返しますか? n=9 の場合は? 私は正しい軌道に乗っていますか？

どなたか譲っていただけると助かります！ありがとう！

4

1 に答える 1

1

このアルゴリズムは、指定された配列または要素のリストの最小値を再帰的に計算します。

のすべての値に対してn。先行するすべての値の最小値を計算しますn(つまり、<= n - 1)。返された値が より小さい場合はvalue[n]、その値を返します。それ以外の場合は、 を返しますvalue[n]。

要素が 1 つしかない場合、基本ケースは自明です。その値を最小値として返します。

于 2013-09-07T17:57:23.157 に答える