← OlimpiApp
Medio
Informatica · Greedy
Denominatori prodotti dal greedy egiziano su 4/17
L'algoritmo greedy per le frazioni egiziane sottrae a ogni passo dal resto corrente la più grande frazione unitaria $\frac{1}{n}$ con $\frac{1}{n}$ ≤ resto (cioè n = ⌈denominatore/numeratore⌉ del resto), finché il resto è 0.
Quale sequenza di denominatori produce l'algoritmo sulla frazione $\frac{4}{17}$?