数学——斐波那契数¶
https://www.cnblogs.com/logeadd/p/9397856.html
斐波那契数（Fibonacci ）满足的数列性质是： $$ a_n = a {n - 1} + a{n - 2} $$ 通项公式为： $$ a_n = \frac{1}{\sqrt 5} \left[ \left( \frac{1 + \sqrt 5}{2} \right) ^ n - \left( \frac{1 - \sqrt 5}{2} \right) ^ n \right] \ a_1 = 1, a_2 = 1, n \geq 3, n \in \N^* $$
判断一个数是否是Fibonacci 数¶
判断是否是Fibonacci数存在一个O(1)的做法，设需要判断的数字为n，只需要去检验5n^2+4或5n^2-4是否是完全平方数即可。
典型题目如 GeeksForGeeks的 Check if the number is Fibonacci：https://practice.geeksforgeeks.org/problems/check-if-the-number-is-fibonacci/0
Check if a given number is Fibonacci number. Fibonacci number is a number which occurs in Fibonacci series.
Input: The first line of input contains an integer T denoting the number of test cases. Each test case contains a number.
Output: Print "Yes" if the entered number is Fibonacci number else "No".
Constraints: 1 <= t <= 100 1 <= n <= 100
Example:Input: 2 34 41 Output: Yes No
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstdio>
using namespace std;
bool isSquareNumber(int n)
{
int x = sqrt(n);
return x * x == n;
}
bool check(int n)
{
return isSquareNumber(5 * n * n + 4) || isSquareNumber(5 * n * n - 4);
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int caseNum;
cin >> caseNum;
while (caseNum--) {
int n;
cin >> n;
if (check(n)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
计算Fibonacci数¶
比如LeetCode 509 Fibonacci Number，LeetCode 1137.N-th Tribonacci Number。值得注意的是，利用通项公式求解并不会很快，因为计算两个n次的指数并连同根式，速度并不会很快。
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).
Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Note:
0 ≤ N ≤ 30.
通项公式法¶
求解数列通项公式可以采用： $$ a_n - \lambda a_{n -1 } = k(a_{n-1} - \lambda a_{n -2 }) $$ 解出k, \lambda即可求出通项公式。 $$ a_n = \frac{1}{\sqrt 5} \left[ \left( \frac{1 + \sqrt 5}{2} \right) ^ n - \left( \frac{1 - \sqrt 5}{2} \right) ^ n \right] \ a_1 = 1, a_2 = 1, n \geq 3, n \in \N^* $$
#include <cmath>
class Solution {
public:
int fib(int N) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 1/sqrt(5) * (pow((1 + sqrt(5)) / (2), N) - pow((1 - sqrt(5)) / (2), N));
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Fibonacci Number.
Memory Usage: 7.7 MB, less than 100.00% of C++ online submissions for Fibonacci Number.
打表法¶
因为N不超过30，所以完全可以写出前30项，实现O(1)的访问。
class Solution {
public:
int fib(int N) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> fibs{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040};
return fibs[N];
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Fibonacci Number.
Memory Usage: 7.6 MB, less than 100.00% of C++ online submissions for Fibonacci Number.
迭代法¶
考虑其通项公式，当前项至于与其相邻的前两项有关，所以可以采用两个临时变量来存储结果。
class Solution {
public:
int fib(int N) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (N == 0) return 0;
if (N == 1) return 1;
int pre = 0, cur = 1;
for (int i = 2; i <= N; ++i) {
int tmp = pre + cur;
pre = cur;
cur = tmp;
}
return cur;
}
};
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Fibonacci Number.
Memory Usage: 7.7 MB, less than 100.00% of C++ online submissions for Fibonacci Number.
矩阵快速幂¶
假设有矩阵2*2矩阵A，满足下面的等式： $$ A *\left[\begin{array}{c} f(n-1) \ f(n-2) \end{array}\right]=\left[\begin{array}{c} f(n) \ f(n-1) \end{array}\right]=\left[\begin{array}{c} f(n-1)+f(n-2) \ f(n-1) \end{array}\right] $$ 可以得到矩阵A： $$ A=\left[\begin{array}{ll} 1 & 1 \ 1 & 0 \end{array}\right] $$ 因此也就可以得到下面的矩阵等式： $$ \left[\begin{array}{ll} 1 & 1 \ 1 & 0 \end{array}\right]^{n-1} *\left[\begin{array}{l} f(1) \ f(0) \end{array}\right]=\left[\begin{array}{c} f(n) \ f(n-1) \end{array}\right] $$
class Solution {
public:
struct Matrix {
int a11, a12, a21, a22;
};
Matrix mul(Matrix m1, Matrix m2) {
return {
m1.a11 * m2.a11 + m1.a12 * m2.a21, m1.a11 * m2.a12 + m1.a12 * m2.a22,
m1.a21 * m2.a11 + m1.a22 * m2.a21, m1.a21 * m2.a12 + m1.a22 *m2.a22
};
}
Matrix pow(Matrix m, int n) {
if(n == 0) return {
1, 0,
0, 1
};
auto temp = pow(m, n / 2);
temp = mul(temp, temp);
if(n % 2) temp = mul(temp, m);
return temp;
}
int Fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
Matrix m = {
0, 1,
1, 1
};
auto temp = pow(m, n - 1);
return temp.a22;
}
};
计算AVL树的结点高度¶
证明：一颗有N个节点的AVL树，它的高度H小于等于1.44log(N+1)-0.328
设S_H是高度为H的最小规模的AVL树，一颗高为H的最小规模的AVL树必须有一颗高度为H-1的子树和一颗高度为H-2的子树，所以可以用递归公式表示： $$ S_{H}=\left{\begin{array}{l}{1 \quad \quad 当H=0} \ {2 \quad \quad 当H=1} \ {S_{H-1}+S_{H-2}+1 \quad \quad 当H \geq 2}\end{array}\right. $$ 比较S_H与Fibonacci数： $$ F_{i}=\left{\begin{array}{l}{1 \quad \quad当i = 0}\ {1\quad \quad 当i=1} \ {F_{i-1}+F_{i-2}\quad \quad当i\geq 2}\end{array}\right. $$ 易知S_{H}=F_{k+2}-1，可知： $$ S_{H}=\left[\left(\frac{1+\sqrt{5}}{2}\right){n+2}-\left(\frac{1-\sqrt{5}}{2}\right){n+2}\right] \times \frac{\sqrt{5}}{5}-1 $$ 因为\frac{1-\sqrt{5}}{2} = -0.618， 当H\geq3时，|\frac{1-\sqrt{5}}{2}|<0.09，所以 $$ S_H = \left[\left(\frac{1+\sqrt{5}}{2}\right){n+2}-\left(\frac{1-\sqrt{5}}{2}\right){n+2}\right] \times \frac{\sqrt{5}}{5}-1 \approx \frac{\sqrt{5}}{5} \times\left(\frac{1+\sqrt{5}}{2}\right)^{n+2}-1 $$ 如果有N个节点的AVL树，则： $$ N \geqslant \frac{\sqrt{5}}{5} \times\left(\frac{1+\sqrt{5}}{2}\right)^{H+2}-1 $$ 所以可得： $$ H+2 \leqslant \log _{\frac{1}{2}}[\sqrt{5}(N+1)] \leqslant \log _{\frac{1}{2}} \sqrt{5}+\log _{\frac{1}{2}}+\sqrt{5}(N+1) $$ 整理后得到： $$ \begin{aligned} H & \leqslant \frac{\log _{2}(N+1)}{\log _{2} \frac{1+\sqrt{5}}{2}}+\log _{\frac{1+\sqrt{5}}{2}} \sqrt{5}-2 \ &=\frac{\log _{2}(N+1)}{0.6942}+1.6723-2 \ &=1.44 \log _{2}(N+1)-0.328 \end{aligned} $$ 所以在最坏情况下，AVL树的高度至多比满二又树的高度增加44%。由此可见，AVL树中所有操作的最坏情况下的时间复杂度都是对数级的。