Re: [obm-l] mais uma!

["David Turchick" <davidturchick@xxxxxxxxxxx>]

Vc poderia me explicar como que vai de 5 p/ 25 em apenas um segundo? Devo 
estar interpretando o problema diferente, ou erroneamente.
Valeu,
David

>From: Vinicius José Fortuna <ra992559@ic.unicamp.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] mais uma!
>Date: Sat, 3 Aug 2002 15:01:59 -0300 (EST)
>
>On Sat, 3 Aug 2002, David Turchick wrote:
>
> > Para ir de 6 amebas para 25 amebas o mais rápido possível, vc pode tanto
> > fazer:
> > 6 -> 5 -> 4 -> 28 -> 27 -> 26 -> 25, como
> > 6 -> 30 -> 29 -> 28 -> 27 -> 26 -> 25, e ambas são feitas no menor tempo
> > possível. (Não provei, mas acho que dá p/ entender o que eu tô fazendo,
> > tendo pensado um pouquinho no problema. Caso contrário, diga.)
>
>Falso!
>De 6 para 25 é possível fazer:
>6 -> 5 -> 25
>
>Quanto ao problema original, esse exemplo mostra que multiplicar sempre
>por 7 e não utilizar outros valores pode não levar ao tempo mínimo.
>
>Ao meu ver entendi o problema pela seguite recorrência:
>
>T(1) = 0
>T(n) = min(T(n+1), min{2<=i<=7 e i divide n}(T(n/i))
>
>
>Como a minha área é programação, implementei um programa que encontrasse o
>valor de T(2000). Modelei o problema como caminho mínimo em um grafo
>orientado, onde os vértices são os números e as arestas (a,b) ligam
>vértices a e b se b=a-1 ou b=a*i, 2<=i<=7.
>
>O número de movimentos para chegar ao número n será a distância do 1 até
>o número.
>
>Assim, encontrei que a solúção mínima é de cinco movimentos, que podem
>ser:
>
>1 -> 4 -> 16 -> 80 -> 400 -> 2000
>
>Até mais
>
>Vinicius Fortuna
>Ciência da Computação - Unicamp
>
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================





=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================