lista01(com respostas)

Prévia do material em texto

Universidade Tecnológica Federal do Paraná
Departamento Acadêmico de Informática
IF61C – Fundamentos de Programação 1 (2013-2)
Prof. Bogdan Tomoyuki Nassu
Lista de Exercícios – Aula 1
(*) 1. Entre em www.codeblocks.org, baixe o software Code::Blocks e instale-o no seu computador. Se
você estiver usando o sistema operacional Windows, instale a versão com o MinGW. O Code::Blocks
é a ferramenta que usaremos para desenvolver programas durante o semestre.
Nota: se você sabe o que está fazendo, pode usar o Microsoft Visual C++ 2008 Express Edition. Se
você sabe o que está fazendo e também sabe o que é e como fazer um Makefile, pode usar
diretamente o gcc. Se você não entendeu esta nota, ignore-a.
Nota: foram registrados alguns problemas usando o Code::Blocks com o Windows 8. Caso você não
tenha uma alternativa a este SO, dê preferência ao Visual C++ 2088 Express Edition.
(*) 2. Procure saber o que é Linux e o que é o Mint Linux usado nos laboratórios. Se você não tem
experiência com Linux, procure tutoriais simples e se familiarize ao menos com os comandos básicos
de terminal.
(*) 3. Leia e reflita sobre o seguinte texto do renomado físico Richard Feynman sobre a educação no
Brasil. Apesar de o texto se referir a uma realidade da década de 1950, muitas das críticas
permanecem tristemente atuais.
http://www.uel.br/cce/fisica/pet/EnsinoRichardFeynman.pdf
(*) 4. Assista ao vídeo abaixo e reflita sobre o que é dito nele.
http://www.youtube.com/watch?v=nKIu9yen5nc
(**) 5. Descreva, usando linguagem natural e/ou notação matemática, um algoritmo para decompor um
dado número de segundos em dias, horas, minutos e segundos. Por exemplo, 90061 segundos
equivalem a 1 dia, 1 hora, 1 minuto e 1 segundo.
(***) 6. Tia Maria estava servindo suco para as crianças da sua sala no jardim de infância quando
notou que tinha colocado no copo do Joãozinho suco de abacaxi e no copo da Mariazinha suco de
melancia. Ocorre que Tia Maria se confundiu: Joãozinho não gosta de suco de abacaxi, e Mariazinha
não toma suco de melancia. Como as jarras de suco já estão vazias – na verdade, já foram até
lavadas – Tia Maria precisa trocar o conteúdo dos copos, já que cada criança só deve beber do seu
próprio copo.
Descreva, usando linguagem natural, um algoritmo para que Tia Maria realize a troca do conteúdo dos
dois copos. Suponha que os dois copos têm o mesmo tamanho, e que Tia Maria deve sujar o mínimo
possível de louça.
(***) 7.
a) Suponha que você tem 3 pepitas de ouro: p1, p2 e p3, de pesos diferentes, e precisa descobrir qual
delas é a mais pesada. Para isso, dispõe apenas de uma balança de comparação muito simples (mas
felizmente, precisa), que apenas indica qual de 2 objetos colocados sobre seus pratos é o mais
pesado. Você não tem pesos que possa usar como referência. Descreva um algoritmo que indique
qual das pepitas é a mais pesada sem recorrer a objetos externos, usando apenas a balança e as
próprias pepitas.
b) Suponha agora que em vez de 3 pepitas você tem n pepitas, p1, p2, ..., pn, e que deseja saber qual
delas é a mais leve E qual é a mais pesada. Como seria o algoritmo neste caso?
(***) 8. Um agricultor possui 1 (uma) espiga de milho. Cada espiga tem 150 grãos, e cada grão pesa
1g (um grama). Descreva, usando linguagem natural, um algoritmo para determinar quantos anos
serão necessários para que o agricultor colha mais de cem toneladas de milho (1T = 1000Kg, 1Kg =
1000g), sendo que:
a. A cada ano ele planta todos os grãos da colheita anterior.
b. Há apenas uma colheita por ano.
c. 10% (dez por cento) dos grãos não germinam (morrem sem produzir).
d Cada grão que germina produz duas espigas de milho.
Considere que a quantidade de terra disponível é sempre suficiente para o plantio.
Universidade Tecnológica Federal do Paraná
Departamento Acadêmico de Informática
IF61C – Fundamentos de Programação 1 (2013-2)
Prof. Bogdan Tomoyuki Nassu
Lista de Exercícios - Aula 1 - Respostas
1 a 4. (Sem correção.)
5. Dado T o número total de segundos:
- O número D de dias é dado pela parte inteira da divisão T/86400 (86400 é o
número de segundos em um dia: 60 x 60 x 24).
- O número H de horas é dado pela parte inteira da divisão (T-86400D)/3600 (3600
é o número de segundos em uma hora: 60 x 60).
- O número M de minutos é dado pela parte inteira da divisão (T-86400D-
3600H)/60.
- O número S de segundos é dado por T-86400D-3600H-60M.
6. Tia Maria vai precisar de um recipiente auxiliar para colocar o conteúdo de
um dos copos. Pode ser outro copo que tenha pelo menos o mesmo tamanho dos copos
das crianças, ou até uma das jarras. Basta então ela colocar o conteúdo do copo
de Mariazinha (suco de melancia) no recipiente auxiliar, o conteúdo do copo do
Joãozinho (suco de abacaxi) no copo de Mariazinha, e o conteúdo que estava no
recipiente auxiliar (suco de melancia) no copo de Joãozinho. Se precisar, ela
pode lavar os copos entre as operações. O conteúdo dos copos fica assim:
Início: Joãozinho: abacaxi Mariazinha: melancia Auxiliar: nada
1 troca: Joãozinho: abacaxi Mariazinha: nada Auxiliar: melancia
2 trocas Joãozinho: nada Mariazinha: abacaxi Auxiliar: melancia
3 trocas Joãozinho: melancia Mariazinha: abacaxi Auxiliar: nada
7.
a) Precisamos comparar as pepitas 2 a 2. Suponha que pa > pb indica que a pepita
a é mais pesada que a pepita b. Sendo assim:
- Se p1 > p2 e p1 > p3, a pepita mais pesada é p1.
- Se p1 > p2 e p1 < p3, a pepita mais pesada é p3.
- Se p1 < p2 e p2 > p3, a pepita mais pesada é p2.
- Se p1 < p2 e p2 < p3, a pepita mais pesada é p3.
b) Para resolver este problema, precisamos pegar as pepitas uma por vez e
separar a pepita mais pesada e a pepita mais leve encontradas até o momento.
Suponha que temos uma pilha de pepitas ainda não analisadas (que começa com
todas as pepitas), uma pilha de pepitas já analisadas (que começa vazia), e duas
posições, que chamaremos de pl para a pepita mais leve encontrada até o momento
e pp para a pepita mais pesada encontrada até o momento. Começamos com p1 e p2:
- Se p1 > p2, colocamos p1 na posição da pepita mais pesada (pp) e p2 na da
pepita mais leve (pl), ou o contrário caso p2 > p1.
- Começando com p3, pegamos cada pepita pi da pilha das não analisadas, e
comparamos com a pepitas em pp e pl. Se pi < pl, pi é mais leve que a pepita
mais leve que havíamos encontrado até o momento, então colocamos pi no lugar da
antiga pl, e jogamos a pepita que estava em pl na pilha das pepitas já
analisadas. Fazemos o mesmo para a pepita mais pesada, trocando a pepita que
está na posição pp por pi se pi > pp. Se pi não for nem mais leve que pl nem
mais pesada que pp, jogamos pi na pilha das pepitas já analisadas. No final,
teremos a pepita mais leve de todas em pl e a mais pesada em pp.
8. O truque para entender este tipo de exercício é sempre começar listando o
estado dos elementos que fazem parte do problema, montando uma tabela. Para
identificar quais são estes elementos, precisamos interpretar o enunciado.
Fazendo as contas para cada ano, temos o seguinte resultado:
Anos passados | Número de espigas | Número de grãos | Toneladas
-------------------------------------------------------------------------------
0 | 1 | 150 | (150/1000)/1000 = 0,00015
1 | 150x0,9x2 = 270 | 270x150 = 40500 | 20250/1000000 = 0,0405
2 | 72900 | 10935000 | 10,935
3 | 19683000 | 2952450000 | 2952,45
Podemos então identificar como a tabela foi preenchida:
- Inicialmente, temos:
 anos passados: 0
 espigas de milho: 1
 grãos: 150 x o número de espigas de milho
 peso (em toneladas): número de grãos / 1000000
- Repita até que o peso seja maior que 100 toneladas:
 Aumente em 1 o número de anos passados.
 Defina o novo número de espigas como sendo o númerode grãos anterior x 0,9 
(porque apenas 90% das espigas germina) x 2 (porque cada grão gera 2 espigas).
 Defina o novo número de grãos como sendo o novo número de espigas x 150.
 Defina o novo peso como sendo o novo peso / 1000000.
É possível eliminar algumas dessas entidades, porque elas são definidas em
função de outras (por exemplo, em vez do peso, poderíamos usar diretamente o
número de grãos / 1000000), mas por clareza por enquanto fica tudo explícito.