数値を扱うアルゴリズムと計算問題

このレッスンの全体像：武器は「トレース表」と「2つの公式」

今回の7テーマは、次の2種類に分かれます。

トレースとは、流れ図やプログラムを手で1ステップずつ実行し、変数の値の変化を追うことです。頭の中だけで追うと、分岐の向きや何回目かを取り違えます。必ず表に書くのが、いちばん確実な対策です。

引き算の繰返しで割り算をする（商と余り）

結論：y を引けた回数が商 q、引けなくなったときの残りが余り r です。

商は割り算の答えの整数部分、余りは割り切れずに残った数です。たとえば、17個のみかんを5個ずつ袋に詰めると、3袋できて2個残ります。袋の数が商、残ったみかんが余りです。

flowchart TD
  A["q ← 0, r ← x"] --> B{"r ＜ y ?"}
  B -- "No" --> C["r ← r − y, q ← q + 1"]
  C --> B
  B -- "Yes" --> D["終了（q＝商, r＝余り）"]

x=17、y=5 でトレースすると次のとおりです。

結果は q=3（17÷5 の商）、r=2（余り）です。選択肢は「商と余りを入れ替えたもの」と「x と y を入れ替えたもの」でひっかけてきます。引かれているのは x、引いているのは y なので、x÷y になります。

ユークリッドの互除法（最頻出・厚めに）

結論：2つの数の「大きい方から小さい方を引く（または割った余りに置き換える）」操作を繰り返すと、最後に残る数が最大公約数です。

**最大公約数（GCD）**は、2つの数を両方とも割り切れる数のうち最大のものです。たとえば 12 と 18 なら 6 です。ユークリッドの互除法は、これを速く求める古典的な手順です。

試験には2つの書き方が出ます。見た目は違いますが、どちらも答えは最大公約数です。

mod は割り算の余り（x mod y ＝ x を y で割った余り）、div は商の整数部分です。mod版は引き算版の「同じ数を何回も引く」部分を、1回の割り算で済ませたものです。

よく出る問われ方は3つです。

• 比較は何回か：引き算の回数に、最後の「等しい」と判定する1回を足します。これを数え忘れるのが典型的なミスです。
• 答えの値：途中に出てくる余りや初期値を答えに選ばせる選択肢があります。
• 指定した順に実行させる初期値の関係：数字を入れずに a、b のまま追い、最後の「m=n」を式にします（例題参照）。

10進数を2進数に変える（2で割る方法）

結論：2で割った余り（0か1）を下の桁から順に並べたものが2進数です。 商は次の割り算に使います。

j=13 なら、13→余り1・商6、6→余り0・商3、3→余り1・商1、1→余り1・商0 です。下の桁から 1,0,1,1 と並ぶので、2進数では 1101 になります。

流れ図では、**先に余りを格納し（NISHIN(k) ← j mod 2）、あとで j を商に更新する（j ← j div 2）**という順番が大事です。順番を逆にすると、元の j の余りを取る前に j が変わってしまいます。選択肢は「div と mod の入れ替え」と「a と b の順番の入れ替え」でひっかけてきます。

シフト演算と加算で掛け算をする

結論：小学校の筆算と同じです。乗数を1桁ずつ見て、その桁が1なら被乗数を足します。 1桁進むごとに、被乗数を左へ1つずらします。

シフトはビット列を左右にずらす操作です。論理シフトは、空いたところに0を入れるシフトです。

第0ビットは最下位ビット（いちばん右の桁）です。毎回「Y の第0ビットを見る → 1なら Z に X を足す → X を左に、Y を右に1ビットずらす」を16回繰り返します。選択肢は「第15ビット（最上位）を見る」と「シフトの左右が逆」の組合せでひっかけてきます。Y を右にずらすなら、見るべきは毎回同じ第0ビットです。

反復の収束（不動点）

y ← f(x)、x ← y を繰り返して y が変わらなくなったら、次の f に入る x も y と同じ値です。つまり f(y) = y が成り立ちます。このような値を不動点と呼びます。f(a)=y は1回目だけの関係なので、ひっかけです。

格子の最短経路は「並べ方」の数

結論：右に m 回・上に n 回進む最短経路の数は C(m+n, n) です。

最短経路では、後戻りせずに右と上だけで進みます。そのため経路は、「右」と「上」の札を何通りに並べられるかと同じ数になります。組合せ C(n,r) は、n 個の中から r 個を選ぶ選び方の数で、C(5,2) = (5×4)÷(2×1) = 10 です。

経由点がある問題では、つい足し算をしたり、R を無視して全体の数を数えたりしがちです。「〜を通って」と書かれていたら、2つの区間に分けて掛け算します。

符号の平均ビット数と一意に復号できる条件

結論：平均ビット数 ＝ Σ（各文字のビット長 × 出現確率）です。 ビット長をただ平均するのではなく、よく出る文字ほど重く数えます。

一意に復号できるとは、つながったビット列を区切り方が1通りに決まる形で元に戻せることです。試験では、語頭条件（どの符号も、ほかの符号の先頭部分になっていない）を満たしていれば一意に復号できると判断して解けます。

選び方は2段階です。まず語頭条件で候補を絞り、残った中で平均ビット数を比べます。いちばん短く見えても、復号できない符号は不正解です。