Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmic

Cunoaștem deja ce este acela Șirul lui Fibonacci, șir de numere descoperit de matematicianul Leonardo Pisano, unde fiecare element se definește în funcție de suma ultimilor doi. Astfel,

Ecuatie

Formal, se consideră că există și al 0-lea termen al șirului, cu valoarea 0:

Ecuatie

Există multe aplicații, în special în probleme de olimpiadă sau de concursuri, unde trebuie să determinăm eficient al n-lea termen al șirului. Metoda descrisă pentru clasa a IX-a, pe care am discutat-o în acest articol, generează brut toți termenii de dinainte pentru a putea găsi cel de-al n-lea termen, însă asta înseamnă că algoritmul brut face n pași și are astfel complexitatea O(n).

Din fericire însă, utilizând ridicarea la putere în timp logaritmic pe matrice, există o metodă de găsire a celui de-al n-lea termen din șirul Fibonacci cu complexitatea O(log n) (logaritmică). Deși înmulțirea matricelor se învață în clasa a XI-a la matematică, noțiunile discutate aici sunt foarte ușor de înțeles pentru orice clasă.

Metodă eficientă: matrice Fibonacci

Considerăm matricea (de la matematică) următoare:

Ecuatie

Am înlocuit valorile de 0 și de 1 cu termeni din șirul lui Fibonacci. Să vedem ce se întâmplă în continuare atunci când ridicăm matricea la puterea a 2-a:

Ecuatie

Vedem că matricea M2 conține termenii F1, F2 și F3. Vedem că M3 o să conțină termenii F2, F3 și F4:

Ecuatie

Prin urmare, găsim că, ridicând matricea noastră M la puterea n, generăm matricea:

Ecuatie

Matricea aceasta are pe a doua coloană a primei linii (și pe prima coloană a celei de-a doua linii) elementul Fn, pe care ni l-am dorit să îl generăm. Totodată, cum înmulțirea matricelor se poate realiza logaritmic, putem să adaptăm algoritmul și să generăm în O(log n) matricea noastră.

Al n-lea termen Fibonacci în timp logaritmic în C++

Atenție: termenii șirului Fibonacci ies foarte rapid din tipurile de date int și long long. De aceea, problemele care cer calcularea celui de-al n-lea termen Fibonacci de obicei cer modulo un număr prim, precum 666013 sau 1.000.000.007. În secvența de mai jos, am calculat termenii modulo 666013.

#include <iostream>

using namespace std;

int m[2][2], rasp[2][2], n;

//Functie care inmulteste matricea a cu b, punand rezultatul in a
void inmultireMatrice(int a[][2], int b[][2]) {
    int aa[2][2]; //Copie a lui a
    aa[0][0] = a[0][0]; aa[0][1] = a[0][1];
    aa[1][0] = a[1][0]; aa[1][1] = a[1][1];

    int bb[2][2]; //Copie a lui b
    bb[0][0] = b[0][0]; bb[0][1] = b[0][1];
    bb[1][0] = b[1][0]; bb[1][1] = b[1][1];

    a[0][0] = ((long long)aa[0][0] * bb[0][0] + aa[0][1] * bb[1][0]) % 666013;
    a[0][1] = ((long long)aa[0][0] * bb[0][1] + aa[0][1] * bb[1][1]) % 666013;
    a[1][0] = ((long long)aa[1][0] * bb[0][0] + aa[1][1] * bb[1][0]) % 666013;
    a[1][1] = ((long long)aa[1][0] * bb[0][1] + aa[1][1] * bb[1][1]) % 666013;
}

void ridicare(int n) {
    while(n > 0) {
        if(n % 2 == 1)
            inmultireMatrice(rasp, m);
        inmultireMatrice(m, m);
        n /= 2;
    }
}

int main()
{
    //Citim n
    cin >> n;

    //Matricea initiala
    m[0][0] = 1; m[0][1] = 1;
    m[1][0] = 1; m[1][1] = 0;

    //Matricea raspuns (initial este egala cu I2)
    rasp[0][0] = 1; rasp[0][1] = 0;
    rasp[1][0] = 0; rasp[1][1] = 1;

    //Ridicam matricea la puterea n
    ridicare(n);

    //Afisam cel de-al n-lea termen Fibonacci
    cout << rasp[0][1];
    return 0;
}

Bibliografie și alte resurse

Cuprinsul lecției

Se încarcă…

Citește și

Al N-lea termen Fibonacci în C++Instrucțiunea continue (structuri repetitive)Instrucțiunea de decizie în C++: if, else, switch, caseIndicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Complexitatea unui algoritm (timp și spațiu) în C++Suma numerelor naturale dintr-un interval dat în C++Cum să citești și să afișezi în fișiere în C++Bordarea unei matrice în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleFuncții predefinite în C++ (matematice, șiruri de caractere)Cea mai lungă secvență de elemente crescătoare în C++Maximul și minimul unui vector în C++Numărul de apariții al unui număr într-un vector în C++Vectori de frecvență (de apariții) în C++Inversarea unui șir de caractere în C++Afișarea elementelor unui vector recursiv în C++Ce înseamnă endl în C++?Suma elementelor unui vector recursiv în C++Do while vs while în C++ - Care e diferența?Codul ASCII (tabel complet)Verifică dacă trei puncte sunt coliniare C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Șiruri de caractere în C++. Tot ce trebuie să știiNumărul minim de peroane pentru o gară în C++Cel mai semnificativ bit în C++Al N-lea termen dintr-o progresie aritmeticăMaximul și minimul a trei valori în C++Aria și circumferința unui cerc în C++Numărul de cifre ale factorialului unui numărCum să afișezi partea întreagă a unui număr real în C++Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Interclasarea a doi vectori în C++Indicatorul lui Euler în C++Transformarea unui număr din baza 2 în baza 10 în C++Verificare dacă șir de caractere este palindrom în C++Ciurul lui Eratostene în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleInstrucțiunea do while (structuri repetitive)Cel mai frecvent element dintr-un șir în C++Instrucțiunea for (structuri repetitive)Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Numere triunghiulare. Verificarea unui număr triunghiularCe este o funcție void în C++?Verifică dacă un număr dat este o putere de 2 în C++Numărul permutărilor în C++ (formula permutărilor)Algoritm recursiv pentru căutare binară (clasa a X-a)Căutare binară în C++Câte numere naturale sunt într-un interval dat? (C++)Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăFactorialul unui număr în C++Numărul combinărilor în C++ (formula combinărilor)Instrucțiunea while (structuri repetitive)Verifică dacă un număr aparține șirului Fibonacci în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorMateria pentru olimpiada de informatică - tot ce trebuie să știiComentarii în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortDistanța dintre două puncte în C++Transformarea unei litere mici în literă mare în C++Pointer în C++. Variabile de tipul char * (char steluță)Cel mai puțin semnificativ bit în C++Ce înseamnă variabilă globală și locală în C++?Verifică dacă un caracter este cifră în C++Matrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicMaximul și minimul a n valori în C++Află secolul unui an citit de la tastatură în C++Tipul struct în C++. Ce sunt structurile de date neomogeneOglinditul unui număr în C++Radicalul unui număr în C++ (rădăcina pătrată)Verifică dacă un număr este par sau impar fără modulo în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Divide et Impera (metodă de programare C++)Suma 1 + 2 + 3 + ... + N în C++Valoarea absolută (modulul) unui număr în C++Aflarea sumei primelor N sume GaussMatrice pătratice în C++. Diagonala principală și secundarăTransformarea unei litere mari în literă mică în C++Ce este o variabilă unsigned în C++?Inversarea unui vector în C++CMMDC recursiv a două numere naturale în C++Verifică dacă un caracter este literă în C++Cifra maximă a unui număr recursiv în C++Transformarea unui număr din baza 10 în baza 2 în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Al N-lea termen dintr-o progresie geometricăVerifică dacă o literă este vocală în C++Verificarea unui an bisect în C++Instrucțiunea break (structuri repetitive)Oglinditul recursiv al unui număr în C++Generarea șirului Fibonacci generalizat în C++Funcții în C++. Ce sunt subprogrameleVectorii în C++: citire și afișareMediana unui șir de valori în C++Calculul combinărilor de n luate câte k (nCk) în C++Cifra de control a unui numărOperații cu numere mari în C++ - Toate funcțiile explicateVerificare dacă un număr este palindrom în C++Cifra maximă și minimă a unui număr în C++Citirea și afișarea matricelor în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Interschimbarea a două variabile în C++ (3 metode)Aria unui triunghi folosind coordonatele acestora în C++Citește un șir de caractere cu spații în C++Șirul lui Fibonacci în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleVectorii în C++: declarare și parcurgereVerificare număr prim în C++ (Clasa a IX-a)Numărul de divizori primi ai unui număr în C++Structuri repetitive (while, do while, for, etc)Maximul și minimul a două valori în C++Verifică dacă o literă este mică sau mare în C++Rădăcina cubică a unui număr în C++ (cube root)Prima cifră a unui număr în C++Suma divizorilor unui număr în C++Numărul de divizori al unui număr în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Cel mai mic număr cu suma cifrelor N în C++Recursivitate în C++Cum să calculezi instant 2 la puterea N în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Copiuțe: Cifrele unui numărAfișarea divizorilor primi ai unui număr în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont