Algoritmos - Aula 2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Algoritmos e Estrutura de
Dados I
Aula de 03/08/2016 Professor Alessandro Carneiro
Solução de Problemas
para
solucionar
Que	estratégia	você	usa problemas?
Os mais simples como “comer ou respirar” nós já resolvemos instintivamente, quase sem pensar, mas os problemas complexos precisam de uma abordagem mais sistematizada.
Solução de Problemas
Etapas para solução de problemas
Compreenda o problema
Entenda	o	enunciado	e	tire	de	lá
todas	as
informações necessárias.
Elabore uma estratégia de resolução
Execute a estratégia
Ao executar a estratégia verifique cada passo.
Revise
Observe o resultado obtido.
Pode parecer um pouco abstrato, mas esteja certo que a nossa mente realiza, freqüentemente, muitas destas análises mesmo que inconscientemente.
Prática – Problema 01
Os Músicos
Três músicos: João, Antônio e Francisco, tocam guitarra, bateria e baixo. Contudo, não se sabe quem toca o quê. Sabe-se que o Antônio não é o baixista. Que João ensaia com o guitarrista às Quintas. E que o baixista
ensaia	sempre	sozinho	às consegue	dizer		quem	toca
Terças.	Você cada	um		dos
instrumentos?
Vamos construir, juntos, uma solução?
Os Músicos
Etapa 1: Compreenda o Problema.
Nesta etapa devemos deixar claras as
condições do problema, tais como:
Existem três pessoas e três instrumentos.
Cada pessoa toca um instrumento diferente.
Temos que descobrir qual instrumento cada pessoa toca.
Existem três frases informativas que podem levar a solução.
Os Músicos
Etapa	2:	Construa	uma	Estratégia	de Resolução.
Precisamos buscar a solução, de maneira que
ela possa ser testada.
Se	você	já	fez	algum	problema	similar,	esta
estratégia surge naturalmente.
Uma estratégia possível é concluir quem toca cada instrumento por eliminação, ou seja, analisando as frases informativas do enunciado eliminando as alternativas que não são possíveis.
Os Músicos
Os Músicos
Etapa 3: Execute a Estratégia
Nesta	etapa	realizamos	os	passos
definidos	na
estratégia, ou seja, analisar as frases informativas para preencher a tabela. Vamos começar a preenchê- la com base na afirmação: “Antônio não é o baixista”. Podemos assinalar na tabela, na coluna de Antônio que ele não toca baixo. Ficando assim:
Os Músicos
Já a segunda afirmação tem que ser analisada em conjunto com a terceira afirmação. Veja bem: “João ensaia com o guitarrista às Quintas. O baixista ensaia sempre sozinho, às Terças”. Ora, se João ensaia com o guitarrista, logo ele não ensaia sozinho, portanto, ele também não é o baixista. Assim podemos acrescentar à tabela mais um não.
Os Músicos
Por eliminação (não é João nem Antônio). Descobrimos que Francisco é o baixista e com isso também descobrimos que o mesmo Francisco não é guitarrista nem baterista. Vamos assinalar isto na tabela, ficando assim:
Os Músicos
Analisando agora somente a segunda afirmação “João ensaia com o guitarrista às Quintas”. Podemos concluir que João não é o guitarrista. E ao assinalar isto na tabela descobrimos quem é o guitarrista. É Antônio.
Agora por eliminação podemos concluir que o baterista é João, pois ele não toca guitarra e nem baixo. Além disso, podemos assinalar que Antônio não toca bateria. A tabela final fica assim:
Etapa 4: Revise
Dúvidas?
Problema 2
parte
Dois Comboios
Um	comboio
velocidade	de
120	Km/h	em
direção	a
de	Brasília	a	uma
São
Paulo, ao mesmo tempo em que outro comboio parte de São Paulo a uma velocidade de 80km/h em direção a Brasília.
Pergunta: Quando os comboios se encontram, qual deles está mais próximo de Brasília? Aquele que parte de Brasília ou o que parte de São Paulo?
Problema 3
As Pizzas (traduzido de Wikipedia Puzzles, 2006)
André, Renata, César, Jane e Ozzi pediram cinco pizzas (uma para cada um). Cada pizza continha três sabores. Os cinco sabores disponíveis na pizzaria eram: pimentão, milho, cebola, calabreza e palmito. O único sabor, em comum, nos pedidos de André e César foi o palmito. O único sabor, em comum, nos pedidos de Jane e Ozzi foi a calabreza. O único sabor, em comum, nos pedidos de Renata e César foi o milho. O único sabor, em comum, nos pedidos de Renata e Jane foi o pimentão.
Problema 4
Na floresta, a hiena mente às segundas, terças e quartas- feiras; a onça mente às quintas, sextas e sábados. Nos dias em que elas não mentem, elas dizem a verdade. Um dia, encontraram-se hiena e onça e deu-se este diálogo:
Hiena: Olá onça! Ontem eu menti.
Onça: Olá hiena! Eu também menti ontem. Em que dia aconteceu este encontro?
Problema 5
Quatro irmãos encontraram-se após longo período distantes,
Médico,
cada	um	retornando	com	uma	profissão: Engenheiro, Arquiteto e Advogado.
Agenor não era Advogado nem Médico. Cláudio não era Engenheiro nem Advogado.
Patrício
não	era
Se Agenor não era Engenheiro então Advogado.
Matheus não era Médico nem Advogado. Patrício não era Médico nem Engenheiro. Qual a profissão de cada um?
Problema 6
Tem-se 3 caixas, contendo uma delas duas bolas pretas, outra 2 bolas brancas e a outra, uma bola branca e uma preta.. As caixas têm etiquetas escritas com BB, PP e PB, correspondente às iniciais das cores de cada bola. Porém alguém trocou as etiquetas das caixas de forma que todas ficaram com as inscrições erradas. Tirando apenas uma bola de uma das caixas (sem olhar para a outra), descobrir o conteúdo das 3 caixas.
Problema 7
Um pescador esta do lado de um rio, ele tem um barco e precisa levar um saco de milho, uma galinha e uma raposa para o outro lado. O barco só agüenta ele e mais alguma coisa ( milho ou a galinha ou a raposa ). Ele não pode deixar a galinha com o milho, porque a galinha comeria o milho, e nem pode deixar a galinha com a raposa, se não a raposa comeria a galinha... O que ele deve fazer?