Re: [obm-l] mais uma!

[Vinicius José Fortuna <ra992559@xxxxxxxxxxxxx>]

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>
=========================================================================