K-ta liczba ciągu Fibonacciego

Question

Witam. Jak znaleźć k-tą liczbę ciągu Fibonacciego?

Comments

Całkiem szybko można wyznaczyć to za pomocą potęgowania macierzy, mianowicie:

---

A jakiś kawałek kodu? Szczerze nie słyszałem jeszcze o potęgowaniu macierzy

---

Od biedy:

#include <bits/stdc++.h>

struct Matrix22u {
	Matrix22u(uint64_t fill = 1) {
		for(uint64_t i = 0; i < 2; ++i) {
			for(uint64_t j = 0; j < 2; ++j) {
				data[i][j] = fill;
			}
		}
	}

	Matrix22u operator*(const Matrix22u& rhs) const {
		Matrix22u result(0);

		for(int32_t i = 0; i < 2; ++i) {
			for(int32_t j = 0; j < 2; ++j) {
				for(int32_t k = 0; k < 2; ++k) {
					result.data[i][j] += data[i][k] * rhs.data[k][j];
				}
			}
		}

		return result;
	}

	Matrix22u pow(uint64_t power) {
		if(power == 1) {
			return *this;
		}

		Matrix22u tmp = pow(power/2);
		tmp = tmp * tmp;

		return power % 2 ? tmp * (*this) : tmp;
	}

	uint64_t data[2][2];
};

uint64_t kth_fib(uint64_t k) {
	Matrix22u tmp(1);
	tmp.data[1][1] = 0;

	tmp = tmp.pow(k+1);
	return tmp.data[1][1];
}

int main(void) {
	for(uint64_t i = 0; i < 100; ++i) {
		std::cout << kth_fib(i) << " ";
	}
	std::cout << std::endl;
	return 0;
}

 

Answer 1

Możesz zacząć od pierwszej liczby i do każdej kolejnej, dodawać dwie poprzednie.

Albo rekurencyjnie i zacząć od ostatniej. return fibb(current-1) + fibb(current-2);