平成29年度春期 データベーススペシャリスト 午前Ⅰ 問3

流れ図を追うための確認ポイント

流れ図の各処理を順番に読み、整数の状態がどの場面で変わるかを整理することに集中しましょう。分岐や繰り返しでは、条件をその都度確認し、途中の状態を記録して全体の流れを見失わないことが大切です。

この問題で問われていること

注目する観点は、処理を一つ進めるたびに対象となる値や条件の状態を丁寧に更新できているかです。開始時の情報、分岐の判定、繰り返しの区切りを時系列で対応づけ、最後まで同じ記録方法で追跡してください。

視点

整数の処理を読むときは、流れ図を上から一度に判断せず、処理のまとまりごとに現在の状態を表に記録しながら進めます。分岐では判定時点の状態を確認し、繰り返しでは一周ごとの変化と終了条件を区別して整理すると、読み違いを減らせます。

確認ポイント

• 処理の順序を一つずつ記録する
• 分岐の判定時点を確認する
• 繰り返しごとの状態変化を整理する

正解

イ

解説

この流れ図は、二つの正の整数を、割り算の余りを使って順に小さくしていく処理です。余りが0になった時点で、最後に残ったxは両方の数に共通する最大の約数を表します。

理由

初めにx=a、y=bとし、各回でtにxをyで割った余りを入れた後、xを元のy、yを余りに置き換えます。これはユークリッドの互除法です。yが0になると、それ以上割り算の余りを求められないため、直前のxがaとbの最大公約数になります。

比較

最小公倍数は最大公約数を利用して別途計算する値であり、この処理のxに直接格納されません。また、商や近い素数を求める処理では、余りを使って二つの変数を繰り返し更新する構造にはなりません。したがって正しい選択肢はイです。

選択肢ア

これは不正解だよ。この処理は最小公倍数を直接求める手順ではなく、割り算の余りを利用して二つの値を更新し、最終的に一方を0にします。最小公倍数を求めるには、最大公約数との関係を使った別の計算が必要です。

選択肢イ（正解）

これは正解だよ。xとyを、xをyで割った余りを使って順に置き換える処理はユークリッドの互除法です。yが0になった終了時のxは、初めに与えられたaとbの両方を割り切れる最大の整数、つまり最大公約数になります。

選択肢ウ

これは不正解だよ。流れ図では素数かどうかを判定する処理や、aとbの小さい方との差を調べる処理はありません。行われているのは割り算の余りによる値の更新であり、小さい方に最も近い素数を探す処理とは異なります。

選択肢エ

これは不正解だよ。aをbで割った商を求めるだけなら、割り算の結果をそのまま保存すれば終了します。しかし流れ図では余りをtに保存し、その後xとyを入れ替える反復を行います。終了時のxは商ではなく、共通の約数を表します。

学習のポイント

ユークリッドの互除法の更新規則と停止時の値の意味を理解する。