apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I674 materiais7.931 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\u2c6ncia, obtivemos o resultado correto, que serviu
para ana´lise das outras soluc¸o\u2dces.
Segunda soluc¸a\u2dco
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\u2dco com
relac¸a\u2dco ao nu´mero total de carteiras na sala.
A soluc¸a\u2dco 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\u2dco na\u2dco se aplica para os casos de con-
tagem de presentes a um com\u131´cio numa prac¸a pu´blica, pois na\u2dco ha´ carteiras na rua.
Terceira soluc¸a\u2dco
Para resolver o problema do com\u131´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\u2dco elegante, na pra´tica e´ o que a organizac¸a\u2dco do com\u131´cio e a pol´\u131cia usam.
Mas deve-se saber de antema\u2dco a metragem da prac¸a e estimar a taxa de pessoas por
metro quadrado. O me´todo e´ ta\u2dco bom quanto melhor for a estimativa. Tambe´m e´
melhor se a populac¸a\u2dco estiver uniformemente distribu´\u131da.
Concluiu-se que e´ um bom me´todo, mas que na\u2dco e´ preciso. Isto e´, a chance
do nu´mero estimado ser exatamente o nu´mero de presentes e´ baixa. Os me´todos
anteriores sa\u2dco exatos, isto e´, nos da\u2dco 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\u2dco 80% correta. A questa\u2dco
que restou e´ se o erro de 20% e´ aceita´vel ou na\u2dco. Isto depende do motivo pelo qual
se quer contar os alunos na sala.
Quarta soluc¸a\u2dco
Para resolver o problema da precisa\u2dco, 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\u2dco para contar torcedores no esta´dio ou presentes em
um show de rock. Mas tambe´m foi considerado que a soluc¸a\u2dco exige uma ou mais
catracas, uma barreira para ningue´m entrar sem passar pela roleta e etc, para se
garantir a exatida\u2dco do resultado. No caso do com\u131´cio na\u2dco seria via´vel. No caso da
sala de aula foi constatado que na\u2dco havia roletas e portanto o me´todo na\u2dco se aplicava.
Quinta soluc¸a\u2dco
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\u2dco
bastaria uma simples multiplicac¸a\u2dco para a determinac¸a\u2dco do nu´mero correto.
De fato esta soluc¸a\u2dco funciona perfeitamente bem em lugares como por exemplo o
exe´rcito. As filas sa\u2dco 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\u2dco tenha completado 10.
Infelizmente as carteiras estavam bagunc¸adas na nossa sala e este ca´lculo na\u2dco 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\u2dco exata para o problema.
Sexta soluc¸a\u2dco
Nova sugesta\u2dco de outro aluno: cada estudante no in´\u131cio 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\u2dco muito boa. Na verdade e´ a versa\u2dco em paralelo da primeira soluc¸a\u2dco.
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\u2dco em poucos segundos, mais
algum tempo para as somas (isto demorou mais. . . ). Mas o resultado foi exato.
A soluc¸a\u2dco na\u2dco exige conhecimento pre´vio, na\u2dco exige equipamento adicional e e´
razoavelmente escala´vel, isto e´, funciona para salas de tamanhos diferentes.
Se´tima soluc¸a\u2dco
Para finalizar, o professor apresentou a soluc¸a\u2dco 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 \u131´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\u2c6s quartos estara\u2dco sentados, eventualmente
um deles tera´ um nu´mero \u131´mpar. E´ fa´cil perceber que o resultado sai em tempo
12 CAPI´TULO 2. SOBRE PROBLEMAS E SOLUC¸O\u2dcES
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\u2dco de pessoas termina
em 20 passos.
Parece um bom algoritmo, ele da´ resultado exato, na\u2dco exige conhecimento pre´vio,
e´ escala´vel, isto e´, funciona muito bem para um grande nu´mero de pessoas, mas exige
organizac¸a\u2dco dos presentes.
Infelizmente aquela turma na\u2dco 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\u2dco goste. O processo que um cidada\u2dco 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\u2dco
do mundo se pudesse usar um composto de pneu mais mole e com isto ganhar preciosos
segundos com relac¸a\u2dco 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\u2dco caseira na\u2dco 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´\u131 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\u2dco 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\u2c6nicos para levantar e baixar o carro todo de uma vez e esta´