Алгоритм Фибоначчи — разделяй и властвуй
#include <iostream>
using namespace std;
int main() {
int i=1;
int j=0;
int k=0;
int h=1;
int t=0;
int n;
cin>>n;
while (n) {
if (n%2) {
t=j*h;
j=i*h+j*k+t;
i=ik+t;
}
t=h*h;
h=2*k*h+t;
k=k*k+t;
n=n/2;
}
cout<<j;
return 0;
}
Это самый быстрый алгоритм Фибоначчи, который я нашел в интернете. Другие алгоритмы, которые я понимаю, но этот не имеет никакого смысла для меня.
Я не вижу, как этот алгоритм связан с умножением матриц или возведением в степень путем возведения в квадрат. Может кто-нибудь объяснить?
Решение
Это стандартный матричный метод для вычисления чисел Фибоначчи. Переменные h, i, j и k являются четырьмя элементами матрицы. Матричная арифметика выписана «от руки».
Другие решения
Матричное решение состоит в том, чтобы взять матрицу
1 1
0 1
И поднимите его до степени, равной нужному числу Фибоначчи. Вы можете сделать это, используя log (n) шагов. Вы используете двоичный формат власти. На каждом шаге вы умножаете матрицу на себя (эквивалентно умножению показателя степени на 2) и умножаете на исходную матрицу, если бит равен 1 (эквивалентно добавлению 1 к показателю степени).
Теперь проверьте еще раз код. Переменные кодируют 4 ячейки в матрице, и есть некоторая вставка логики умножения, но она все та же.