apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
inviabilidade do me´todo nestes casos.

Executamos a contagem em aproximadamente 1 minuto. Dois alunos tambe´m
fizeram a contagem e, apo´s confereˆncia, obtivemos o resultado correto, que serviu
para ana´lise das outras soluc¸o˜es.

Segunda soluc¸a˜o

Pensando no problema de se contar na ordem de 100 alunos, um estudante sugeriu
que se fizesse apenas a contagem das carteiras vazias e em seguida uma subtrac¸a˜o com
relac¸a˜o ao nu´mero total de carteiras na sala.

A soluc¸a˜o tambe´m e´ muito simples e funciona perfeitamente bem, mas exige um
conhecimento pre´vio: deve-se saber antecipadamente o total de carteiras na sala.

Esta maneira de contar e´ cada vez melhor quanto maior for o nu´mero de presentes,
pois o nu´mero de carteiras vazias e´ menor do que o das ocupadas. Por outro lado, se
a sala estiver com pouca gente, o me´todo anterior e´ mais eficiente.

Os alunos observaram tambe´m que a soluc¸a˜o na˜o se aplica para os casos de con-
tagem de presentes a um comı´cio numa prac¸a pu´blica, pois na˜o ha´ carteiras na rua.

Terceira soluc¸a˜o

Para resolver o problema do comı´cio, outro estudante sugeriu que se fizesse uma
estimativa baseada na metragem total da prac¸a, multiplicada pelo nu´mero estimado
de pessoas por metro quadrado.

Soluc¸a˜o elegante, na pra´tica e´ o que a organizac¸a˜o do comı´cio e a pol´ıcia usam.
Mas deve-se saber de antema˜o a metragem da prac¸a e estimar a taxa de pessoas por
metro quadrado. O me´todo e´ ta˜o bom quanto melhor for a estimativa. Tambe´m e´
melhor se a populac¸a˜o estiver uniformemente distribu´ıda.

Concluiu-se que e´ um bom me´todo, mas que na˜o e´ preciso. Isto e´, a chance
do nu´mero estimado ser exatamente o nu´mero de presentes e´ baixa. Os me´todos
anteriores sa˜o exatos, isto e´, nos da˜o o nu´mero correto de presentes. Este me´todo
tambe´m serve razoavelmente bem para o nu´mero de alunos na sala de aula. De fato,
nesta aula, o professor conseguiu o nu´mero com aproximac¸a˜o 80% correta. A questa˜o
que restou e´ se o erro de 20% e´ aceita´vel ou na˜o. Isto depende do motivo pelo qual
se quer contar os alunos na sala.

Quarta soluc¸a˜o

Para resolver o problema da precisa˜o, outro estudante sugeriu o uso de roletas.

2.1. CONTANDO O NU´MERO DE PRESENTES EM UM EVENTO 11

Efetivamente e´ esta a soluc¸a˜o para contar torcedores no esta´dio ou presentes em
um show de rock. Mas tambe´m foi considerado que a soluc¸a˜o exige uma ou mais
catracas, uma barreira para ningue´m entrar sem passar pela roleta e etc, para se
garantir a exatida˜o do resultado. No caso do comı´cio na˜o seria via´vel. No caso da
sala de aula foi constatado que na˜o havia roletas e portanto o me´todo na˜o se aplicava.

Quinta soluc¸a˜o

Mais uma vez outro estudante apresentou uma boa alternativa: contar o nu´mero de
filas de carteiras e, dado que todas tenham o mesmo nu´mero de estudantes, enta˜o
bastaria uma simples multiplicac¸a˜o para a determinac¸a˜o do nu´mero correto.

De fato esta soluc¸a˜o funciona perfeitamente bem em lugares como por exemplo o
exe´rcito. As filas sa˜o rapidamente arrumadas com, digamos, 10 soldados em cada fila,
sabendo-se o nu´mero de filas basta multiplicar por 10, eventualmente tendo-se que
contar o nu´mero de pessoas em uma fila que na˜o tenha completado 10.

Infelizmente as carteiras estavam bagunc¸adas na nossa sala e este ca´lculo na˜o pode
ser feito. Tambe´m ficaria estranho o professor colocar todos os alunos em filas. Foi
tambe´m observado que o me´todo fornece a soluc¸a˜o exata para o problema.

Sexta soluc¸a˜o

Nova sugesta˜o de outro aluno: cada estudante no in´ıcio de cada fila conta o nu´mero de
alunos da sua fila, tomando o cuidado de contar a si pro´prio tambe´m. Depois soma-se
todas as contagens de todos os primeiros de fila.

Soluc¸a˜o muito boa. Na verdade e´ a versa˜o em paralelo da primeira soluc¸a˜o.
Distribuindo-se a tarefa, cada primeiro de fila tem entre 10 e 15 alunos para con-
tar em sua fila. Se a soma foi correta o nu´mero obtido ao final do processo e´ exato.
No caso daquela aula os estudantes realizaram a operac¸a˜o em poucos segundos, mais
algum tempo para as somas (isto demorou mais. . . ). Mas o resultado foi exato.

A soluc¸a˜o na˜o exige conhecimento pre´vio, na˜o exige equipamento adicional e e´
razoavelmente escala´vel, isto e´, funciona para salas de tamanhos diferentes.

Se´tima soluc¸a˜o

Para finalizar, o professor apresentou a soluc¸a˜o seguinte: todos os estudantes se le-
vantam e se atribuem o nu´mero 1. Em seguida os alunos se organizam em pares. Em
cada par, primeiro e´ somado o nu´mero de cada um dos dois, um deles guarda este
nu´mero e permanece de pe´, o outro deve se sentar. Os que ficaram em pe´ repetem
este processo ate´ que so´ exista um u´nico aluno em pe´. Ele tem o nu´mero exato de
estudantes na sala.

Como se divide a sala em pares, apo´s a primeira rodada metade da sala deve ter
o nu´mero 2 e a outra metade esta´ sentada, considerando que a sala tem o nu´mero de
alunos par. Se for ı´mpar um deles tera´ ainda o nu´mero 1. Apo´s a segunda rodada um
quarto dos alunos devera´ ter o nu´mero 4 e treˆs quartos estara˜o sentados, eventualmente
um deles tera´ um nu´mero ı´mpar. E´ fa´cil perceber que o resultado sai em tempo

12 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O˜ES

proporcional ao logaritmo do nu´mero total de alunos, o que e´ bem ra´pido. De fato,
para mil pessoas o processo termina em 10 passos e para um milha˜o de pessoas termina
em 20 passos.

Parece um bom algoritmo, ele da´ resultado exato, na˜o exige conhecimento pre´vio,
e´ escala´vel, isto e´, funciona muito bem para um grande nu´mero de pessoas, mas exige
organizac¸a˜o dos presentes.

Infelizmente aquela turma na˜o se organizou direito e o resultado veio com um erro
de 40%. . . Mas apo´s duas rodadas de treinamento, na terceira conseguimos obter o
resultado correto.

2.2 Trocando os quatro pneus

Todo mundo sabe trocar pneus, embora na˜o goste. O processo que um cidada˜o comum
executa e´ muito simples: levanta o carro com o macaco, tira todos os quatro parafusos
da roda com o pneu furado, tira a roda do eixo, coloca a roda com o pneu novo no
eixo, em seguida aperta os quatro parafusos. Finalmente, baixa o carro e esta´ pronto.

Nos anos 1980, um famoso piloto de fo´rmula 1 imaginou que poderia ser campea˜o
do mundo se pudesse usar um composto de pneu mais mole e com isto ganhar preciosos
segundos com relac¸a˜o aos seus concorrentes. O problema e´ que estes compostos mais
moles se deterioram rapidamente exigindo a troca dos quatro pneus no meio da corrida.
O tal piloto, apo´s alguns ca´lculos, concluiu que se levasse menos de 8 segundos para
trocar os quatro pneus, valeria a pena aplicar este me´todo.

Obviamente a soluc¸a˜o caseira na˜o serve. O me´todo descrito acima custa em geral
20 minutos por pneu, com um pouco de pra´tica 10 minutos. Com muita pra´tica 2 ou
3 minutos. Para trocar os quatro pneus, 8 a 12 minutos.

Da´ı o problema: Como trocar os quatro pneus de um carro em menos de 8 segun-
dos?

Um dos grandes custos de tempo e´ ter que trocar o macaco para cada roda: usamos
um macaco hidra´ulico, destes de loja de pneus, e levantamos o carro todo de uma so´
vez.

Mas, para cada roda, temos 4 parafusos, isto e´, 16 no total, ou melhor, 32, pois
tem que tirar e depois recolocar: usa-se uma aparafusadeira ele´trica para amenizar o
problema, mas ainda na˜o e´ suficiente.

Se a roda tiver um u´nico parafuso a economia de tempo e´ maior ainda. Mas
ainda estamos na casa dos minutos, e o tempo total deve ser menor que 8 segundos.
Desistimos do campeonato?

Com 4 pessoas, cada uma troca uma roda, divide-se o tempo por 4. Opa! Ja´
estamos abaixo de 1 minuto.

Se tiver ainda a possibilidade de 3 pessoas por roda: um tira o parafuso, outro tira
a roda velha, um terceiro coloca a roda nova e o primeiro aperta o parafuso. Mais 2
mecaˆnicos para levantar e baixar o carro todo de uma vez e esta´