LeetCode 509. 斐波那契数

村雨遥

发布于 2020-04-09 15:21:32

2940

发布于 2020-04-09 15:21:32

文章被收录于专栏：JavaPark

题目

509. 斐波那契数[1]

描述

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

示例 1：

**输入：**2 **输出：**1 **解释：**F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

**输入：**3 **输出：**2 **解释：**F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

**输入：**4 **输出：**3 **解释：**F(4) = F(3) + F(2) = 2 + 1 = 3.

解题思路

利用递归的思想；
当N为0或1时，返回自身的值；
当N大于1时，返回fib(N-2)+fib(N-1)的值

实现

package Array;

/**
 * Created with IntelliJ IDEA.
 * Version : 1.0
 * Author  : cunyu
 * Email   : cunyu1024@foxmail.com
 * Website : https://cunyu1943.github.io
 * Date    : 2020/4/4 17:05
 * Project : Algorithm illustration
 * Package : Chapter3
 * Class   : Fibonacci
 * Desc    : 509. 斐波拉契数
 */
public class FiveZeroNine {
	public static void main(String[] args) throws Exception {
		FiveZeroNine fiveZeroNine = new FiveZeroNine();
		int N = 9;
		System.out.println(fiveZeroNine.fib(N));
	}

	/**
	 * 斐波拉契数
	 * @param N
	 * @return 斐波拉契数列中第N个值
	 */
	public int fib(int N) {
		if (N == 0 || N == 1) {
			return N;
		} else {
			return fib(N - 1) + fib(N - 2);
		}

	}
}

参考资料

[1]

509. 斐波那契数: https://leetcode-cn.com/problems/fibonacci-number/

题目

509. 斐波那契数[1]

描述

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N，计算 F(N)。

示例 1：

输入： 2

输出： 1

解释： F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2：

输入： 3

输出： 2

解释： F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3：

输入： 4

输出： 3

解释： F(4) = F(3) + F(2) = 2 + 1 = 3.

解题思路

利用递归的思想；
当N为0或1时，返回自身的值；
当N大于1时，返回fib(N-2)+fib(N-1)的值

实现

package Array;

/**
 * Created with IntelliJ IDEA.
 * Version : 1.0
 * Author  : cunyu
 * Email   : cunyu1024@foxmail.com
 * Website : https://cunyu1943.github.io
 * Date    : 2020/4/4 17:05
 * Project : Algorithm illustration
 * Package : Chapter3
 * Class   : Fibonacci
 * Desc    : 509. 斐波拉契数
 */
public class FiveZeroNine {
	public static void main(String[] args) throws Exception {
		FiveZeroNine fiveZeroNine = new FiveZeroNine();
		int N = 9;
		System.out.println(fiveZeroNine.fib(N));
	}

	/**
	 * 斐波拉契数
	 * @param N
	 * @return 斐波拉契数列中第N个值
	 */
	public int fib(int N) {
		if (N == 0 || N == 1) {
			return N;
		} else {
			return fib(N - 1) + fib(N - 2);
		}

	}
}