解答と解説: Fibonacci Sequences

「問題演習: Fibonacci Sequences」の解答編です。Web 上でよく見かけるフィボナッチ数列のプログラムは再帰を使っています。今回は再帰を使うことができないという制約を付けて問題を出題しました。

解答例

Javaでの解答例です。

解答例１）

	public class Solution {
	public int fibonacci(int n) {
	if (n < 2) {
	return n;
	}
	int[] dp = new int[n + 1];
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
	dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
	}
	}

view raw fibonacci.java hosted with ❤ by GitHub

解答例２）

	public class Solution {
	public int fibonacci(int n) {
	if (n < 2) {
	return n;
	}
	int a = 0;
	int b = 1;
	for (int i = 2; i <= n; i++) {
	int tmp = a + b;
	a = b;
	b = tmp;
	}
	return b;
	}
	}

view raw fibonacci.java hosted with ❤ by GitHub

解説

解答例の解説をする前に、フィボナッチ数列を初めて見た人のために再帰を使ったプログラムを載せておきます。

	public class Solution {
	public int fibonacci(int n) {
	if (n < 2) {
	return n;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
	}
	}

view raw fibonacci.java hosted with ❤ by GitHub

解答例１は動的計画法を用いたプログラムです。上記の再帰を使ったプログラムでは、同じ値に対するフィボナッチ数を何度も計算していました。例えば fibonacci(5) を求めるとき fibonacci(4) + fibonacci(3) が呼ばれます。このとき fibonacci(4) は fibonacci(3) + fibonacci(2) を実行します。この時点で fibonacci(3) が 2 回実行されていることがわかります。1 度だけ実行して解を保存し、再度必要になったときに再利用する方が効率的です。これを実装したのが解答例１になります。

解答例２は a に 1 つ前のフィボナッチ数、b に現在のフィボナッチ数を格納し、n に近づくたびに b には両者の和を入れ、a には前回のフィボナッチ数である b を入れるようにしています。これを n まで繰り返すと b には n 番目のフィボナッチ数が入ります。

他にも数学的な解法などありますので興味ある方はご覧ください。ウィキべディアへのリンクを貼っておきます。

以上が今回の解説になります。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。