コンピュータの仕組みとアルゴリズム

ハードウェアの構成、2進数、アルゴリズムの考え方。

この単元の目標

📑 目次

(1011)_2 = 8 + 0 + 2 + 1 = (11)_{10}, \qquad (255)_{10} = (FF)_{16}

10進 → 2進は 2で割り続けて余りを下から読む。16進は2進4桁と対応するので、2進 ↔ 16進は桁区切りだけで変換できます。

例題（線形探索 vs 二分探索）

整列済み配列1000件を二分探索するとき、中央要素を調べる回数は最大何回か。中央要素との大小・一致の判定をまとめて1回と数え、線形探索との差も述べよ。

解答・解説

二分探索は $\lfloor \log_2 1000 \rfloor + 1 = 10$ 回、線形探索は最大1000回です。増加の仕方はそれぞれ $O(\log n)$ と $O(n)$ で、差を「指数的」と呼ぶのは不正確です。二分探索では中央への直接アクセスができる整列済み配列を前提にします。

確認クイズ（コンピュータとアルゴリズム）

問1. 2進数 $(1011)_2$ を10進数で表すと？

問2. データ数 n に対する二分探索の計算量のオーダーは？

問3. アルゴリズムの基本3構造に含まれないものはどれか。

トピック第 1 問

次の2進数を10進数に変換せよ。

(11000000)_{2}

無限ドリル: 2進数⇔10進数の変換がランダムに出題されます。情報Iの計算問題の定番

📝 メモこの端末のみに保存

メモ欄はページ読み込み後に使えるようになります。