平成29年度 高度共通 午前I（PM試験） 問3
次の流れ図の処理で，終了時の x に格納されているものはどれか。ここで，与えられた a，b は正の整数であり，mod(x,y) は x を y で割った余りを返す。
- ア a と b の最小公倍数
- イ a と b の最大公約数
- ウ a と b の小さい方に最も近い素数
- エ a を b で割った商
解答・解説を見る
正解：イ
AI解説
正解はイ。流れ図はxとyの大小を比較し、大きい方から小さい方を引く(または剰余をとる)操作を、両者が等しく(余りが0に)なるまで繰り返す構造で、これはユークリッドの互除法である。互除法の終了時に得られる値はaとbの最大公約数である。 ア: 最小公倍数はa×b÷(最大公約数)で求められるが、この流れ図では乗算を行っておらず得られない。 イ: 正解。mod(x,y)で余りを取りながら値を入れ替える処理はユークリッドの互除法そのもので、最終的にxには最大公約数が残る。 ウ: 素数を求めるには割り切れるかどうかの判定を多数の数に対して行う必要があり、この流れ図の処理とは異なる。 エ: 商を求めるだけなら1回の除算で済み、余りが0になるまで繰り返す構造にはならない。 💡 「mod(余り)を取りつつ2つの値を入れ替えて繰り返す」流れ図を見たら即ユークリッド互除法=最大公約数と判断してよい。例:a=12,b=8→8,4→4,0で答え4。
出典：平成29年度 秋期 プロジェクトマネージャ試験 午前I 問3 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。