求Fibonacci数的几种方法[转载]
本文共 1437 字，大约阅读时间需要 4 分钟。
原文见
先给出Fibonacci的定义：
简单地总结了下，至少有5中方法来求Fibonacci(n)。
- 直接带公式
- 简单递归
- 循环
- 改进的递归
- 使用矩阵
这里主要介绍下如何用矩阵来求F(n)。
直接公式
简单递归
- int Fibonacci(int n)
- {
- if (1 >= n) return n;
- else return Fibonacci(n – 1) + Fibonacci(n – 2);
- }
循环
- int Fibonacci(int n)
- {
- int fib_n1 = 0, fib_n2 = 1;
- int fib_n;
- if (n <= 1) return n;
- for (int i = 2; i <= n; ++i) {
- fib_n = fib_n1 + fib_n2;
- fib_n1 = fib_n2;
- fib_n2 = fib_n;
- }
- return fib_n;
- }
改进的递归
- vector<int> fibonacci;
- int Fibonacci(int n)
- {
- if (1 >= n) return n;
- if (fibonacci.size() < n+1) fibonacci.resize(n+1, 0);
- if (0 == fibonacci[n]) {
- if (0 == fibonacci[n-1]) fibonacci[n-1] = Fibonacci(n-1);
- fibonacci[n] = fibonacci[n - 1] + fibonacci[n - 2];
- }
- return fibonacci[n];
- }
使用矩阵
首先，我们要构造出一个合适的矩阵运算式。下面是其中一种选择方案：
很显然，这是一个递归定义式。我们可以进一步进行转化。
我们可以看到，F(n)事实上就等于上述公式中第二个矩阵n-1次幂后下标为(0,0)的元素值。现在的问题转化到如何快速地求解矩阵的幂运算。可以参考之前的一篇Blog：。那么我们可以设计一个快速的矩阵幂运算实现方式。
- void Power(int base[][2], unsigned exponent, int res[][2])
- {
- int tempBase[2][2];
- memcpy(tempBase, base, sizeof(tempBase));
- int e[2][2] = { {1, 0},{0, 1}};
- while (exponent) {
- while (!(exponent & 1)) {
- Square(tempBase);
- exponent >>= 1;
- }
- --exponent;
- Product(e, tempBase);
- }
- memcpy(res, e, sizeof(e));
- }
其中的Square和Product函数很好实现。那么，求解斐波那契的矩阵实现可以写成：
- int Fibonacci(int n)
- {
- if (1 >= n) return n;
- int baseCoefficient[2][2] = { {1, 1}, {1, 0}};
- int finalCoefficient[2][2];
- Power(baseCoefficient, n - 1, finalCoefficient);
- return finalCoefficient[0][0];
- }
关于上面介绍的矩阵运算，可以很好的运用到和。参考解答可以在和找到。
你可能感兴趣的文章
【一天一道LeetCode】#76. Minimum Window Substring
查看>>
【计算机网络 第五版】阅读笔记之一：概述
查看>>
【计算机网络 第五版】阅读笔记之二：物理层
查看>>
【一天一道LeetCode】#83. Remove Duplicates from Sorted List
查看>>
【一天一道LeetCode】#91. Decode Ways
查看>>
【一天一道LeetCode】#92. Reverse Linked List II
查看>>
【一天一道LeetCode】#93. Restore IP Addresses
查看>>
【一天一道LeetCode】#94. Binary Tree Inorder Traversal
查看>>
【一天一道LeetCode】#113. Path Sum II
查看>>
【一天一道LeetCode】#114. Flatten Binary Tree to Linked List
查看>>
【unix网络编程第三版】阅读笔记（二）：套接字编程简介
查看>>
【一天一道LeetCode】#115. Distinct Subsequences
查看>>
【一天一道LeetCode】#116. Populating Next Right Pointers in Each Node
查看>>
【一天一道LeetCode】#117. Populating Next Right Pointers in Each Node II
查看>>
【一天一道LeetCode】#118. Pascal's Triangle
查看>>
【一天一道LeetCode】#119. Pascal's Triangle II
查看>>
【unix网络编程第三版】ubuntu端口占用问题
查看>>
【一天一道LeetCode】#120. Triangle
查看>>
【unix网络编程第三版】阅读笔记（三）：基本套接字编程
查看>>
同步与异步的区别
查看>>