応用情報技術者 2014年 春期 午後 問03

解答の論理構成

1. 第1ループの終了条件（ア）
   • 問題文は「両者は同時に出発し、進んだマス…の余りを比較しながら、余りが一致するところ…まで進む。」と述べています。
   • したがってウサギ（p）とカメ（m）の余りが一致した時点でbreakすべきです。
   • よって ア は「mがpと等しい」。
2. pを元に戻す操作（イ）
   • 同じ段落で「ウサギは最初に戻って」とあるため、ウサギの余りpを開始時の余り1にリセットします。
   • よって イ は「p ← 1」。
3. 循環節先頭を探すループ条件（ウ）
   • 復帰後は「今度は両者とも1歩ずつ進む。最初に両者の余りが一致したところ…が、循環節の先頭」と説明されています。
   • 一致するまで繰り返すのでループ条件は「mがpと等しくない」。
   • よって ウ は「mがpと等しくない」。
4. 循環節末尾検出の初期化（エ）
   • 末尾は「ウサギだけが再びカメと余りが一致するところ…まで1歩ずつ進む」ことで求めます。
   • このときt（末尾位置）は循環節の先頭位置sから数え始める必要があります。
   • よって エ は「t ← s」。

誤りやすいポイント

• 第1ループと第2ループの比較対象を混同し、ア と ウ を逆に記入してしまう。
• 「ウサギは最初に戻る」を「余りを 0 にする」と誤解し、イ に「p ← 0」としてしまう。
• 末尾検出でtを0から数え始め、エ を書き漏らして循環節長がずれる。

FAQ

解答の導き方

• $r_1=$ amari($1\times 10,88$) $=10$
• $r_2=$ amari($10\times 10,88$) $=100\mathrm{mod}88=12$
• $r_3=$ amari($12\times 10,88$) $=120\mathrm{mod}88=32$
• $r_4=$ amari($32\times 10,88$) $=320\mathrm{mod}88=56$
• $r_5=$ amari($56\times 10,88$) $=560\mathrm{mod}88=32$

• 反復1: m=f(1)=10 、 p=f(f(1))=f(10)=12 → 等しくない（α 回数1）
• 反復2: m=f(10)=12 、 p=f(f(12))=f(32)=56 → 等しくない（α 回数2）
• 反復3: m=f(12)=32 、 p=f(f(56))=56 → 等しくない（α 回数3）
• 反復4: m=f(32)=56 、 p=f(f(56))=56 → 等しいのでbreak（α 回数4）

• 繰り返し1: s→2, m=f(56)=32（β 回数1）, p=f(1)=10 → 等しくない
• 繰り返し2: s→3, m=f(32)=56（β 回数2）, p=f(10)=12 → 等しくない
• 繰り返し3: s→4, m=f(56)=32（β 回数3）, p=f(12)=32 → 等しいので終了

誤りやすいポイント

• [イ] を m ← 1 と誤解する点。本文は「ウサギは最初に戻る」と明記しており,正しくは p ← 1 です。ここを取り違えると先頭検出の初期状態が逆になり誤ったカウントになります。
• 余りのインデックスと小数桁位置のズレ（余りのインデックス $\mu$ と小数桁位置 $s$ は $s=\mu +1$）を見落とす点。余りが最初に繰り返した位置と、循環節の先頭小数桁は1つずれます。
• ループ内で変数を更新してから比較しているか（更新後にifを行うか）を見落とし、初期状態で即一致すると誤判断する点。プログラムは各反復でまずm,pを更新してから比較しています。
• β を周期長 $\lambda$ と混同する点。β は先頭検出フェーズでのカメの更新回数で、余り列の最初の循環位置 $\mu$ に等しくなります（今回は $\mu =3$）。
• 終了条件として余りが0になる場合（有限小数）は第2フェーズを実行しない点（コード中にif(pが0と等しくない) がある）を忘れる点。

FAQ

解答の導き方

誤りやすいポイント

• pが0になった瞬間にmも同一回で0になると誤解する。例：n=4では初回でpが0になりmは2、次回にmが0になってその時点で一致してbreakする。pが先に0になることがある点を押さえること。
• s, t が初期化で0になっている点を見落とすと、戻り値が0である理由が説明できない。図6冒頭の「s ← 0」「t ← 0」を必ず確認する。
• whileを抜けた直後の判定「if(pが0と等しくない)」を読み違え、p==0でも先頭検出処理が行われると誤解しやすい（実際はスキップされる）。

FAQ

解答の論理構成

1. 記憶域量の考察
   • プログラム図6には変数として「n」「m」「p」「s」「t」の5つしか登場しません。
   • 【問題文】では「与えられたnに基づき、0記法で表した場合、関数junkanのプログラムが必要とする記憶域の大きさは オ」とあります。
   • 配列やリストなどサイズがnに比例する構造を一切使わず、固定個数のスカラー値だけで処理しているため、必要なメモリは入力サイズnに依存せず一定です。
   • よって オ には計算機科学で「定数時間（空間）」を表す O(1) が入ります。
2. 計算量の考察
   • 周期検出部（ウサギとカメで余りが一致するまで）
     while ループは余りの総種類数である高々 n−1 回で必ず終了します（同じ余りが出現すると循環が確定するため）。
   • 循環節の先頭検出部、末尾検出部も、それぞれ循環節長＋非循環部長を1回ずつなぞるだけなので、総和は高々n−1歩です。
   • したがって全体で実行する余り計算は入力値に比例し、「計算量は カ となる」という記述には O(n) が当てはまります。
3. まとめ
   • 記憶域：固定個数の変数のみ → O(1)
   • 計算量：余りの種類数（最大n−1）だけ繰返し → O(n)

誤りやすいポイント

• 「amari(a,b) を2回呼ぶから2倍でO(2n)」と細かく数えてしまう
  ➔ 演算回数に定数倍を付けてもビッグオー表記では同じO(n) です。
• 余りを毎回記録していると勘違いし、記憶域をO(n) としてしまう
  ➔ 本アルゴリズムはフロイド法なので記録は不要です。
• 循環節長だけを計算量として採り「最大でもn−1だからO(n−1)」と書く
  ➔ 引き算も定数扱い、正式にはO(n) とします。

FAQ