Ciąg Fibonaciego to ciąg liczb naturalnych określonych rekurencyjnie, gdzie kolejny wyraz ciągu jest wyrażony przez sumę poprzednich dwóch wyrazów.
Istnieją też ciągi wyższych stopni, na przykład: ciąg Tribonacciego, Tetranacciego, Pentanacciego, Hexanacciego itd. Różnią się jedynie ilością sumowanych poprzednich wyrazów ciągu.
Sumujemy trzy poprzednie wyrazy ciągu.
Sumujemy cztery poprzednie wyrazy ciągu.
Dowolny ciąg stopnia możemy wyrazić następująco:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
int fibonacci(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
return fibonacci(n - 2) + fibonacci(n - 1);
}
int tribonacci(int n) {
if(n == 0 || n == 1) return 0;
if(n == 2) return 1;
return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
}
int ogolny(int n, int k = 2) {
if(n < k - 1) return 0;
if(n == k - 1) return 1;
int suma = 0;
for(int i = k; i > 0; i--) {
suma += ogolny(n - i, k);
}
return suma;
}
int main() {
// Dla testu liczymy dziesiąte wyrazy ciągów
cout << "fibonacci(10) = " << fibonacci(10) << endl; // Ciąg Fibonacciego
cout << "tribonacci(10) = " << tribonacci(10) << endl; // Ciąg Tribonacciego
cout << "ogolny(10, 2) = " << ogolny(10, 2) << endl; // Ciąg Fibonacciego (wzór ogólny)
cout << "ogolny(10, 3) = " << ogolny(10, 3) << endl; // Ciąg Tribonacciego (wzór ogólny)
cout << "ogolny(10, 4) = " << ogolny(10, 4) << endl; // Ciąg Tetranacciego (wzór ogólny)
}
fibonacci(10) = 55
tribonacci(10) = 81
ogolny(10, 2) = 55
ogolny(10, 3) = 81
ogolny(10, 4) = 56