平成24年度 高度共通 午前I（PM試験） 問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で割った余りを返すものとする。〔関数の定義〕gcd(m, n)＝m（n＝0のとき），gcd(n, m mod n)（n＞0のとき）
- ア 2
- イ 3
- ウ 4
- エ 5
解答・解説を見る
正解：ウ
AI解説
定義に従って再帰呼出しを順に書き出す。gcd(135,35)→135 mod 35=30なのでgcd(35,30)→35 mod 30=5なのでgcd(30,5)→30 mod 5=0なのでgcd(5,0)→n=0となり5を返して終了。呼出しはgcd(135,35)、gcd(35,30)、gcd(30,5)、gcd(5,0)の4回であり、正解はウ。これはユークリッドの互除法による最大公約数の計算である。 ア: 2回は誤り。剰余計算を途中で打ち切った場合の数え方であり、n=0になるまで呼出しは続く。 イ: 3回は誤り。最後のgcd(5,0)(n=0で終了する呼出し)を数え忘れるとこの値になる。典型的なひっかけである。 ウ: 正しい。gcd(135,35)→gcd(35,30)→gcd(30,5)→gcd(5,0)で計4回呼び出される。 エ: 5回は誤り。余りが0になった後はそれ以上呼び出されない。 💡 再帰回数を問う問題は、頭の中で追わず必ず呼出し列を紙に書き出す。「最初の呼出しも1回に数える」「終了条件の呼出しも1回」という条件の読み落としが最頻出のミスである。
出典：平成24年度 秋期 プロジェクトマネージャ試験 午前I 問3 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。