2008-8 第1問 (3)

(a) 衝突回避はチェイン法による
0 : (k₃, r₃)
1 : (k₂, r₂)
2
3
4 : (k₅, r₅), (k₆, r₆)
5 : (k₇, r₇), (k₈, r₈)
6
7
8
9
10 : (k₁, r₁)
11
12 : (k₄, r₄)
13
14
15
16

(b)
v = k₁, k₂, k₃, k₄, k₅, k₇ のとき、比較回数は1回
v = k₆, k₈ のとき、比較回数は2回

よって、
C = (1 * 6 + 2 * 2) / 8 = 5 / 4
C_max = 2