劍指Offer面試題10.I——斐波那契數列

斐波那契數列

• 題目
• C++
• Java
• Python
• Go

題目

寫一個函數，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項（即 F(N)）。斐波那契數列的定義如下：

F(0) = 0, F(1) = 1

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

斐波那契數列由 0 和 1 開始，之後的斐波那契數就是由之前的兩數相加而得出。

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請傳回 1。

示例 1：

輸入：n = 2

輸出：1

示例 2：

輸入：n = 5

輸出：5

提示：

0 <= n <= 100

C++

#include <iostream>
using namespace std;

int fib(int n){
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int tmp = (a + b) % 1000000007;
        a = b;
        b = tmp;
    }
    return a;
}


int main(){
    cout<<fib(47)<<endl;
    system("pause");
    return 0;
}
           

Java

package offertenfirst;


public class offertenfirst{
    public static int fib(int n){
        int a = 0, b = 1;
        for(int i = 0; i < n; i++){
            int tmp = (a + b) % 1000000007;
            a = b;
            b = tmp;
        }
        return a;
    }
    public static void main(String[] args) {
        System.out.println(fib(47));
    }
}
           

Python

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a % 1000000007

print(fib(47))

           

Go

package main

import "fmt"

func fib(n int) int {
	a, b := 0, 1
	for i := 0; i < n; i++ {
		a, b = b, (a+b) % 1000000007
	}
	return a 
}

func main() {
	fmt.Println(fib(95))
}