Um algoritmo é uma sequência de instruções que nos permite realizar uma tarefa. Mesmo que você não tenha aprendido com esse nome, certamente, conhece vários. Exemplo: multiplicação de dois números – aquela ‘velha história’ de multiplicar número por número e dizer “vai um’…

Vejamos um problema de algoritmo interessante: temos um prédio de 36 andares e dois ovos. Qual o andar mais alto do qual podemos largar um ovo sem que ele se quebre? Para nós, esse será o ‘andar seguro’. Observação: esses são ovos especiais, porque não se quebram tão facilmente! Nossa missão: bolar um algoritmo que minimize o número de lançamentos necessários para achar o andar seguro.

Para começar, vamos determinar nossa tarefa da forma mais precisa possível: 1) Temos dois ovos; 2) O prédio tem 36 andares; 3) Queremos determinar qual o andar seguro; 4) Se um ovo lançado de certo andar quebra, então, ele quebra se lançado de qualquer andar acima desse; 5) Se um ovo lançado de certo andar não quebra, então, ele não quebra se lançado de qualquer andar abaixo dele e, portanto, pode ser reutilizado; 6) Nosso método tem que ser tal que garanta que encontraremos o andar seguro em um número preestabelecido de lançamentos.

Comecemos com um só ovo. Nesse caso, não há muito o que fazer. Lançamos do primeiro andar; se quebrar, então, não há andar seguro; se não quebrar, passamos para o andar logo acima dele e repetimos o processo. Pior cenário? Fazer 36 lançamentos.

Com dois ovos, fica mais interessante. Não é necessário começar do primeiro andar, porque podemos nos dar ao luxo de perder um ovo e, ainda assim, continuar nossa busca pelo andar seguro. Como o prédio tem um número finito de andares, há um algoritmo que resolve nosso problema em um número máximo de passos conhecido previamente.

Imagine que lançamos o ovo do andar X. Se ele quebrar, então, temos que investigar os andares abaixo dele. Como vimos, não há muito o que fazer, a não ser começar os testes a partir do primeiro andar. Nesse caso, temos: 1) um lançamento do andar X; e 2) no pior cenário, mais X – 1 lançamentos, a partir do primeiro andar, totalizando X lançamentos.

E se, ao lançarmos o ovo do andar X, ele não quebrar? Agora, temos que testar andares acima dele – lembrando que nosso método deve ter um número máximo preestabelecido de lançamentos (nesse caso, X) e já ‘gastamos’ um, ou seja, só podemos fazer mais X – 1 lançamentos, no máximo.

Aqui está a chave: devemos lançar o ovo de X – 1 andares acima do andar X, ou seja, o segundo lançamento se dará do andar X + X – 1 = 2X -1. Se o ovo quebrar, começaremos a testar, de baixo para cima, os andares entre X e 2X – 1 (um total de X – 2 andares) e acharemos o andar seguro com, no máximo, 1 + 1 + X – 2 = X lançamentos (número igual ao do primeiro cenário). Se o ovo não quebrar no segundo lançamento, faremos um novo lançamento subindo mais X – 2 andares, porque já teremos ‘gastado’ dois lançamentos. E assim por diante.

Para garantir que encontraremos o andar seguro, devemos ter X + X – 1 + X – 2 + … + 1 = 36, que é o total de andares do prédio. Qual o valor de X? Somando da direita para a esquerda, 1 + 2 + … – e com um pouco de paciência –, temos X = 8, porque 1 + 2 + … + 8 = 36. 

Com esse algoritmo, encontramos o andar seguro em, no máximo, oito lançamentos.

E para prédios mais altos? Que tal um desafio?