Vai al contenuto principale

Informatica · Greedy

Termini del greedy di Fibonacci-Sylvester sulla frazione 5/121

L'algoritmo greedy di Fibonacci-Sylvester scompone una frazione a/b con 0 < a/b < 1 in somma di frazioni unitarie distinte: a ogni passo sottrae dal resto corrente la più grande frazione unitaria $\frac{1}{n}$ con $\frac{1}{n}$ ≤ resto, cioè $n = \lceil \frac{b}{a} \rceil$ se il resto è a/b, e ripete finché il resto diventa 0.
Applicando l'algoritmo alla frazione $\frac{5}{121}$, da quante frazioni unitarie è composta la scomposizione finale?

La tua risposta

Vanno bene sia 3,14 sia 3.14.