Hm, primeiro precisamos deixar o enunciado mais preciso:
i) Eu preciso apenas DESCOBRIR a senha, ou preciso INSERI-LA no dispositivo?
ii) O dispositivo avisa quando a gente acerta a senha totalmente (acho que
o usual seria "sim")? Ou apenas diz "não"/"quase"?
iii) "Coincidente" significa digito correto na posição correta, ou apenas
"aparece em algum lugar da senha"?
iv) A priori, a senha pode ter dígitos repetidos (acho que o usual seria
"sim")?
v) A senha seria um CONJUNTO de 3 dígitos, ou a ordem importa (acho que o
usual seria "ordem importa")?
Para uma cota inferior (usualmente bem ruinzinha), tem uma ideia que
funciona em vários problemas deste tipo: qualquer algoritmo vai pegar uma
sequência de respostas do dispositivo (digamos, Q="quase", N="nao" e
A="acertou!") e traduzir isso numa possivel senha. Em outras palavras, por
mais complexo que seja o algoritmo, no final das contas ele "gera" uma
grande tabela, algo assim:
Se as respostas forem QQNQNQA, a senha vai ser 127;
Se as respostas forem NNQQNA, a senha vai ser 889;
...
e assim por diante. Por isso, se o número de sequências de letras for MENOR
que o número possivel de senhas, não tem como o algoritmo funcionar
GARANTIDAMENTE -- haverá senhas fora da tabela (ou sequências que levam a
mais de uma senha, evidenciando a falha do algoritmo nesses casos)!
Para ser um pouco mais concreto, vou supor 10^3 possíveis senhas (dígitos
ordenados, com repetição). Vou provar que, neste caso, um algoritmo com 9
tentativas NUNCA descobre a senha -- tem que ser pelo menos 10.
Duas outras observações interessantes:
a) Obviamente, se em algum momento seu algoritmo chega em A, PARE, você
achou a senha correta e **nenhuma das tentativas seguintes te
providencia nenhuma informação adicional**. Se você inventar um algoritmo
doido que continua tentando coisas depois do A, eu posso fazê-lo ficar MAIS
EFICIENTE retirando os passos adicionais; ou seja, fazendo todas as
sequências com terminarem nesse A;
b) Por outro lado, vou supor que você TEM QUE INSERIR a senha correta; ou
seja todas as sequências da sua "tabela" terminam em "A".
Assim, o número MÁXIMO de sequências de letras na sua tabela seria:
Comprimento 1: 1 sequência (a saber, "A")
Comprimento 2: 2 sequências (NA e QA)
Comprimento 3: 4 sequências (NNA, NQA, QNA, QQA)
...
Comprimento 9: 2^8=256 sequências
Total: 511 sequências ("máximo" pois, dependendo do algoritmo, talvez
algumas nunca ocorram). Como são 1000 possíveis senhas, é impossível seu
algoritmo distingui-las todas!
On Mon, Dec 13, 2021 at 10:00 AM Jeferson Almir <jefersonram...@gmail.com>
wrote:
> Amigos peço ajuda nessa questão.
>
> Tem uma senha de 3 digitos
> (Qualquer digito de 0 a 9)
> E nos temos um dispositivo
> Que compara a senha
> Com um número que escolhemos
> E retorna não se tem todos os digitos diferentes da senha
> E retorna quase se tem pelo menos 1 digito coincidente com a senha
> Qual é o menor numero de tentativas que precisamos usar esse dispositivo
> tal que podemos descobrir a senha com certeza, independente de qual ela
> seja?
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
