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" <[EMAIL PROTECTED]>
Reply-To: [email protected]
To: [email protected]
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, [EMAIL PROTECTED] 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
=========================================================================
