2008-8 第2問 (3)
(2)で求めた回路を次のように変更する。
このカウンタを利用して、以下のように回路を構成する。
このカウンタを利用して、以下のように回路を構成する。
スポンサーサイト
2008-8 第1問 (4)
逐次探索はプログラムが非常に単純で実装が容易だが、エントリ数が多いと実行速度が遅くなってしまう。
2分探索はO(logN)で動作するため、エントリ数が増えても高速に動作するが、事前にデータをソートしておく必要がある。
ハッシュ表はエントリ数が増えても定数時間で探索が可能であり、2分探索よりも更に高速だが、メモリの使用量が非常に大きいという問題がある。
2分探索はO(logN)で動作するため、エントリ数が増えても高速に動作するが、事前にデータをソートしておく必要がある。
ハッシュ表はエントリ数が増えても定数時間で探索が可能であり、2分探索よりも更に高速だが、メモリの使用量が非常に大きいという問題がある。
2008-8 第1問 (3)
(a) 衝突回避はチェイン法による
0 : (k3, r3)
1 : (k2, r2)
2
3
4 : (k5, r5), (k6, r6)
5 : (k7, r7), (k8, r8)
6
7
8
9
10 : (k1, r1)
11
12 : (k4, r4)
13
14
15
16
(b)
v = k1, k2, k3, k4, k5, k7 のとき、比較回数は1回
v = k6, k8 のとき、比較回数は2回
よって、
C = (1 * 6 + 2 * 2) / 8 = 5 / 4
Cmax = 2
0 : (k3, r3)
1 : (k2, r2)
2
3
4 : (k5, r5), (k6, r6)
5 : (k7, r7), (k8, r8)
6
7
8
9
10 : (k1, r1)
11
12 : (k4, r4)
13
14
15
16
(b)
v = k1, k2, k3, k4, k5, k7 のとき、比較回数は1回
v = k6, k8 のとき、比較回数は2回
よって、
C = (1 * 6 + 2 * 2) / 8 = 5 / 4
Cmax = 2
