千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2016年8月実施 専門 A5

标签：

• Binary-Search
• Algorithm-Complexity

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

次の Pascal プログラムを考える。

const n = max;
var a: array [1..n] of integer;
    p, c: integer;
function src(t: integer): boolean;
  var b, e, m: integer;
begin
  if t <= 0 then begin src := false; p := 0; c := 0 end
  else begin
    b := 1; e := n; c := 1;
    while b <= e do begin
      m := (b + e) div 2; c := c + 1;
      if t < a[m] then e := m - 1 else b := m + 1
    end;
    p := e;
    { * }
    src := (t = a[e])
  end
end;

(1) max=8、配列が $2,3,5,7,11,13,17,19$ のとき、src(10) の返り値と実行後の $p$ を求めよ。

(2) 同じ配列で src(m) がエラーとなり得る整数 $m$ を求めよ。

(3) エラーを防ぐよう { * } 以降を修正せよ。

(4) 一般の昇順配列 $a[1]<\cdots<a[n]$ について、実行後の $c$ が $O(\log\mathrm{max})$ となることを示せ。整数演算のあふれはない。

题目描述

考虑上述二分搜索程序。

(1) 数组为 $2,3,5,7,11,13,17,19$ 时，求 src(10) 的返回值及 $p$。

(2) 在同一数组上，哪些整数输入会引起错误？

(3) 修改 { * } 之后的语句来消除错误。

(4) 对任意严格升序数组，证明执行后的计数 $c=O(\log\mathrm{max})$，假定无整数溢出。

Kai

(1)

調べる添字は $4,6,5$。終了時 $b=5,e=4$ なので、返り値は false、$p=4$。

(2)

$m=1$。このとき全ての配列要素より小さいため $e=0$ となり、a[0] を参照してしまう。$m\le0$ は最初の分岐で終了し、$m\ge2$ なら終了時 $1\le e\le8$ なのでこのエラーはない。

(3)

if e < 1 then src := false
else src := (t = a[e])

これで添字が有効な場合のみ配列を参照する。

(4)

配列が定義できる $n=\mathrm{max}\ge1$ を考える。探索区間の長さが $L=e-b+1$ のとき、ループ一回後の長さは高々 $\lfloor L/2\rfloor$。従ってループ回数は高々 $\lfloor\log_2n\rfloor+1$ であり、$t>0$ なら

$$c\le\lfloor\log_2n\rfloor+2.$$

$t\le0$ では $c=0$。よって漸近的に $c=O(\log n)$ である。