Considere o seguinte algoritmo: Dada a/b (acho q precisa ser entre 0 e 1), tome o menor n1 tal que 1/n1 <= a/b. Daí, tome o menor n2 tal que 1/n2 <= a/b - 1/n1. Daí tome o menor n3 tal que 1/n3 <= a/b - 1/n1 - 1/n2 Etc... Esse processo eventualmente para (quando uma desigualdade <= se torna uma igualdade), com: a/b = 1/n1 + 1/n2 + 1/n3 + ... + 1/nk, para algum k. Resta saber se produz uma fração egípcia (ou seja, se n1 < n2 < n3 < ...) e se a fração egípcia resultante é a menor possível. Vou pensar melhor é tentar simular alguns casos numa planilha.
Enviado do meu iPhone Em 3 de jul de 2019, à(s) 22:11, Bernardo Freitas Paulo da Costa <bernardo...@gmail.com> escreveu: > On Wed, Jul 3, 2019 at 8:34 PM Claudio Buffara > <claudio.buff...@gmail.com> wrote: >> Infinitas. >> Basta usar recursivamente a relação 1/n = 1/(n+1) + 1/(n(n+1)), que cada >> vez você obtém uma representação mais longa. >> 1/2 = 1/3 + 1/6 = 1/3 + 1/7 + 1/42 = 1/3 + 1/7 + 1/43 + 1/1806 = ... > > Mais difÃcil, talvez, seria calcular qual o menor número de termos > necessários para representar p/q :) Será que isso é NP completo? > > Abraços, > -- > Bernardo Freitas Paulo da Costa > > -- > Esta mensagem foi verificada pelo sistema de antivírus e > acredita-se estar livre de perigo. > > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > ========================================================================= -- Esta mensagem foi verificada pelo sistema de antiv�rus e acredita-se estar livre de perigo. ========================================================================= Instru��es para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
