応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

最大公約数を求めるアルゴリズム

平成29年春期 午前 問6
問6 次の流れ図の処理で,終了時のxに格納されているものはどれか。ここで,与えられたa,bは正の整数であり,mod(x,y)はxをyで割った余りを返す。

H29h-問6
ア aとbの最小公倍数
イ aとbの最大公約数
ウ aとbの小さい方に最も近い素数
エ aをbで割った商
実際に数字を入れてみるといいでしょう。
mod(x,y)はxをyで割った余りを返す。とありますから、xの方を大きくしましょう。
たとえば、a=10、b=3とします。
x=10、y=3

ループ1の1回目(y=0ではないので)
t=1(10÷3=3 余り1)
x=3
y=1

ループ1の2回目(y=0ではないので)
t=0
x=1
y=0
つまり、x=1であることが分かります。では、選択肢の4つを見ると
ア aとbの最小公倍数 ⇒30なので×
イ aとbの最大公約数 ⇒1なので○
ウ aとbの小さい方に最も近い素数 ⇒1なので○
エ aをbで割った商 ⇒3なので×
よって、イかウです。

イではないかとあたりをつけて、a=12、b=8、xが最大公約数である4になるかを確かめましょう。
たとえば、a=12、b=8とします。
x=12、y=8

ループ1の1回目(y=0ではないので)
t=4(12÷8=1 余り4)
x=8
y=4

ループ1の2回目(y=0ではないので)
t=0
x=4
y=0
と、xが最大公約数である4になりました。これは、選択肢ウのaとbの小さい方に最も近い素数である2とも違います。よって、イが正解です。

過去に似たような問題が出題されていますので、このアルゴリズムは最大公約数を求めるものだと覚えておくとよいでしょう。

【正解】イ
補足および実際のプログラムはこちら
http://sm.seeeko.com/archives/65924350.html