Fibonacci-elemek

Írjon programot, amely segít eldönteni egy számsorozat elemeiről, hogy azok a Fibonacci-sorozat elemei-e!

A Fibonacci-sorozatot a következőképpen definiáljuk:

    F₁ = 1,
    F₂ = 1,
    F_n = F_n – 1 + F_n – 2, ha n > 2,

azaz a sorozat minden eleme – az első két elem kivételével – az előző két elem összegeként számítható ki.

A bemenet több sorból áll. Minden sor egész számokat tartalmaz; amennyiben többet is, akkor őket a soron belül pontosan egy szóköz karakter választja el egymástól. A sor első száma (n) a vizsgálandó számok darabszámát adja meg. A bemenet végét egy olyan sor jelzi, ahol n = 0. A programjának az egyes sorokban található további n darab számról kell eldöntenie, hogy elemei-e a Fibonacci-sorozatnak. A további számok olyan pozitív egészek, amelyeknek az értéke nem haladja meg a 100 000-et.

Segítségképpen megemlítjük, hogy a fenti képlettel definiált Fibonacci-sorozat első 25 elemének az értéke nem haladja meg a 100 000-et, a 26. elem értéke már meghaladja azt.

A programja minden sor esetén írjon a standard kimenetre egy „YES” szót, ha a sorban megvizsgált számok mindegyike eleme a Fibonacci-sorozatnak, illetve egy „NO” szót, ha van olyan szám a megvizsgált számok között, amelyik nem eleme a Fibonacci-sorozatnak!

Példa bemenet

1. 1 1
2. 12 2 5 13 34 89 233 610 1597 4181 10946 28657 75025
3. 12 1 3 8 21 55 144 377 987 2584 6765 17711 46368
4. 3 1 8 5
5. 1 4
6. 5 1 2 3 4 5
7. 6 1 10 100 1000 10000 100000
8. 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. YES
2. YES
3. YES
4. YES
5. NO
6. NO
7. NO

letöltés szöveges állományként