Se o objetivo eh minimizar o numero **maximo** de palpites... Certamente, eh
possivel adivinhar em um maximo de 5 palpites, usando a seguinte estrategia
de ir trocando um digito de cada vez (Pi=i-esimo palpite, Ri=i-esima
resposta):
P1=0000
P2=0001
P3=0011
P4=0111
Se a resposta "melhorou" ao passar de Pi para Pi+1, eh porque aquele digito
que voce trocou estah correto, e vice-versa. Ou seja, apos estes 4 palpites,
voce jah sabe os ultimos 3 digitos com certeza.
Agora basta olhar a resposta a P1 para descobrir se o digito incerto eh 0 ou
1; assim, o 5o palpite serah correto.
Exemplo:
R1=1, R2=2, R3=1 e R4=2.
Como R2>R1, o ultimo digito eh 1, isto eh, xxx1 (pois esta eh a unica
diferenca entre P1 e P2);
Como R3<R2, xx01.
Como R4>R3, x101.
Enfim, como R1=1, soh tem um 0 na resposta, entao 1101 eh a resposta.
Esta estrategia eh facilmente generalizavel: sempre eh possivel adivinhar um
numero de n bits com, no maximo, n+1 palpites (agora, serah que dah com
menos?).
Abraco,
Ralph
2008/11/18 Douglas Ribeiro Silva <[EMAIL PROTECTED]>
> O jogo dos 4 bits consiste no computador escolher um número de 4 bits
> e o usuário tentar adivinhar. Para cada palpite do usuário o
> computador retorna quantos bits ele acertou.
>
> Ex: o computador escolhe 0101
>
> Usuario: 0000
> PC:2
> Usuario: 0100
> PC: 3
> Usuario: 1111
> PC: 2
> Usuario: 0111
> PC: 1
> Usuario: 0101
> PC: 4
>
> Qual a melhor estratégia para o jogo? O jogador deve sempre trocar a
> quantidade de dígitos que o computador indicar? Qual a quantidade
> máxima que um usuário inteligente gastaria para acertar o numero?
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================
>
