capitulo1_4_3_NB217C_20132

Prévia do material em texto

NB217 – Algoritmos e Estruturas de 
Dados I 
 
 
 
 
 
CAPÍTULO I 
 
 
 
 
 
 
 
 
Profa. Rosanna Mara Rocha Silveira 
Fevereiro/2013 - Versão 4.3 
 
 
 
LÓGICA ............................................................................................................................................................. 2 
PROCESSO DE AUTOMAÇÃO DE UM PROBLEMA.................................................................................... 4 
ALGORITMO..................................................................................................................................................... 4 
EXERCÍCIOS PROPOSTOS DO CAPÍTULO I:............................................................................................................. 9 
 
2 
CAPÍTULO I 
LÓGICA 
 
O que é lógica? 
É a arte de pensar corretamente. A lógica ensina a colocar ordem no pensamento. Uma de 
suas preocupações é determinar quais operações são válidas e quais não são. E quais 
operações antecedem outras. 
 
Exemplos: 
 
1) Uma pessoa adulta e consciente, para tomar banho, primeiro tira a roupa usando 
a lígica de estabelecer um contato direto entre a sua pele e a água e também 
para não molhar a sua roupa. 
 
2) Moramos em três pessoas. 
 Nenhum de nós dois quebrou o vaso de porcelana. 
 Quem quebrou o vaso? 
 
3) Gerson é cientista. 
 Todo cientista é estudioso. 
 Logo, Gerson é estudioso. 
 
 Exercício 1.1) Quantos quadrados você vê no desenho abaixo? A lógica é considerar 
apenas os quadrados pretos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercício 1.2) Jonas possui 15 bolas visualmente idênticas. Entretanto, uma delas é um 
pouco mais pesada do que as outras 14, que têm todas o mesmo peso. Utilizando uma 
balança de dois pratos semelhante à da figura abaixo, qual é o número mínimo de pesagens 
que deverá ser feito para que se possa garantir que a bola, que destoa quanto ao peso, seja 
identificada? 
 
 
 
 
3 
Exercício 1.3) Um rico senhor levou sua cruz de ouro, cravejada com diamantes, para um 
joalheiro fazer a manutenção. Esperto, antes de entregá-la ao joalheiro, contou as pedras 
que tinha na cruz em três direções (AD, BD e CD), e em qualquer uma destas direções, a 
cruz tinha oito diamantes (ver esquema abaixo). O joalheiro, entretanto, é mais esperto e se 
apropria de 2 (duas) pedras, mas muda a posição das restantes de tal forma que a 
contagem nos três sentidos ainda é a mesma. Como o joalheiro fez isto? 
 
 (A) 
* * * * * * * Sentidos: 
* * * * * * * AAA→ D = 8 pedras 
 * * * * * * * AAB→ D = 8 pedras 
(B) * * * * * * * (C) AAC→ D = 8 pedras 
 * * * * * * * 
* * * * * * * 
 * * * * * * * 
 * * * * * 
 (D) * * 
 
 
 
Exercício 1.4) Um homem precisa atravessar um rio com um barco que possui capacidade 
de carregar apenas ele mesmo e mais uma de suas três cargas, que são: um lobo, um bode 
e um maço de alfafa. O que o homem deve fazer para conseguir atravessar o rio sem perder 
suas cargas? 
 
 
 
 
 
 
 
 
 
 
 
 
Exercício 1.5) No quadriculado seguinte os números foram colocados nas células 
obedecendo a um determinado padrão. 
 
16 34 27 X 
13 19 28 42 
29 15 55 66 
 
Seguindo esse padrão, o número X deve ser tal que 
a) X > 100 
b) 90 < X < 100 
c) 80 < X < 90 
d) 70 < X < 80 
e) X < 70 
 
4 
PROCESSO DE AUTOMAÇÃO DE UM PROBLEMA 
 
 PROBLEMA 
 
 estudo detalhado do problema 
 
ANÁLISE 
 
 
 ESPECIFICAÇÃO 
 
 implementa uma série de funções 
 
PROGRAMAÇÃO 
 
 
 ALGORITMO ou FLUXOGRAMA 
 
 descrição em linguagem de programação de alto nível 
 
CODIFICAÇÃO 
 
 
 PROGRAMA-FONTE 
 
 tradução e análise sintática do programa 
 
COMPILAÇÃO 
 
 
 PROGRAMA-OBJETO 
 
 ligação dos módulos (se houver) 
 
MONTAGEM ou LINKAGEM 
 
 
 PROGRAMA-EXECUTÁVEL 
 
 Conjunto de testes com diversas amostras de entrada 
escolhidas de forma a permitir que sejam detectados erros 
 
TESTES 
 
 
 APLICAÇÃO 
 
ALGORITMO 
É uma sequência lógica de passos que visa atingir um objetivo bem definido. 
Exemplos: uma receita de bolo 
 a troca de um pneu furado 
 o cálculo da média de um aluno 
 
5 
As formas mais conhecidas de representar um algoritmo são: 
 
Descrição narrativa: expressa em linguagem natural 
 
Exemplo - A troca de um pneu furado: 
1) afrouxar ligeiramente as porcas 
2) suspender o carro 
3) retirar as porcas e o pneu 
4) colocar o pneu reserva 
5) apertar as porcas 
6) abaixar o carro 
7) dar o aperto final nas porcas 
 
Fluxograma convencional: expresso com desenhos 
 
 
 início ou fim entrada de dados 
 
 
 saída de dados processamento 
 
 
 decisão 
 
 
 
Exemplo: Cálculo da média de um aluno e sua situação de aprovação 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 S 
 
 
 N 
 
 
 
 
 
 
INÍCIO 
NOTA 1, 
NOTA2 
MEDIA = 
( NOTA1 + NOTA2) 
 / 2 
M E DIA 
>= 
70 
' APROVADO' 
' REPROVADO' 
FIM 
 
6 
Pseudocódigo: assemelha-se bastante à forma com que os programas são escritos. 
Também chamado de PORTUGOL (português + algol). 
 
Algoritmo MEDIA_FINAL 
declare 
 NOTA1, NOTA2, MEDIA numérico; // primeira e segunda notas e média 
início 
 escreva “Entre com as 2 notas”; 
 leia NOTA1, NOTA2; // entrada das 2 notas 
 MEDIA ← (NOTA1 + NOTA2) / 2; // cálculo da média 
 se (MEDIA >= 70) // análise da aprovação 
 então escreva “Aprovado”; 
 senão escreva “Reprovado”; 
fim. 
 
Escrever um algoritmo, em descrição narrativa, para trocar uma lâmpada no teto: 
 
• PEGUE UMA ESCADA 
• POSICIONE-A EMBAIXO DA LÂMPADA 
• BUSQUE UMA LÂMPADA NOVA 
• SUBA NA ESCADA 
• RETIRE A LÂMPADA VELHA 
• COLOQUE A LÂMPADA NOVA 
 
A sequenciação é uma convenção com o objetivo de reger o fluxo de execução, 
determinando qual ação vem a seguir. 
 
Está correto o algoritmo? 
E se a lâmpada não estiver queimada? 
 O algoritmo faz com que ela seja trocada do mesmo modo. Ele não prevê esta 
situação. 
O que temos que incluir no algoritmo? 
 
• PEGUE UMA ESCADA 
• POSICIONE-A EMBAIXO DA LÂMPADA 
• BUSQUE UMA LÂMPADA NOVA 
• LIGUE O INTERRUPTOR. SE A LÂMPADA NÃO ACENDER, ENTÃO: 
– SUBA NA ESCADA 
– RETIRE A LÂMPADA VELHA 
– COLOQUE A LÂMPADA NOVA 
 
O algoritmo pode ser otimizado? 
O que poderíamos fazer? 
 
• LIGUE O INTERRUPTOR. SE A LÂMPADA NÃO ACENDER, ENTÃO: 
– PEGUE UMA ESCADA 
– POSICIONE-A EMBAIXO DA LÂMPADA 
– BUSQUE UMA LÂMPADA NOVA 
– SUBA NA ESCADA 
– RETIRE A LÂMPADA VELHA 
 
7 
– COLOQUE A LÂMPADA NOVA 
 
O que ocorreu foi a inclusão de um teste seletivo (condição) que determina qual ou quais 
ações serão executadas dependendo do resultado da inspeção da condição. 
 
A solução parece adequada. Mas e se a lâmpada nova não funcionar? 
• LIGUE O INTERRUPTOR. SE A LÂMPADA NÃO ACENDER, ENTÃO: 
– PEGUE UMA ESCADA 
– POSICIONE-A EMBAIXO DA LÂMPADA 
– BUSQUE UMA CAIXA DE LÂMPADAS 
– SUBA NA ESCADA 
– RETIRE A LÂMPADA VELHA 
– COLOQUE A LÂMPADA NOVA 
– SE A LÂMPADA NÃO ACENDER, ENTÃO: 
• RETIRE A LÂMPADA E COLOQUE OUTRA 
– SE A LÂMPADA NÃO ACENDER, ENTÃO: 
• RETIRE A LÂMPADA E COLOQUE OUTRA 
– SE.. 
– ...... 
 
Até quando??? 
 
• LIGUE O INTERRUPTOR. SE A LÂMPADA NÃO ACENDER, ENTÃO: 
– PEGUE UMA ESCADA 
– POSICIONE-A EMBAIXO DA LÂMPADA 
– BUSQUE UMA CAIXA DE LÂMPADAS 
– SUBA NA ESCADA 
– RETIRE A LÂMPADA VELHA 
– COLOQUE A LÂMPADA NOVA 
– ENQUANTO A LÂMPADA NÃO ACENDER, FAÇA 
• RETIRE A LÂMPADA 
• COLOQUEOUTRA LÂMPADA 
 
O algoritmo repete os dois últimos comandos até que a lâmpada acenda, ou seja, 
estabelece um fluxo repetitivo de comandos. Percebe-se que o número de repetições é 
indefinido, e que depende apenas da condição estabelecida, o que leva a repetir as ações 
até se alcançar o objetivo: trocar a Lâmpada queimada por outra que funcione. 
 
E se tivéssemos 10 lâmpadas para trocar em lugares distintos? 
Teríamos que ter um algoritmo para cada lâmpada? 
 
• ENQUANTO A QUANTIDADE DE SOQUETES TROCADOS FOR MENOR QUE 10, 
FAÇA: 
– LIGUE O INTERRUPTOR. SE A LÂMPADA NÃO ACENDER, ENTÃO: 
• PEGUE UMA ESCADA 
• POSICIONE-A EMBAIXO DA LÂMPADA 
• BUSQUE UMA CAIXA DE LÂMPADAS 
• SUBA NA ESCADA 
• RETIRE A LÂMPADA VELHA 
 
8 
• COLOQUE A LÂMPADA NOVA 
• ENQUANTO A LÂMPADA NÃO ACENDER, FAÇA 
– RETIRE A LÂMPADA 
– COLOQUE OUTRA LÂMPADA 
• MAIS UM SOQUETE TROCADO 
 
 
Exercício 1.6) Elabore um algoritmo em descrição narrativa para sacar dinheiro em um 
banco 24 horas. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercício 1.7) Faça um algoritmo em fluxograma para calcular e mostrar o perímetro de um 
triângulo dados seus lados. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9 
Exercícios propostos do Capítulo I: 
 
P1.1) Em 2001, quando perguntaram ao pai de Alda, Beatriz e Cristina quais eram suas 
idades, ele disse que Alda tinha a idade de Beatriz somada com três vezes a idade de 
Cristina. Porém, três anos antes disso, ele dizia que Beatriz tinha a mesma idade de Cristina 
e que, depois de dois anos, já em 2003, seria Alda que teria três vezes a idade de Cristina. 
Quais serão as idades das três filhas em final de 2011? Apresente o desenvolvimento da 
questão. 
 
P1.2) Cinco jovens: Ana, Bruno, Cris, Daniela e Élvio, repartiram os últimos sorvetes, três de 
morango e dois de chocolate. Élvio e Bruno tomaram de sabores diferentes entre si; Ana e 
Élvio tomaram do mesmo sabor; e, Bruno e Cris, de sabores diferentes entre si. Qual foi o 
sabor de cada um? 
 
P1.3) “Eu nunca me importo em usar cinto de segurança quando tenho que ir ao 
supermercado local, porque eu não estarei dirigindo a mais de 40 Km/h”. 
O autor da frase aparentemente assume que acidentes de trânsito: 
a) somente ocorrem quando o motorista não está em sua vizinhança. 
b) nunca ocorrem quando o carro está a menos de 40 km/h. 
c) nunca ocorrem quando o carro está andando exatamente a 40 km/h. 
d) sempre ocorrem quando o carro está exatamente a 40 km/h. 
e) somente ocorrem quanto o carro está a mais de 40 km/h. 
 
P1.4) Em um laboratório de experiências veterinárias, foi observado que o tempo gasto para 
um coelho percorrer um labirinto na enésima (n) tentativa era dado pela função Q(n) = 
(3+12/n) minutos. Com relação a essa experiência, pode-se afirmar, então que um coelho: 
a) consegue percorrer o labirinto em menos de 3 minutos; 
b) gasta 5 minutos e 40 segundos para percorrer o labirinto na 5ª. tentativa; 
c) gasta 8 minutos para percorrer o labirinto na 3ª. tentativa; 
d) percorre o labirinto em 4 minutos na 10ª. tentativa; 
e) percorre o labirinto em uma das tentativas, em 3 minutos e 30 segundos. 
Justifique sua resposta. 
 
P1.5) Três jesuítas e três canibais precisam atravessar um rio; para tal, dispõem de um 
barco com capacidade para duas pessoas. Por medidas de segurança não se permite que 
em alguma margem permaneça uma quantidade de jesuítas inferior à de canibais. Qual a 
sequência de passos correta e mais adequada que permitiria a travessia com segurança? 
(O barco é sempre conduzido por um deles: jesuíta ou canibal) 
 
P1.6) Três macacos sábios têm os seguintes nomes: João, Dito e Luís. Seus sobrenomes 
são Ferpa, Salto e Melão, não necessariamente nessa ordem. Um deles não vê, outro não 
fala e outro não ouve, também não necessariamente nessa ordem. Dito lamenta que seu 
amigo Ferpa não possa ouvir. Luís e Salto adoram ver as macaquices mútuas. Aquele que 
não ouve vive assistindo às provocações entre João e Melão. Qual é o nome completo 
(nome e sobrenome) e a característica de cada um (cego, surdo ou mudo)? 
 
P1.7) Elabore um algoritmo em descrição narrativa que calcule e mostre a média aritmética 
de 4 notas de 50 alunos; e apresente o resultado (Reprovado: se média < 70 ou Aprovado, 
caso contrário). 
 
P1.8) Faça um algoritmo em fluxograma para mostrar o resultado da divisão de dois 
números lidos. Verifique a possibilidade de não haver divisão (divisão por zero). 
 
P1.9) Gabriel brinca com 24 moedas de R$ 1,00. Inicialmente, ele forma com elas três 
pilhas. Em seguida, dobra a segunda pilha colocando nela moedas retiradas da primeira; 
depois, dobra a terceira com moedas retiradas da segunda e, finalmente, dobra o que restou 
 
10 
na primeira pilha com moedas retiradas da terceira, ficando, assim, as três pilhas com o 
mesmo número de moedas. Qual é o número de moedas que havia, no início, na pilha mais 
alta? Mostre o seu raciocínio. 
 
P1.10) Cinco times ibéricos - Antares, Bilbao, Cascais, Deli e Elite – disputam um 
campeonato de basquete e, no momento, ocupam as cinco primeiras posições na 
classificação geral. Sabe-se que: 
 - Antares está em primeiro lugar e Bilbao está em quinto; 
 - Cascais está na posição intermediária entre Antares e Bilbao; 
 - Deli está à frente do Bilbao, enquanto que o Elite está imediatamente atrás do 
Cascais. 
Nestas condições, quem está em segundo lugar?