Boa tarde! Embora seja bastante óbvio. Só me apercebi agora. Para o caso b, quando nós chegamos ao pior caso com n testes, sem resultado. No algoritmo primordial. Pegava-se dois pares falhos e tínhamos + 4 chances. n+4. Depois o Ralph, o melhorou e caímos em n +3. O que havia reparado é que para tirar pelo menos n baterias defeituosas, pegando um conjunto de n+ 1 baterias, se faz necessário (n+1)*n/2 testes. O que dá uma relação número de testes : mínimo de n baterias defeituosas de (n+1)/2, o que dá uma melhor relação para pelo menos uma bateria, que dá 1. Para pelo menos duas, 3/2 e só vai piorando. Portanto, o método usado por Ralph, por sentimento não podia ser o melhor. Mas como melhorá-lo? Simples, por demais, embora só atinei agora. É só lembrar que quando somamos 4 a n, nós estamos desperdiçando dois testes que nós já o fizemos antes. Portanto para não esquecer: Separa-se 4 bateias e n-2 testes com as 2n-4 restantes. Ai se faz os 4 testes, no máximo com essas últimas. Teremos então n+2 igual ao resultado do item a)
Sds, PJMS Em dom, 24 de fev de 2019 às 19:10, Ralph Teixeira <ralp...@gmail.com> escreveu: > Provando que n+2 eh otimo no item (a): > > Suponha que voce arrumou um jeito de testar n+1 pares e garantir que > funciona. Vou mostrar que tah errado. > > Afinal, nos seus n+1 pares tem 2n+2 baterias, contando repeticoes. > Portanto, alguma das 2n+1 baterias aparece em (pelo menos) dois dos seus > pares. Marque essa bateria com a letra R e olhe para os OUTROS pares, fora > esses 2 (ou mais)... Destes n-1 (ou menos) pares, escolha uma bateria de > cada e marque com a letra R tambem (pode ser repetido se quiser). No final > das contas, marcamos com a letra R um total de 1+(n-1)=n baterias (ou > menos, se tiver repeticoes). Pois bem, se essas baterias fossem as ruins, > os seus pares NAO achariam uma combinacao boa, entao seu jeito nao GARANTE > que a lanterna vai acender. > > Agora falta mostrar que n+3 eh otimo para (b) -- ou arrumar um jeito > melhor. > > Abraco, Ralph. > > On Sun, Feb 24, 2019 at 6:49 PM Ralph Teixeira <ralp...@gmail.com> wrote: > >> Era n+2 para o item (a); o que eu falei ali foi um jeito de fazer em n+3 >> para o item (b), melhor que o n+4 que eu tinha falado antes. >> >> Abraco, Ralph. >> >> On Sun, Feb 24, 2019 at 5:14 PM Pedro José <petroc...@gmail.com> wrote: >> >>> Boa tarde! >>> Ralph, >>> também não sei se é ótimo. Postei a resposta para provocar. >>> Só que você afirmou ter um método melhor, mas não foi. Para a) com n+2 >>> estava garantido acender. Com o que você propôs podemos atingir n+3. Então >>> não foi melhor. >>> Ou talvez não tenha compreendido. >>> >>> Sds, >>> PJMS >>> >>> Em dom, 24 de fev de 2019 às 15:27, Pedro José <petroc...@gmail.com> >>> escreveu: >>> >>>> Boa tarde! >>>> a) Você pode ter n baterias com falha e n+1 sem estar em modo de falha. >>>> Seu pior caso é sempre pegar uma ruim e uma boa, pois aí você nem >>>> acende a lâmpada nem esgota rapidamente as em modo de falha. >>>> Quando você fizer n tentativas, a que sobrou é boa. >>>> E em cada lote tem uma boa e uma em falha. >>>> Você pode demorar duas se na primeira escolher a que está em modo de >>>> falha. Portanto, você poderá gastar n+2 tentativas no máximo. >>>> Isto é interpretando o problema da seguinte forma. qual o menor número >>>> de tentativas que garanta a funcionabilidade da lâmpada. Pois a >>>> lâmpada pode funcionar com apenas uma tentaiva. >>>> >>>> b) O pior caso é n tentativas. Sendo sempre uma ruim e uma boa. >>>> Pegando dois lotes temos três chances para não acender a lâmpada RB, BR >>>> e RR e uma para acender BB. Portanto, no pior caso teríamos n+4 tentativas. >>>> >>>> Creio que seja isso. >>>> Todavia, recomendaria um voltímetro. >>>> >>>> Sds, >>>> PJMS >>>> >>>> >>>> >>>> Em dom, 24 de fev de 2019 às 11:40, Jeferson Almir < >>>> jefersonram...@gmail.com> escreveu: >>>> >>>>> 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. >> >> > -- > 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.
