平成22年度 秋期 午前 問7
基礎理論
流れ図に関する問題
正の整数 M に対して，次の二つの流れ図に示すアルゴリズムを実行したとき，結果 x の値が等しくなるようにしたい。a に入れる条件として，適切なものはどれか。
〔二つの流れ図〕
左の流れ図（前判定のループ端で書いたもの）
開始 → 1→x → ループ端〔演算 n：M，−1，1〕→ x×n→x → ループ端〔演算〕→ 終了
注記「ループ端の繰返し指定は，変数名：初期値，増分，終値 を示す。」
⇒ n は M から始まり、−1 ずつ増え、1 で終わる（M, M−1, …, 2, 1）
右の流れ図（後判定で書き直したもの）
開始 → 1→x → 1→n
→ 〔x×n→x〕→〔n＋1→n〕→ 判断〔 a 〕
判断が No … 〔x×n→x〕の手前へ戻る
判断が Yes … 終了- アn＜M
- イn＞M－1
- ウn＞M
- エn＞M＋1
答えと解説を見る
✓ これが正解ウn＞M
解説
掛け終えた時点の変数の値で、終了条件を決めます。
2 つの流れ図は同じ値を作ることが求められています。左は繰返し指定を使った前判定の形で、変数は与えられた正の整数から 1 ずつ減って 1 まで動くので、掛け合わせた結果はその整数の階乗になります。右は後判定に書き直したアルゴリズムで、掛け算を先に行い、そのあと変数を 1 増やしてから判断に進みます。ここで見るべき点は 2 つだけです。最後に掛けたい値はいくつか、そしてその掛け算を終えた時点で変数がいくつになっているか、です。右の流れ図では、変数が 1 のときに 1 度掛け、増やしてから判断に入ります。ですから k 回目に掛けるのは k であり、掛け終えた時点の変数は k ＋ 1 です。元の整数を掛け終えた瞬間に止めたいので、変数がその整数を超えたときに終わる条件を置けばよいことになります。前判定と後判定では判断に来たときの変数が 1 つずれるので、左の初期値や終値をそのまま写すと必ず 1 回分多いか少なくなります。小さい値で 4 つの条件を実際に回して確かめてください。
ほかの選択肢はなぜ違うのか
- アn＜M：不等号の向きが逆で、1 周目の判断でいきなり条件が成り立ちます。1 度しか掛けないまま終わるので、整数が 3 のときの結果は 1 にとどまり、階乗になりません。
- イn＞M－1：止まる時期が 1 周早くなります。整数が 3 のとき 2 周目で終わって結果は 2 となり、最後の 1 回分を掛ける前に判断が成り立ってしまいます。
- エn＞M＋1：止まる時期が 1 周遅れます。整数が 3 のとき 4 周目まで回って結果は 24 となり、余分に 1 つ大きい値まで掛けてしまいます。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成22年度 秋期 応用情報技術者試験 午前 問7
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）