Amigo meu fez da seguinte forma: Suponha que as 8 pilhas sejam divididas em 3 grupos:
ABC | DEF | GH (1) ABC tem 3 pilhas carregadas - 1 teste (2) DEFGH tem 3 pilhas carregadas - C(5,3) = 10 testes. Obs.: Como DEFGH não tem 3 pilhas carregadas e ABC não tem 3, ambos tem, obrigatoriamente, 2 pilhas carregadas Configurações Possíveis: * ABC tem 2 * DEF tem 0, 1 ou 2 * GH tem 0, 1 ou 2 (3) GH tem 2 pilhas carregadas: Como ABC tem 2 também, precisamos apenas de 2 testes. Obs.: Agora, podemos voltar a atenção para DEF Configurações Possíveis: * ABC tem 2 * DEF tem 1 ou 2 * GH tem 0 ou 1 (4) Testar 2 de ABC com 1 de DEF = C(3,2) * C(3,1) = 9 testes TOTAL: 1 + 10 + 2 + 9 = 22 testes Em 16 de janeiro de 2012 10:36, Hugo Fernando Marques Fernandes < hfernande...@gmail.com> escreveu: > 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 > <brenovieir...@hotmail.com>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? >> > >