練習問題

13A-1: フィボナッチ数（難易度♠） †

フィボナッチ数列は、一つ前の項と二つ前の項の和で定義され、1, 1, 2, 3, 5, 8, 13, 21,... と続く数列である。 \[ \begin{align} f_1 &= 1 \\ f_2 &= 1 \\ f_n &= f_{n-1} + f_{n-2} \quad \text{($n > 2$)} \end{align} \] [math]n[/math] を大きくすると、隣り合うフィボナッチ数の比 [math]\frac{f_n}{f_{n-1}}[/math] が黄金比に近づく。

20番目のフィボナッチ数 [math]f_{20}[/math] を求めるプログラムを作成せよ。

13A-2: ユークリッドの互除法（難易度♠） †

ユークリッドの互除法は、二つの正の整数 [math]m[/math], [math]n[/math] ([math]m > n[/math])の最大公約数を求めるアルゴリズムである。

• [math]m[/math] が [math]n[/math] で割り切れるとき、[math]n[/math] が最大公約数
• そうでないとき、[math]m[/math] を [math]n[/math] で割ったときの余りを [math]r[/math] とすると、[math]n[/math] と [math]r[/math] の最大公約数が、[math]m[/math] と [math]n[/math] の最大公約数

ユークリッドの互除法を用いて 84 と 49 の最大公約数を求めるプログラムを作成せよ。

13A-3: 基数変換（難易度♠♠） †

10進数を2進数に変換するには、まず 2 で割り、商と余りを求める。 求めた商をさらに 2 で割り、商と余りを求める。 これを商が 0 になるまで繰り返し、求めた余りを逆順に並べると2進数になる。

たとえば、10進数の 10 について考えると、10 を 2 で割ると 5 余り 0、5 を 2 で割ると 2 余り 1、2 を 2 で割ると 1 余り 0、1 を 2 で割ると 0 余り 1 である。 余りを逆順に並べると 1010 になり、これが10進数 10 を2進数で表したものである。

10進数 65 を2進数に変換して出力するプログラムを作成せよ。

13A-4: ハノイの塔（難易度♠♠♠） †

ハノイの塔とは、次のようなパズルである。

[math]n[/math]枚の大きさが異なる円盤がある。 大きな円盤を小さな円盤の上に置くことはできず、円盤を置くことができる場所は A, B, C の3つしかない。 今、A にすべての円盤が下から大きい順に積まれている。 すべての円盤を C に移動させるには、どうしたらいいか。

5段のハノイの塔を解く手順を出力するプログラムを作成せよ。

13A-5: 配列のコピー（難易度♠♠） †

次の部分プログラムは、配列aの要素を配列bに再帰的にコピーするものである。 プログラムを完成させよ。

/*
 *  配列aの要素を配列bに再帰的にコピーする
 */
void copy(int a[], int b[], int from, int to) {
  if (from <= to) {
    b[from] = a[from];
    copy(a, b,        ,        );
  }
}

int main(void) {
  int a[5] = {1, 2, 3, 4, 5}, b[5];

  copy(a, b, 0, 4);  // 配列aから配列bへ要素番号0から4までの要素をコピーする

  int i;
  for (i = 0; i < 5; i++) {
    printf("%d\n", b);
  }

  return 0;
}

13A-6: 人口シミュレーション（難易度♠） †

[math]n[/math]年の人口を[math]P_n[/math]とすると、人口の増減は漸化式を用いて次のようにモデル化できる。 \[ \begin{align} \Delta P_n &= P_n - P_{n-1} = \alpha P_{n=1} \\ P_n &= (1 + \alpha) P_{n-1} \end{align} \] ここで、[math]\alpha[/math]は、前年同月比の人口増加率を表す。

2015年（7月1日現在）の日本人人口は1億2523万4000人で、前年同月に比べ0.21%の減少であった。 このときの人口増加率が続くとして、50年後（2065年）の日本人人口を推計するプログラムを、再帰関数populを定義して作成せよ。