東京工業大学 情報理工学院 数理・計算科学系 2018年8月実施 午前 問C

Author

祭音Myyura

Description

配列 d[0], d[1], ... , d[n−1] には n 個の相異なる整数が昇順で入っているとする． 探索アルゴリズムを記述した次の擬似コードを BinSearch と呼ぶ．

def search(k, a, b)         # a ≦ i ≦ b かつ d[i] = k となる i を返す.
                            # そのような i が無い場合は -1 を返す.
    i := a + ((b - a) / 2)  # ☆
    if (d[i] == k)
        return i
    else if ((k < d[i]) && (a < i))
        return search(k, a, i-1)
    else if ((d[i] < k) && (i < b))
        return search(k, i+1, b)
    else
        return -1
    end
end

ただし ☆ の行中の / は切り捨てで商を求める演算である． 与えられた整数 k に対して search(k,0,n−1) を実行すると，d[i] = k となる i が存在する場合はその i が返され，存在しない場合は −1 が返される． search(k,0,n−1) の計算の中で ☆ の行が実行される総回数（つまり search が呼び出される総回数）を steps(k, n) と表記する． たとえば配列 d が {30,50} のとき steps(30, 2) = 1 であり（なぜなら search(30,0,1) だけが呼び出される）steps(40, 2) = 2 である（なぜなら search(40,0,1) と search(40,1,1) が呼び出される）． max_steps(n) = (steps(k, n)) と定義する． これはこのアルゴリズムで n 個の要素の中から探索をする際の最悪ステップ数である． max_steps(n) の値は n にだけ依存して d[0], d[1], ... , d[n−1] の値には依存しない．

(1) max_steps(15) の値を書け．

(2) ☆ の行の代入文を

i := a + ((b - a) / 1)

（これは i := b に等しい）に変更した擬似コードを UniSearch と呼ぶ．UniSearch における max_steps(10) の値を書け． さらに配列 d が {0,2,4,6,8,10,12,14,16,18} のとき，steps(k, 10) = max_steps(10) となる k の値をひとつ書け．

(3) ☆ の行の代入文を

i := a + ((b - a) / 10)

に変更した擬似コードを DecSearch と呼ぶ． DecSearch における max_steps(10) の値を書け． さらに配列 d が上記と同じとき，steps(k, 10) = max_steps(10) となる k の値をひとつ書け．

(4) ３つの関数 bin, uni, dec を次のように定義する．

• bin(n) = BinSearch における max_steps(n).
• uni(n) = UniSearch における max_steps(n).
• dec(n) = DecSearch における max_steps(n).

これらそれぞれの関数をオーダー記法 で表せ．さらにそれを求めた根拠を簡潔に説明せよ．

(5) 次の に入る正しい語句を「よりも真に大きい」「よりも真に小さい」「と等しい」の中からそれぞれ選べ。

• bin(n) のオーダーは uni(n) のオーダー .
• bin(n) のオーダーは dec(n) のオーダー .
• uni(n) のオーダーは dec(n) のオーダー .

Kai

(1)

• max_steps(15) = 4

(2)

最悪の場合、要素を大きい順に1つ残らず調べる。

• max_steps(10) = 10
• k = 0

(3)

なので、 となる。

よって、(2) と同じに、最悪の場合、要素を小さい順に1つ残らず調べる。

• max_steps(10) = 10
• k = 18

(4)

(5)

• bin(n) のオーダーは uni(n) のオーダー よりも真に小さい.
• bin(n) のオーダーは dec(n) のオーダー と等しい.
• uni(n) のオーダーは dec(n) のオーダー よりも真に大きい.