#255 · Subiectul II · Programare

Verifică dacă două numere sunt termeni consecutivi în șirul lui Fibonacci

✓ Rezolvare explicatăTeleorman 2026 · nr. 15

Enunț

Scrieți un program care citește de la tastatură două numere naturale a și b, 1 ≤ a ≤ b ≤ 32000, și care verifică dacă aceste numere sunt termeni consecutivi în șirul lui Fibonacci, afișând un mesaj corespunzător.

Exemple

Date de intrare	Date de ieșire	Explicații
`8 13`	`DA`	8 și 13 sunt vecini în șir: …, 5, 8, 13, 21, …
`8 21`	`NU`	Ambele sunt termeni Fibonacci, dar între ele e 13
`1 1`	`DA`	Primii doi termeni ai șirului
`2 2`	`NU`	2 apare o singură dată în șir

Ultimele două exemple sunt construite și verificate de mână; primele două sunt cele oficiale. Mesajul nu e impus de subiect, am ales DA / NU ca în exemplu.

Rezolvare

C++

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int x = 1, y = 1;               // doi termeni consecutivi
    while (y < b) {                 // avansam pana cand y ajunge la b sau il depaseste
        int urm = x + y;
        x = y;
        y = urm;
    }

    if (x == a && y == b)
        cout << "DA";
    else
        cout << "NU";
    return 0;
}

Cum funcționează

Avansarea perechii (x, y) e exact cea explicată pe larg la primii n termeni Fibonacci. Ce e nou aici: nu știi câți termeni ai nevoie, deci bucla nu e for cu număr fix de pași, ci while cu o condiție de oprire.

Te oprești la prima pereche în care y ≥ b. În acel moment, y e cel mai mic termen Fibonacci care nu e mai mic decât b, iar x e chiar termenul dinaintea lui. Rămâne o singură comparație: perechea la care te-ai oprit e exact (a, b)?

Trasare pentru a = 8, b = 21:

`x`	`y`	`y < 21`?
1	1	da
1	2	da
2	3	da
3	5	da
5	8	da
8	13	da
13	21	nu → stop

Perechea finală e (13, 21), nu (8, 21) → NU. Pentru a = 8, b = 13 bucla se oprește la (8, 13) → DA.

De ce int ajunge aici: bucla se oprește imediat ce y trece de b ≤ 32000, deci cea mai mare valoare atinsă e 46368.

Cazul 1 1 e capcana enunțului: 1 apare de două ori la începutul șirului. Cu x = y = 1 la start, bucla nici nu pornește, perechea (1, 1) se recunoaște direct, iar 1 2 se recunoaște la primul pas. Ambele sunt perechi consecutive în ambele convenții (0, 1, 1, 2… sau 1, 1, 2…), deci aici convenția nu schimbă răspunsul.

Greșeli frecvente

Verificarea separată „a e Fibonacci” și „b e Fibonacci” — 8 21 ar da DA, deși între ele e 13. Trebuie verificat că sunt vecini, nu doar că aparțin șirului.
while (y <= b) — bucla trece de perechea căutată: pentru 8 13 se oprește la (13, 21) și răspunde NU.
Doar y == b la final, fără x == a — orice a împreună cu b = 13 ar da DA.
Generarea a „suficient de mulți” termeni într-un vector de 20 — al 20-lea termen e 6765, deci perechea (17711, 28657) nu mai e găsită. Bucla cu oprire pe valoare nu are nevoie de nicio estimare.

Exersează mai departe

Probleme cu aceeași tehnică

#073ProgramareSă se afişeze primii n termeni ai şirului lui Fibonacci #173ProgramareMatrice completată cu termeni din șirul lui Fibonacci #247ProgramarePrimii n termeni ai șirului 1, 1 2, 1 2 3, … (șir format din grupe)#253ProgramareAl n-lea termen al șirului 1, 2, …, 9, 11, 22, …, 99, 111, …#302ProgramarePrimii n termeni ai șirului lui Fibonacci, separați prin virgulă #582ProgramareMedia numerelor prime din șirul lui Fibonacci aflate într-o matrice (fibo și divprim)