斐波那契数列
斐波那契数列
题目
写一个函数来计算第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
题解
递归
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));
}
}
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();
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()
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))
}
自顶向下(备忘录)
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));
}
}
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();
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()
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))
}
自底向上
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));
}
}
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));
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))
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))
}