プログラミングの基礎(擬似言語のトレース)
次の関数 c を c(4, 2) として呼び出したとき、c が呼ばれる回数(最初の呼出しを含む)はどれか。
○整数型: c(整数型: n, 整数型: k)
if (k = 0 or k = n)
return 1
endif
return c(n − 1, k − 1) + c(n − 1, k)- A5
- B6
- C11
答えと解説を見る
正解：C. 11
c(n, k) は、n 個から k 個を選ぶ組合せの数(二項係数)を、パスカルの三角形の関係で求めます。c(4, 2) は c(3, 1) と c(3, 2) を呼び、それぞれがさらに c(2, 0) と c(2, 1)、c(2, 1) と c(2, 2) を呼び、2回現れる c(2, 1) はどちらも c(1, 0) と c(1, 1) を呼びます。1を返す呼出しが6回、2つの呼出しを行う呼出しが5回あり、合計11回です。戻り値は6で、1を返す呼出しの回数と一致します。
- A. 2つの呼出しを行う呼出しの回数だけを数えた値です。1を返す6回も数えます。
- B. 戻り値 c(4, 2) = 6 で、呼ばれる回数ではありません。
- C. 正しい。1を返す6回と、2つの呼出しを行う5回の合計です。