b) Tem um jeito melhor: comece testando ab,ac,bc. Se der errado, significa que tem (pelo menos) 2 ruins aqui, entao sobram 2n-3 baterias onde tem mais boas do que ruins... O que eh exatamente o item (a)! (Bom, trocando n por n-2). Entao pelo metodo da (a), conseguimos um par de baterias boas em (n-2)+2=n tentativas extra. Total: n+3 tentativas!
Agora, isso eh o otimo? Abraco, Ralph. On Sun, Feb 24, 2019 at 2:55 PM Ralph Teixeira <[email protected]> wrote: > Bom, tenho estrategias boas, mas tem que provar que sao otimas (ou arrumar > uma melhor): > > a) Faca n tentativas com 2 baterias cada, sem intersecao. Se nenhuma > dessas tentativas der certo, voce eh muito azarado e cada par tinha > exatamente uma bateria ruim. Bom, entao a bateria que nao foi testada tem > que ser boa -- tente-a com cada uma do ultimo par testado, vai ter que > funcionar. Total: n+2 tentativas. > > b) Idem ao de cima... Mas se apos n tentativas nao deu certo, tome os dois > ultimos pares (digamos, ab e cd) e tente as combinacoes com 1 bateria de > cada (digo: ac, ad, bc, bd). Uma dessas vai ter que funcionar. Total: n+4 > tentativas. > (Sinto um cheirinho de que esta aqui NAO eh otima.... Mas tem que pensar > mais.) > > Abraco, Ralph. > > On Sun, Feb 24, 2019 at 11:39 AM Jeferson Almir <[email protected]> > wrote: > >> Peço ajuda aos amigos da lista, sei que existe um problemas da obm >> "parecido", aguardo dicas ou soluções. Eu tentei formar um grafo de >> tentativas e penso como otimizar ele. >> >> a.) Existem 2n + 1 (n> 2) baterias. Não sabemos quais baterias são boas >> e quais são ruins, mas sabemos que o número de baterias boas é maior do que >> o número de baterias ruins. Uma lâmpada usa duas baterias e só funciona >> se ambas forem boas. Qual é o menor número de tentativas suficientes >> para fazer a lâmpada funcionar? >> >> b.) O mesmo problema, mas o número total de baterias é 2n (n> 2) e os >> números de baterias boas e ruins são iguais. >> >> >> >> -- >> 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.
