Olá pessoal! Desculpem a minha ausencia esses dias da lista pra responder às duvidas dos que responderam o meu e-mail inicial.
Ótima estratégia Ralph! Gostei bastente mesmo do seu método! Mas como você mesmo levantou a hipótese, será que da pra fazer com menos tentativas? Acho que não... pelos motivos citados pelo Maurício Acho que chegamos então que o mínimo são 5 tentativas.. Obrigado a todos! 2008/11/18 Ralph Teixeira <[EMAIL PROTECTED]>: > 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 >> ========================================================================= > > ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
