Re: [obm-l] A torre de han�i

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] A torre de han�i

Tambem dah pra provar que 2^n - 1 eh o menor numero de movimentos necessario.

on 09.04.05 15:48, Bruno Fran�a dos Reis at bfreis@gmail.com wrote:

> Se n = 1, vale a propriedade. Supondo v�lida para n, provemos a validade para n+1.
> Para transferir n+1 discos para o suporte B usando C de auxiliar, transfira n discos para o suporte C usando B como auxiliar, depois transfira 1 disco (o ultimo) de A para B, e ent�o transfira n discos de C para B, usando A como auxiliar. Isso nos d�:
> n, A->C: 2^n - 1
> 1, A->B: 1
> n, C->B: 2^n - 1
> total: 2^n - 1 + 1 + 2^n - 1 = 2^n + 2^n - 1 = 2*2^n - 1 = 2^(n+1) - 1, q.e.d.
>
> Abra�o!
> Bruno
>
>
> On 4/9/05, Fernando <goianinho_@terra.com.br> wrote:
> > S�o dados tr�s suportes A, B e C. No suporte A est�o encaixados n 
> >
> > discos cujos di�metros, de baixo para cima, est�o em ordem estritamente decrescente. 
> >
> > Mostre que � poss�vel, com 2^n  � 1 movimentos, transferir todos os discos para o suporte 
> >
> > B, usando o suporte C como auxiliar, de modo que jamais, durante a opera��o, um disco 
> >
> > maior fique sobre um disco menor. 
> >
> > Desde jah grato, []'s