Valeu, Ralph... Agora sim, são 22... será que ainda dá pra baixar mais? Depois vou tentar mais um pouco. Abraços e obrigado pela correção.
Hugo. Em 16 de janeiro de 2012 22:31, Ralph Teixeira <[email protected]> escreveu: > ---------- Forwarded message ---------- > From: Ralph Teixeira <[email protected]> > Date: 2012/1/16 > Subject: RE: [obm-l] Quantidade mínnima de tentativas > To: [email protected] > > > Hugo, nao desanime! Com um pequeno ajuste, sua solucao ainda dah 22 testes! > > (Eu tinha mandado isso para a lista, mas acho que foi barrado por > causa de um anexo) > > Chutei o balde: coloquei as 70 opções para as 4 pilhas boas numa > planilha Excel, em ordem lexicográfica, para ver bem o que está > acontecendo. A cada passo, cobri as opções com os testes do Hugo > usando cores bonitinhas (mando a planilha por E-mail para quem quiser, > ajuda pacas a ver o que estamos fazendo). > Então percebi algumas coisas na solução do Hugo... Resumindo > cripticamente: > > 1. ABC e FGH (2 testes, eliminando 10 opções) > 2a. (D ou E) com todos os pares em ABC (6t, -21op) > 2b. (D ou E) com todos ou FGH (6t, -21op) > 3a. ABE, BDE, CDE (2t, -9op) > 3b. ABF, ABG (2t, -3op) > 4. CFG, CFH, +CGH (-3t, -6op) > Total: 22 testes, 70 opções. > > Note algo interessante: retirei ABH do passo 3b! Afinal, se ABH fosse > bom, as pilhas boas seriam ABCH, ABDH, ABEH, ABFH ou ABGH. Mas em cada > um desses casos, já teríamos uma combinação boa (respectivamente, em > 1, 2a, 2a, 3b, 3b). Então ABH é desnecessário! > > Por outro lado, adicionei CGH no passo 4. O motivo é que a solução do > Hugo não cobria os casos ACGH e BCGH, pelo menos não que eu tenha > visto. > > Ou seja, deu 22 testes! Alguém dá menos? > > Abraço, > Ralph > > 2012/1/16 Hugo Fernando Marques Fernandes <[email protected]>: > > Fiz assim: > > > > Considere três grupos: abc, de, fgh > > > > Testo o primeiro grupo (abc): se falhar este grupo tem 1 ou 2 pilhas > boas. > > Testo o terceiro grupo (fgh): se falhar este grupo tem 1 ou 2 pilhas > boas. > > > > Testo cada elemento do segundo grupo contra os pares formados pelos > > elementos dos outros grupos. São 12 testes, a saber: > > abd, acd, bcd, abe, ace, bce > > e tb fgd, fhd, ghd, fge, fhe, ghe > > > > Note que o segundo grupo (de) pode ter 0, 1 ou 2 pilhas boas. > > 1) Se tiver 0 então existe duas boas no grupo (abc) e duas boas em (fgh) > > 2) Se tiver 1 boa, então um dos grupos (abc) ou (fgh) tem duas boas (e o > > outro uma). Nesse caso, um dos doze testes acima teria funcionado. Logo, > se > > não funcionou, podemos excluir essa hipótese. > > 3) Se tiver duas boas, então cada um dos grupos (abc) e (fgh) tem só 1 > boa > > também. > > > > Se pensarmos primeiro no caso 3, podemos testar (ade), (bde), (cde) e uma > > vai funcionar. > > > > Se não funcionar, resta o caso 1, e os testes (abf), (abg) e (abh) devem > > funcionar - se não funcionar, então com certeza c funciona junto com fg > ou > > fh, ou seja, temos mais dois testes, (cfg) e (cfh) > > > > Então no pior caso temos, 1+1+12+3+3+2 = 22 > > > > Estou certo ou há alguma falha no raciocínio? > > > > Abs a todos. > > > > Hugo. > > > > > > Em 13 de janeiro de 2012 23:00, Breno Vieira <[email protected]> > > escreveu: > >> > >> Como eu ja disse, achei 23: > >> > >> 1. Teste ABC, se nao funcionar sabemos que pelo menos uma entre A, B e C > >> nao funciona. > >> 2. Teste as combinacoes entre DEFGH > >> (DEF,DEG,DEH,DFG,DFH,DGH,EFG,EFH,EGH,FGH), se nenhuma funcionar temos > que > >> tres entre DEFGH nao funcionam, portando duas entre ABC e duas entre > DEFGH > >> funcionam. > >> 3. Sabemos que AB, AC ou BC sao formadas por duas que funcionam e que > pelo > >> menos uma entre D,E,F,G funciona, bastam entao mais 12 testes > totalizando > >> 23. > >> > >> PS:Ainda tem mais outros dois algoritmos um pouco mais complicados que > eu > >> fiz e que tambem chegam em 23. Quem da menos? > > > > > > ========================================================================= > Instruções para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html > ========================================================================= >
