算法题/斐波那契数列：斐波那契数列

题目

写一个函数来计算第n个斐波那契数。 斐波那契数列是一系列数字，其中每个数字是前两个数字的和。最初的几个斐波那契数是:0,1,1,2,3,5,8，数学上我们可以定义斐波那契数为：

Fib(n) = Fib(n-1) + Fib(n-2), 其中：n > 1
给定基准情况: Fib(0) = 0, and Fib(1) = 1

题解

递归

Java

class Fibonacci {

  public int CalculateFibonacci(int n) {
    if(n < 2)
      return n;
    return CalculateFibonacci(n-1) + CalculateFibonacci(n-2);
  }

  public static void main(String[] args) {
    Fibonacci fib = new Fibonacci();
    System.out.println("第5个斐波那契数：---> " + fib.CalculateFibonacci(5));
    System.out.println("第6个斐波那契数：---> " + fib.CalculateFibonacci(6));
    System.out.println("第7个斐波那契数：---> " + fib.CalculateFibonacci(7));
  }
}

JavaScript

class Fibonacci {
  calculateFibonacci(n) {
    if (n < 2)
      return n;
    return this.calculateFibonacci(n - 1) + this.calculateFibonacci(n - 2);
  }

  static main() {
    const fib = new Fibonacci();
    console.log("第5个斐波那契数：---> " + fib.calculateFibonacci(5));
    console.log("第6个斐波那契数：---> " + fib.calculateFibonacci(6));
    console.log("第7个斐波那契数：---> " + fib.calculateFibonacci(7));
  }
}

Fibonacci.main();

Python

class Fibonacci:
    def calculate_fibonacci(self, n):
        if n < 2:
            return n
        return self.calculate_fibonacci(n - 1) + self.calculate_fibonacci(n - 2)

    @staticmethod
    def main():
        fib = Fibonacci()
        print("第5个斐波那契数：--->", fib.calculate_fibonacci(5))
        print("第6个斐波那契数：--->", fib.calculate_fibonacci(6))
        print("第7个斐波那契数：--->", fib.calculate_fibonacci(7))

Fibonacci.main()

Go

package main

import "fmt"

type Fibonacci struct{}

func (f Fibonacci) CalculateFibonacci(n int) int {
	if n < 2 {
		return n
	}
	return f.CalculateFibonacci(n-1) + f.CalculateFibonacci(n-2)
}

func main() {
	fib := Fibonacci{}
	fmt.Println("第5个斐波那契数：--->", fib.CalculateFibonacci(5))
	fmt.Println("第6个斐波那契数：--->", fib.CalculateFibonacci(6))
	fmt.Println("第7个斐波那契数：--->", fib.CalculateFibonacci(7))
}

自顶向下(备忘录)

Java

class Fibonacci {

  public int CalculateFibonacci(int n) {
    int dp[] = new int[n + 1];
    return CalculateFibonacciRecursive(dp, n);
  }

  public int CalculateFibonacciRecursive(int[] dp, int n) {
    if (n < 2)
      return n;
    if (dp[n] == 0)
      dp[n] = CalculateFibonacciRecursive(dp, n - 1) + CalculateFibonacciRecursive(dp, n - 2);
    return dp[n];
  }

  public static void main(String[] args) {
    Fibonacci fib = new Fibonacci();
    System.out.println("第5个斐波那契数：---> " + fib.CalculateFibonacci(5));
    System.out.println("第6个斐波那契数：---> " + fib.CalculateFibonacci(6));
    System.out.println("第7个斐波那契数：---> " + fib.CalculateFibonacci(7));
  }
}

JavaScript

class Fibonacci {
  calculateFibonacci(n) {
    let dp = new Array(n + 1).fill(0);
    return this.calculateFibonacciRecursive(dp, n);
  }

  calculateFibonacciRecursive(dp, n) {
    if (n < 2)
      return n;
    if (dp[n] === 0)
      dp[n] = this.calculateFibonacciRecursive(dp, n - 1) + this.calculateFibonacciRecursive(dp, n - 2);
    return dp[n];
  }

  static main() {
    let fib = new Fibonacci();
    console.log("第5个斐波那契数：---> " + fib.calculateFibonacci(5));
    console.log("第6个斐波那契数：---> " + fib.calculateFibonacci(6));
    console.log("第7个斐波那契数：---> " + fib.calculateFibonacci(7));
  }
}

Fibonacci.main();

Python

class Fibonacci:
    def calculateFibonacci(self, n):
        dp = [0] * (n + 1)
        return self.calculateFibonacciRecursive(dp, n)

    def calculateFibonacciRecursive(self, dp, n):
        if n < 2:
            return n
        if dp[n] == 0:
            dp[n] = self.calculateFibonacciRecursive(dp, n - 1) + self.calculateFibonacciRecursive(dp, n - 2)
        return dp[n]

    @staticmethod
    def main():
        fib = Fibonacci()
        print("第5个斐波那契数：--->", fib.calculateFibonacci(5))
        print("第6个斐波那契数：--->", fib.calculateFibonacci(6))
        print("第7个斐波那契数：--->", fib.calculateFibonacci(7))


Fibonacci.main()

Go

package main

import "fmt"

type Fibonacci struct{}

func (f Fibonacci) CalculateFibonacci(n int) int {
	dp := make([]int, n+1)
	return f.calculateFibonacciRecursive(dp, n)
}

func (f Fibonacci) calculateFibonacciRecursive(dp []int, n int) int {
	if n < 2 {
		return n
	}
	if dp[n] == 0 {
		dp[n] = f.calculateFibonacciRecursive(dp, n-1) + f.calculateFibonacciRecursive(dp, n-2)
	}
	return dp[n]
}

func main() {
	fib := Fibonacci{}
	fmt.Println("第5个斐波那契数：--->", fib.CalculateFibonacci(5))
	fmt.Println("第6个斐波那契数：--->", fib.CalculateFibonacci(6))
	fmt.Println("第7个斐波那契数：--->", fib.CalculateFibonacci(7))
}

自底向上

Java

class Fibonacci {

  public int CalculateFibonacci(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];
  }

  public static void main(String[] args) {
    Fibonacci fib = new Fibonacci();
    System.out.println("5th Fibonacci is ---> " + fib.CalculateFibonacci(5));
    System.out.println("6th Fibonacci is ---> " + fib.CalculateFibonacci(6));
    System.out.println("7th Fibonacci is ---> " + fib.CalculateFibonacci(7));
  }
}

JavaScript

class Fibonacci {
    calculateFibonacci(n) {
        if (n < 2)
            return n;

        const dp = new Array(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (let i = 2; i <= n; i++)
            dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
}

const fib = new Fibonacci();
console.log("5th Fibonacci is ---> " + fib.calculateFibonacci(5));
console.log("6th Fibonacci is ---> " + fib.calculateFibonacci(6));
console.log("7th Fibonacci is ---> " + fib.calculateFibonacci(7));

Python

class Fibonacci:
    def calculate_fibonacci(self, n):
        if n < 2:
            return n

        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]


fib = Fibonacci()
print("5th Fibonacci is --->", fib.calculate_fibonacci(5))
print("6th Fibonacci is --->", fib.calculate_fibonacci(6))
print("7th Fibonacci is --->", fib.calculate_fibonacci(7))

Go

package main

import "fmt"

type Fibonacci struct{}

func (f *Fibonacci) CalculateFibonacci(n int) int {
	if n < 2 {
		return n
	}

	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func main() {
	fib := Fibonacci{}
	fmt.Println("5th Fibonacci is --->", fib.CalculateFibonacci(5))
	fmt.Println("6th Fibonacci is --->", fib.CalculateFibonacci(6))
	fmt.Println("7th Fibonacci is --->", fib.CalculateFibonacci(7))
}