平成24年春期 午前I 共通 問3

関数gcd(m,n)が次のように定義されている。
m=135, n=35のとき、gcd(m,n)は何回呼ばれるか。
ここで、最初のgcd(135,35)の呼び出しも、1回に数えるものとする。
また、m, n(m>n≧0)は整数とし、m mod nはmをnで割った余りを返すものとする。

[関数の定義]
(要図)

ア 2
イ 3
ウ 4
エ 5


ジョブりんご
「机上デバッグをするんだ。」

こぼる
「ギークが言語の性能評価に使う、回帰か!」

ジョブりんご
「Objective-C 大好き!」

こぼる
「えっと、
gcd(135,35) : 1回目
gcd(35,mod(135,35) : 2回目
ん?modってなに??」

ジョブりんご
「余り算だ。剰余算とも言う。」

こぼる
「じゃあ、mod(135,35)のこたえって…
135÷35=3あまり30 で、30なのかな。」

ジョブりんご
「それで合っている。」

こぼる
「んと、じゃあ続きね。
gcd(30,mod(35,30)) = gcd(35,5) : 3回目
gcd(5,mod(30,5) = gcd(5,0) : 4回目
4回呼び出したから、答えはウ!」

ジョブりんご
「難しかったか?」

こぼる
「えへへ。実はMODって、Excelで使ったことあるから知ってたわ~2年前から知ってたわ。」

ジョブりんご
「競合他社の花形ツールを使うなんて!!」