# 用x种方式求第n项斐波那契数，99%的人只会第一种

## 斐波那契数列

0、1、1、2、3、5、8、13、21、34…

F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n ≥ 3，n ∈ N*）

## 求第n项斐波那契数

```//Fibonacci Series using Recursion
#include<stdio.h>
int fib(int n) {
if (n <= 1)
return n;
return fib(n - 1) + fib(n - 2);
}

int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}```

```//Fibonacci Series using Dynamic Programming
#include<stdio.h>

int fib(int n) {
/* Declare an array to store Fibonacci numbers. */
int f[n + 1];
int i;

/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++) {
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i - 1] + f[i - 2];
}

return f[n];
}

int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}```

```// Fibonacci Series using Space Optimized Method
#include<stdio.h>
int fib(int n) {
int a = 0, b = 1, c, i;
if (n == 0)
return a;
for (i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}

int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}```

```//Fibonacci Series using Dynamic Programming
#include<stdio.h>

int fib(int n) {
/* Declare an array to store Fibonacci numbers. */
int f[3];       /* 只需定义一个长度为3的数组 */
int i;

/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;

for (i = 2; i <= n; i++) {
/* Add the previous 2 numbers in the series
and store it：注意下标要对3取模 */
f[i % 3] = f[(i - 1) % 3] + f[(i - 2) % 3];
}

return f[n % 3]; /* 这里要注意下标对3取模 */
}

int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}```

```#include <stdio.h>

/* Helper function that multiplies 2 matrices F and M of size 2*2, and puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);

/* Helper function that calculates F[][] raise to the power n and puts the result in F[][]。Note that this function is designed only for fib() and won't work as general power function */
void power(int F[2][2], int n);

int fib(int n) {
int F[2][2] = { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);

return F[0][0];
}

void multiply(int F[2][2], int M[2][2]) {
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

void power(int F[2][2], int n) {
int i;
int M[2][2] = { { 1, 1 }, { 1, 0 } };

// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}

/* Driver program to test above function */
int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}```

```#include <stdio.h>

void multiply(int F[2][2], int M[2][2]);

void power(int F[2][2], int n);

/* function that returns nth Fibonacci number */
int fib(int n) {
int F[2][2] = { { 1, 1 }, { 1, 0 } };
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}

/* Optimized version of power() in method 4 */
void power(int F[2][2], int n) {
if (n == 0 || n == 1)
return;
int M[2][2] = { { 1, 1 }, { 1, 0 } };

power(F, n / 2);
multiply(F, F);

if (n % 2 != 0)
multiply(F, M);
}

void multiply(int F[2][2], int M[2][2]) {
int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

/* Driver program to test above function */
int main() {
int n = 9;
printf("%d", fib(n));

return 0;
}```

#### 原文链接：原文来自个人公众号：C you again，欢迎关注

```// C++ Program to find n'th fibonacci Number in
// with O(Log n) arithmatic operations
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000;

// Create an array for memoization
int f[MAX] = { 0 };

// Returns n'th fuibonacci number using table f[]
int fib(int n) {
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);

// If fib(n) is already computed
if (f[n])
return f[n];

int k = (n & 1) ? (n + 1) / 2 : n / 2;

// Applyting above formula [Note value n&1 is 1
// if n is odd, else 0.
f[n] = (n & 1) ?
(fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) :
(2 * fib(k - 1) + fib(k)) * fib(k);

return f[n];
}

/* Driver program to test above function */
int main() {
int n = 9;
printf("%d ", fib(n));
return 0;
}```

Java提供了BigInteger类，可以很轻易地算出当n很大时的斐波那契数。

```// Java program to compute n-th Fibonacci number where n may be large.
import java.math.*;

public class Fibonacci {
// Returns n-th Fibonacci number
static BigInteger fib(int n) {
BigInteger a = BigInteger.valueOf(0);
BigInteger b = BigInteger.valueOf(1);
BigInteger c = BigInteger.valueOf(1);
for (int j = 2; j <= n; j++) {
a = b;
b = c;
}

return (a);
}

public static void main(String[] args) {
int n = 1000;
System.out.println("Fibonacci of " + n + "th term" + " " + "is" + " " + fib(n));
}
}```

0 条评论

• ### 浙大版《C语言程序设计（第3版）》题目集 习题5-4 使用函数求素数和

其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

• ### 浙大版《C语言程序设计（第3版）》题目集 习题6-2 使用函数求特殊a串数列和

给定两个均不超过9的正整数a和n，要求编写函数求a+aa+aaa++⋯+aa⋯a（n个a）之和。

• ### 浙大版《C语言程序设计（第3版）》题目集 习题4-6 水仙花数

水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

• ### 用x种方式求第n项斐波那契数，99%的人只会第一种

大家好啊，我们又见面了。听说有人想学数据结构与算法却不知道从何下手？那你就认真看完本篇文章，或许能从中找到方法与技巧。

• ### 策略模式(Strategy)

- 1.Strategy：策略接口，用来约束一系列具体的策略算法。Context使用这个接口来调用具体的策略，实现定义的策略。

• ### 在VS2010上使用C#调用非托管C++生成的DLL文件（图文讲解） 背景

背景      在项目过程中，有时候你需要调用非C#编写的DLL文件，尤其在使用一些第三方通讯组件的时候，通过C#来开发应用软件时，就需要利用DllImpor...

• ### pHash的Java实现

此算法中的DCT变换是从 http://blog.csdn.net/luoweifu/article/details/8214959抄过来的，因为这种需要大量的...

• ### hdu---（1280）前m大的数（计数排序）

前m大的数 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

• ### POJ 1804 Brainman(5种解法，好题，【暴力】，【归并排序】，【线段树单点更新】，【树状数组】，【平衡树】)

Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

• ### BZOJ 1083: [SCOI2005]繁忙的都市【Kruscal最小生成树裸题】

1083: [SCOI2005]繁忙的都市 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2925  Sol...