平成24年度 春期 午前 問5
情報に関する理論
状態遷移に関する問題
図は70円切符の自動販売機に硬貨が投入されたときの状態遷移を表している。状態 Q₄ から状態 E へ遷移する事象はどれか。ここで，状態 Q₀ は硬貨が投入されていない状態であり，硬貨が1枚投入されるたびに状態は矢印の方向へ遷移するものとする。
なお，状態 E は投入された硬貨の合計が70円以上になった状態であり，自動販売機は切符を発行し，釣銭が必要な場合には釣銭を返す。また，自動販売機は10円硬貨，50円硬貨，100円硬貨だけを受け付けるようになっている。
〔状態遷移図〕 状態は Q0 Q1 Q2 Q3 Q4 Q5 Q6 と E（二重丸＝終了状態）。開始は Q0（太い矢印が入る）。 矢印（原典に事象のラベルは書かれていない）: Q0→Q1 Q1→Q2 Q2→Q3 Q3→Q4 Q4→Q5 Q5→Q6 （左から右へ1つずつ進む＝10円） Q0→Q5 Q1→Q6 （大きく飛ぶ弧＝50円） Q0→E Q1→E Q2→E Q3→E Q4→E Q5→E Q6→E 設問が問うている Q4→E の矢印だけが太く描かれている。
- ア10円硬貨が投入された。
- イ10円硬貨又は50円硬貨が投入された。
- ウ10円硬貨又は100円硬貨が投入された。
- エ50円硬貨又は100円硬貨が投入された。
答えと解説を見る
✓ これが正解エ50円硬貨又は100円硬貨が投入された。
解説
40円まで入った状態から70円に届く硬貨を選びます。
この状態遷移の図では、状態が右へ進むごとに投入済みの合計額が増えていきます。一つ隣へ進む矢印は10円硬貨が入ったときの動き、いくつか飛び越える弧はもっと高い額の硬貨が入ったときの動きです。開始の状態から数えて五番目にあたる状態は、10円硬貨が四枚入って合計40円まで来たところです。ここから終了の状態へ移るのは、合計が70円以上になったときですから、残りの30円以上を一枚で満たす硬貨が投入された場合に限られます。この自動販売機が受け付けるのは10円硬貨、50円硬貨、100円硬貨の三種類だけですから、当てはまるのは高い方の二つになります。判定の軸は、その状態までにいくら入っているかと、あと何円を一枚で埋める必要があるかの二点です。
ほかの選択肢はなぜ違うのか
- ア10円硬貨が投入された。：10円硬貨を一枚足しても合計は50円にしかならず、切符の値段には届きません。このときは終了の状態ではなく、右隣の状態へ一つ進むだけになります。
- イ10円硬貨又は50円硬貨が投入された。：50円硬貨なら合計は90円となって終了の状態へ移せますが、10円硬貨では50円にとどまります。一枚で残りを埋められない硬貨まで含めている点が正しくありません。
- ウ10円硬貨又は100円硬貨が投入された。：100円硬貨なら合計は140円となって終了の状態へ移せます。しかし10円硬貨を含めているうえ、同じく終了の状態へ移せる50円硬貨が抜け落ちており、二重に食い違います。
出典：平成24年度 春期 基本情報技術者試験 午前 問5（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）