跳到主要内容

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

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

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) = max⁡k∈Z\max_{k \in Z}(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).

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

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

  • bin(n) のオーダーは uni(n) のオーダー A\boxed{A}.
  • bin(n) のオーダーは dec(n) のオーダー B\boxed{B}.
  • uni(n) のオーダーは dec(n) のオーダー C\boxed{C}.

题目描述​

数组 d[0], d[1], ..., d[n-1] 中存放 nn 个互不相同并按升序排列的整数。把下列搜索伪代码称为 BinSearch：

def search(k, a, b)         # 返回满足 a ≤ i ≤ b 且 d[i] = k 的 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

星号行中的 / 表示商向下取整。对给定整数 kk 执行 search(k,0,n-1)：若存在 d[i] = k 则返回该 ii，否则返回 −1-1。令 steps⁡(k,n)\operatorname{steps}(k,n) 表示此次计算中星号行执行的总次数，也就是 search 的总调用次数。例如，当数组为 {30,50} 时，

steps⁡(30,2)=1,steps⁡(40,2)=2.\operatorname{steps}(30,2)=1,\qquad \operatorname{steps}(40,2)=2.

定义

max_steps⁡(n)=max⁡k∈Zsteps⁡(k,n).\operatorname{max\_steps}(n) =\max_{k\in\mathbb Z}\operatorname{steps}(k,n).

它是搜索 nn 个元素时的最坏步数，只依赖于 nn，与数组内具体整数无关。

  1. 求 BinSearch 的 max_steps⁡(15)\operatorname{max\_steps}(15)。

  2. 把星号行改为

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

    即 i := b，所得算法称为 UniSearch。求其 max_steps⁡(10)\operatorname{max\_steps}(10)。进一步，当数组为 {0,2,4,6,8,10,12,14,16,18} 时，给出一个满足 steps⁡(k,10)=max_steps⁡(10)\operatorname{steps}(k,10)=\operatorname{max\_steps}(10) 的整数 kk。

  3. 把星号行改为

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

    所得算法称为 DecSearch。求其 max_steps⁡(10)\operatorname{max\_steps}(10)；对第 2 问的同一数组，再给出一个达到该最坏步数的整数 kk。

  4. 定义

    • bin⁡(n)\operatorname{bin}(n)：BinSearch 的 max_steps⁡(n)\operatorname{max\_steps}(n)；
    • uni⁡(n)\operatorname{uni}(n)：UniSearch 的 max_steps⁡(n)\operatorname{max\_steps}(n)；
    • dec⁡(n)\operatorname{dec}(n)：DecSearch 的 max_steps⁡(n)\operatorname{max\_steps}(n)。

    分别用 O(⋅)O(\cdot) 表示三者的增长阶，并简要说明依据。

  5. 从“严格大于”“严格小于”“等于”中分别选择正确短语填入：

    • bin⁡(n)\operatorname{bin}(n) 的阶 A\boxed A uni⁡(n)\operatorname{uni}(n) 的阶；
    • bin⁡(n)\operatorname{bin}(n) 的阶 B\boxed B dec⁡(n)\operatorname{dec}(n) 的阶；
    • uni⁡(n)\operatorname{uni}(n) 的阶 C\boxed C dec⁡(n)\operatorname{dec}(n) 的阶。

Kai​

(1)​

15→7→3→115\to7\to3\to1 と探索区間が縮むので、max_steps⁡(15)=4\boxed{\operatorname{max\_steps}(15)=4}。

(2)​

毎回最大の要素を調べるので、max_steps⁡(10)=10\boxed{\operatorname{max\_steps}(10)=10}。例えば k=0\boxed{k=0} とすれば 18,16,…,018,16,\ldots,0 の順に全要素を調べる。

(3)​

区間長が 1010 以下なら ⌊(b−a)/10⌋=0\lfloor(b-a)/10\rfloor=0、すなわち i=ai=a である。したがって、max_steps⁡(10)=10\boxed{\operatorname{max\_steps}(10)=10}。例えば k=18\boxed{k=18} とすれば 0,2,…,180,2,\ldots,18 の順に全要素を調べる。

(4)​

bin⁡(n)=O(log⁡n),uni⁡(n)=O(n),dec⁡(n)=O(log⁡n).\boxed{\operatorname{bin}(n)=O(\log n),\qquad \operatorname{uni}(n)=O(n),\qquad \operatorname{dec}(n)=O(\log n)}.

BinSearch は各回で区間長を半分以下にし、厳密には bin⁡(n)=⌊log⁡2n⌋+1\operatorname{bin}(n)=\lfloor\log_2n\rfloor+1。 UniSearch は最悪時に 11 要素ずつ除くため uni⁡(n)=n\operatorname{uni}(n)=n。 DecSearch の長い方の子区間は

n−1−⌊n−110⌋=⌊9n10⌋n-1-\left\lfloor\frac{n-1}{10}\right\rfloor =\left\lfloor\frac{9n}{10}\right\rfloor

要素であるから、D(0)=0D(0)=0、D(n)=1+D(⌊9n/10⌋)D(n)=1+D(\lfloor9n/10\rfloor) に従い、D(n)=Θ(log⁡n)D(n)=\Theta(\log n) となる。

(5)​

A: よりも真に小さい,B: と等しい,C: よりも真に大きい\boxed{A:\text{ よりも真に小さい},\quad B:\text{ と等しい},\quad C:\text{ よりも真に大きい}}。

本页目录