アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20220724 実施分 問10
整数 x, y (x > y ≧ 0) に対して，次のように定義された関数 F(x, y) がある。F(231, 15) の値は幾らか。ここで，x mod y は x を y で割った余りである。
F(x, y) = x (y=0 のとき)
F(x, y) = F(y, x mod y) (y>0 のとき)
- ア 2
- イ 3
- ウ 5
- エ 7
出典：基本情報技術者試験 科目A免除 修了試験 20220724 実施分 問10
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、F(x,y)=F(y,x mod y)を余りが0になるまで繰り返して最大公約数を求める。
この問題で必要なこと
F(231,15)=F(15,6)=F(6,3)=F(3,0)=3となり、最大公約数3が得られる。
ひっかけ
途中の余り(6など)や割る数(15)を答えと取り違えさせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）