Question

In pseudocode pana mâine dimineață

Answer 1

Răspuns:

Se calculeaza termenii sirului fibonacci pana la n

Se iau apoi pe rand, cel mai mare numar fibonacci care este mai mic decat n

(x), se ia apoi urmatorul numar fibonacci mai mic decat n - x (y). Conform teoremei, numarul ramas trebuie sa fie fibonacci

Raspunsul e: x, n - x, n - x - y

Explicație:

Teorema spune ca n = f1 + f2 + f3; f1, f2, f3 apartin fibonacci si nu sunt consecutive

f(x) este cel mai mare numar fibonacii < n

f(x) < n. Vom demonstra ca daca nu il alegem pe f(x), atunci nu il vom putea construi pe n

sa presupunem ca alegem celelalte treicele mai mari numere

f(x - 1), f(x - 3), f(x - 5) ( cum nu putem alege f(x-2/x-4) pentru ca ar fi 2 numere consecutive

Vom arata ca:

f(x) = f(x - 1) + f(x - 2) > f(x - 1) + f(x - 3) + f(x - 5)

     => f(x - 2) > f(x - 3) + f(x - 5)

f(x - 2) = f(x - 3) + f(x - 4)

      => f(x - 3) + f(x - 4) >  f(x - 3) + f(x - 5)

      => f(x - 4) > f(x - 5 ) ceea ce este adevarat

=> f(x) > f(x - 1) + f(x - 3) + f(x - 5)

=> Ne trebie f(x).

Analog pentru n - f(x) si tot asa