A型システムエンジニアの勉強メモ

情報処理試験の午前問題をネタにして、解説をじっくり書きながら勉強しています。基礎は大事。

広告

基本情報技術者試験 令和元年度 秋季 午前 問11

再帰的に定義される関数の問題。ついでに自然数で少し脱線。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問11

 

自然数 n に対して、次の通り再帰的に定義される関数  f(n) を考える。  f(5) の値はどれか。

 

 f(n) :  if  n ≦ 1  then  return  1  else  return   n + f(n-1)

 

ア 6

イ 9

ウ 15

エ 25

--------------------------

解説

 

再帰的に定義される関数については以下で書いてみている。

koki2016.hatenadiary.com

 

再帰(さいき)とは、ある記述をする際に、その記述の中に自身への参照が含まれていること。

 

 f(n) :  if  n ≦ 1  then  return  1  else  return   n + f(n-1)

 

一行で書くとわかりにくいので、少し工夫して、プログラムみたく改行とインデントを加えてみる。

 

 f(n) :

if  n ≦ 1

then

    return  1

else

    return   n + f(n-1)

 

n が 1 以下のときは 1 を返し、そうでないときは  n + f(n-1) を返すということ。

 

 

問題としては  f(5) を聞いているので、 f(n) の定義に従うと以下のようになる。

 

 f(5)

=  5 + f(5-1)

=  5 + f(4)  

=  5 + 4 + f(4-1)

=  5 + 4 + f(3)

=  5 + 4 + 3 + f(3-1)

=  5 + 4 + 3 + f(2)

=  5 + 4 + 3 + 2 + f(2-1)

=  5 + 4 + 3 + 2 + f(1)  

=  5 + 4 + 3 + 2 + 1  f(1) は n ≦ 1 のときなので 1 になる

=  15

 

となるので、正解は選択肢ウの 15

 

 

計算の途中を見ての通り、この関数は n 以下の正の整数の和を求めている。

等価な数式にするとこんな感じ。

 f(n) = \sum_{k=1}^n k

 

 

ちなみに問題では自然数 n と書いているが、自然数には 0 を含まない流儀と含む流儀がある。

 

  • 0 を含まない流儀の場合は、ここまでの話に問題はない。
  • 0 を含む流儀の場合は、ちょっと問題が起きてくる。

 

問題の  f(n) では n ≦ 1 で return 1 なので、 f(0) = 1 になる。

一方で、

 f(n) = \sum_{k=1}^n k

では  f(0) = 1 とはならないので、等価な数式ではなくなってしまう。

 

勝手に等価な数式は~とか言い出して、勝手に問題が~とか言っているだけなのでどうでもいいことではあるけれど。

関数は定義域もちゃんと意識しましょう、という話でした。

 

 

 

前後の問題はこちら。

koki2016.hatenadiary.com