Re: [obm-l] daria para criar um algoritmo???

["Paulo Santa Rita" <paulosantarita@xxxxxxxxxxx>]

Ola Vanderlei, Prof Nicolau e demais
colegas desta lista ... OBM-L,

Uma outra maneira de ver a mesma solucao sem precisar passar  para binario e 
partir do numero e "decompo-lo" usando as duas teclas. Assim :

1994 = 997*2=997B=(996 + 1)B=996AB=498BAB=249BBAB= 
=(248+1)BBAB=248ABBAB=124BABBAB=62BBABBAB=
=31BBBABBAB=(30+1)BBBABBAB=30ABBBABBAB=15BABBBABBAB=
=14ABABBBABBAB=7BABABBBABBAB=6ABABABBBABBAB=
=3BABABABBBABBAB=2ABABABABBBABBAB=1BABABABABBBABBAB=
=0ABABABABABBBABBAB

A sequencia e, portanto : ABABABABABBBABBAB

Como 2X+2 = 2(X+1) a seguencia BAA teclada para um dado numero qualquer no 
visor e equivalente a teclar AB. Isso implica um criterio de simplificacao, 
ou seja, uma condicao necessaria para que uma sequencia seja minima e que 
nao exista mais que uma letra A consecutiva apos uma letra B.

Exemplo 1 :

ABABAAAABBBBBA = ABA(BAA)AABBBBBA=ABA(AB)AABBBBBA=
=ABAA(BAA)BBBBBA=ABAA(AB)BBBBBA=ABAAABBBBBBA=
=A(BAA)ABBBBBBA=A(AB)ABBBBBBA=AABABBBBBBA

Evidentemente que e possivel gerar um algoritmo, inclusive bastante trivial. 
Ei-lo :

FUNCAO SEQUENCIAMINIMA(NUMERO)

SEQUENCIA =""
ENQUANDO NUMERO # 0

SE mod(NUMERO,2)=0

ENTAO  :
1) SEQUENCIA = "B" + SEQUENCIA
2) NUMERO = NUMERO / 2
SENAO :
1)SEQUENCIA = "A" + SEQUENCIA
2) NUMERO = NUMERO - 1

FIMSE
FIMENQUANTO

RETORNE SEQUENCIA

Esta funcao em pseudo-codigo e facilmente implementavel em qualquer 
linguagem, mesmo as nao procedurais. Ela recebe NUMERO e devolve
a sequencia minima. A variavel locall SEQUENCIA guarda o resultado 
pretendido e e o valor de retornado.

Um Abraco a Todos
Paulo Santa Rita
3,1204,250406

>From: "Nicolau C. Saldanha" <nicolau@mat.puc-rio.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] daria para criar um algoritmo???
>Date: Tue, 25 Apr 2006 09:21:34 -0300
>
>On Mon, Apr 24, 2006 at 01:46:44AM +0000, vandermath@brturbo.com.br wrote:
> > Um equipamento eletrônico consiste de um visor e de duas teclas A e B. 
>Ao
> > ligarmos o equipamento, aparece um zero no visor. Apertando-se a tecla 
>A, o
> > número que está no visor é aumentado de 1 unidade e apertando-se a 
>tecla B, o
> > número que está no visor é multiplicado por dois. Sejam x e y 
>respectivamente
> > as menores quantidades de vezes que devemos apertar as teclas A e B para
> > obter o número 1994.  Qual é o valor da diferença (y – x)?  Se o 
>número fosse
> > muito grande, daria para fazer de um modo fácil???
>
>Se você escrever tudo na base 2 o problema fica bem óbvio:
>a tecla B acrescenta um 0 no final. Por exemplo, 1994 é 11111001010 na 
>base 2.
>Ele pode ser obtido assim:
>
>   0
>A 1
>B 10
>A 11
>B 110
>A 111
>B 1110
>A 1111
>B 11110
>A 11111
>B 111110
>B 1111100
>B 11111000
>A 11111001
>B 111110010
>B 1111100100
>A 1111100101
>B 11111001010
>
>Assim, exceto pelo primeiro algarismo, para cada algarismo 0 apertamos B
>e para cada algarismo 1 apertamos B+A.
>
>[]s, N.

_________________________________________________________________
Facilite sua vida: Use o Windows Desktop Search e encontre qualquer arquivo 
ou e-mail em seu PC. Acesse:  http://desktop.msn.com.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
=========================================================================