bom dia! Não sei onde vi que so precisam +4. Nada a ver. Em ter, 26 de fev de 2019 14:09, Pedro José <[email protected] escreveu:
> 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 <[email protected]> > 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 <[email protected]> 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é <[email protected]> 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é <[email protected]> >>>> 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 < >>>>> [email protected]> 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.
