Ainda pergunto: o computador retorna quantos bits estão certos ou quantos bits estão certos nas posicoes certas? Por exemplo. Se o computador escolhe 0001
Eu chuto 1000 Ele me retorna 4 (3 zeros e 1 um) ou 2 (apenas 2 zeros na posicao correta)? Isso faz toda a diferença e não ficou claro no enunciado. 2008/11/18 Maurício Collares <[EMAIL PROTECTED]> > Não existe maneira de fazer só com 4 tentativas. Suponha que o > computador pode prever o que você vai falar (isso não é nada irreal, > pois se o computador escolhe os bits aleatoriamente e uniformemente, a > chance de ele escolher o correspondente a "adivinhar" é não nula). > Você tenta "0001" e o computador, só de maldade, responde "1". Você > não sabe qual dos 4 dígitos está errado, mas o fato é que você só tem > mais três tentativas pra acertar segundo sua conjectura: > > * Se você tentar mudar apenas um dígito por tentativa (em relação a > combinação original), o computador adivinha qual dígito você não > tentou e escolhe ele como o errado, de modo que você só vai poder > acertar de quinta. > * Se você mudar mais de um dígito em uma das três tentativas que > sobrou e, por consequencia disso, conseguir mudar todos os dígitos (se > não mudar todos, faz a mesma coisa que no caso anterior), você vai ter > dois dígitos que sempre são mudados juntos em relação a configuração > original. Então o computador adivinha qual par sempre é testado > conjuntamente e escolhe um elemento do par como errado. Então, em > todas as tentativas, ou você não muda o dígito errado, ou muda o > dígito errado pra um dígito certo e muda um dígito certo pra um dígito > errado. > > Segue-se que, no pior caso, 4 lances não bastam. É fácil fazer com 6 > lances (basta tentar uma configuração inicial qualquer e mudar os bits > um por um para conseguir informação sobre eles: em cinco lances, vc > tem toda a informação necessária, e aí dá pra acertar no sexto), mas > não pensei como fazer pra provar que dá (ou que não dá) pra fazer com > cinco. > > -- > Abraços, > Maurício > > 2008/11/18 Felipe <[EMAIL PROTECTED]>: > > por entropia deveria ser -log_2 ^(1/(2^4))=log_2^(2^4)=4 bits > > certo? > > > > 1a-q tal poe sem perda de generalidade 0000 > > descobre que sao 2 zeros e 2 uns (2 acertos) > > 2a-depois poe 0111 (3 acertos) > > 3a- 0001 > > 4a- > > > > ah fiz rapido , alguem deve achar uma maneira de no máximo 4. > > > > > > > > 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 > ========================================================================= >