Problemas para Casa

1. Introdução

Estes problemas destinam-se a ser resolvidos pelos alunos em casa. O seu grau de dificuldade varia bastante. Recomenda-se que os alunos os tentem resolver todos. Caso tenham dúvidas poderão sempre usar os horários de dúvidas para as esclarecer.

2. Problemas

1.a) Faça um programa que peça 20 valores ao utilizador e os guarde numa matriz. O programa deve depois permitir ao utilizador introduzir outros valores, que o programa indicará se pertencem ou não aos 20 valores originais (caso o utilizador queira sair deverá escrever o valor especial 0).

Notas: O algoritmo mais evidente (procurar "a direito") funciona, mas que aconteceria com 100000 valores? Seria eficiente? Seria "a direito" que você procuraria uma palavra no dicionário? Será por acaso que as palavras no dicionário estão por ordem? Escreva as suas ideias. Se chegar a um algoritmo mais eficiente, parabéns.

1.b) A procura de valores num vector ordenado pode ser feita de maneiras eficientes (que serão vistas mais tarde, mas às quais pode ter chegado na alínea anterior [se não chegou não se preocupe demasiado]). Mas como resolver o problema da ordenação? Tente resolvê-lo de formas diferentes. Qual das formas que encontrou é mais eficiente? Porquê? Encontrou alguma de que não se tenha falado nas aulas práticas? Lembre-se de como os jogadores profissionais arrumam as cartas.

Nota: A eficiência dos algoritmos tem a ver com o número de operações elementares (operações aritméticas, comparações, etc.) que são efectuadas. Pode-se falar em nº de operações mínimo (o melhor caso), máximo (o pior caso) e médio, para um dado número de valores a ordenar (com disposição aleatória).

2. Suponha que existem 10 itens diferentes (correspondentes, por exemplo, a diferentes títulos académicos na Europa) representados por números de 0 a 9. Exemplo:
0 - licenciatura em Portugal.
1 - Bachalaureat em França.
2 - B.Sc. (Bachelor of Sciences) no Reino Unido.
etc.

Suponha ainda que lhe são dadas 8 equivalências entre esses números (títulos):

0 = 2
1 = 2
etc.

Faça uma programa que, dadas as 8 equivalências na forma de pares de valores, indique as classes de equivalências resultantes (admita que as equivalências são comutativas, transitivas e simétricas, i.e. a = b <=> b = a, a = b e b = c => a = c e a <=> a).

Por exemplo, dadas as seguintes 8 equivalências:

1 = 3
4 = 5
3 = 8
9 = 0
7 = 2
2 = 6
5 = 0
1 = 8

O resultado deve ser:
Identifiquei 3 classes:
Classe 1: 0, 4, 5, 9
Classe 2: 1, 3, 8
Classe 3: 2, 6, 7

Indicando, para o exemplo dado, que graus académicos na Europa são equivalentes entre si.

Tente depois resolver o problema para um número arbitrário de itens e equivalências.

3. Suponha que pretende simular a distribuição de mercadorias numa prateleira de supermercado. Para simplificar suponha que que só tem de se ocupar de uma prateleira que está dividida em 20 áreas e que só tem 10 tipos de mercadorias diferentes (numeradas de 0 a 9). Cada pacote de mercadoria ocupa uma área completa.

Prateleira: _ _ 1 1 1 _ _ 7 7 7 7 7 _ _ 5 5 5 5 5 _

Simule as operações de chegada de mercadorias e saída de mercadorias da prateleira. O utilizador deve poder inserir e retirar um ou mais pacotes de mercadorias.

Exemplo de funcionamento:

Vão entrar ou sair mercadorias? (0 entrada, 1 saída, 2 acabar)
0
Que tipo de mercadoria é? (0-9)
1
Quantos pacotes? (0-20)
3
Inserida!

Vão entrar ou sair mercadorias? (0 entrada, 1 saída, 2 acabar)
1
Que tipo de mercadoria é ? (0-9)
7
Quantos pacotes? (0-20)
6
Não existem 6 pacotes da mercadoria 7.

Vão entrar ou sair mercadorias? (0 entrada, 1 saída, 2 acabar)
0
Que tipo de mercadoria é ? (0-9)
4
Quantos pacotes? (0-20)
3
Não existem 3 áreas contíguas para armazenar a mercadoria 4.
Não foi inserida.

Deve ter em atenção que uma determinada mercadoria deve ser posta em áreas contiguas. Deve também ter em atenção que se não tiver cuidados no modo de distribuir a mercadoria pode não conseguir inserir novas mercadorias mesmo existindo espaço: No exemplo acima se chegassem três pacotes da mercadoria tipo 4 não poderiam ser inseridos dado que não existem três áreas contiguas na prateleira. Como minimizar este problema?

4. Suponha que está a gerir uma carteira de títulos. Cada um desses titulos tem uma percentagem diferente de várias moedas diferentes. A informação que lhe chega às mãos todos os dias é uma tabela com as cotações das várias moedas (que deve inserir quando começa o programa). O programa deve de seguida calcular o valor da sua carteira de títulos com base num conjunto de informações fixas de que dispõe, nomeadamente: quantos títulos tem, quantas unidades de cada título tem e qual a composição de cada título.
Exemplo :

Titulo 1: 10 unidades : 10% PTE, 20% USD, 70% GBP
Titulo 2: 30 unidades : 30% ECU, 70% JPY
...

O valor total da carteira será a soma do valor de cada título.

Valor da carteira = Somatório(valor de um título)

O valor de um titulo é dado por:

Valor de um título = número de unidades * Somatório( %moeda * valor da moeda)