アルゴリズム (全80問中78問目)
No.78
非負の整数nに対して次のとおりに定義された関数F(n)，G(n)がある。F(5)の値は幾らか。
F(n): if n≦1 then return 1 else return n×G(n－1)
G(n): if n＝0 then return 0 else return n＋F(n－1)
F(n): if n≦1 then return 1 else return n×G(n－1)
G(n): if n＝0 then return 0 else return n＋F(n－1)
出典：平成16年春期 問14
- 50
- 65
- 100
- 120
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
設問の関数式は改行がなくわかりにくいですが、整理すると以下のような感じです。
F(n)：
もしnが1以下ならば1を返す、
そうでなければn×G(n－1)の戻り値を返す
もしnが1以下ならば1を返す、
そうでなければn×G(n－1)の戻り値を返す
G(n)：
もしnが0ならば0を返す、
そうでなければn＋F(n－1)の戻り値を返す
式"F(5)"を展開していくと次のようになります。もしnが0ならば0を返す、
そうでなければn＋F(n－1)の戻り値を返す
- F(5)
- 引数5が1以下ではないので"5×G(5－1)"→"5×G(4)"を返す
- G(4)
- 引数4が0ではないので"4＋F(4－1)"→"4＋F(3)"を返す
- F(3)
- 引数3が1以下ではないので"3×G(3－1)"→"3×G(2)"を返す
- G(2)
- 引数2が0ではないので"2＋F(2－1)"→"2＋F(1)"を返す
- F(1)
- 引数1が1以下なので1を返す
- G(2)＝2＋F(1)＝2＋1＝3
- F(3)＝3×G(2)＝3×3＝9
- G(4)＝4＋F(3)＝4＋9＝13
- F(5)＝5×G(4)＝5×13＝65