1o¯ Trabalho Prático de Programação Imperativa 2001/2002
Propostas de trabalho
21 de Novembro de 2001
1
Cartões mágicos
Considerando os cartões abaixo é possı́vel adivinhar um número de 1 a 63. Para tal basta pedir
a alguém que pense num número de 1 a 63 e indique em quais os cartões esse número aparece.
Sabendo os cartões é possı́vel saber o número imediatamente.
2o¯
1o¯
1
3
5
7
9 11 13 15
2
3
6
7 10 11 14 15
17 19 21 23 25 27 29 31
18 19 22 23 26 27 30 31
33 35 37 39 41 43 45 47
34 35 38 39 42 43 46 47
49 51 53 55 57 59 61 63
50 51 54 55 58 59 62 63
4o¯
3o¯
4
20
36
52
5
21
37
53
6
22
38
54
7
23
39
55
12
28
44
60
13
29
45
61
14
30
46
62
8
24
40
56
15
31
47
63
9
25
41
57
10
26
42
58
11
27
43
59
5o¯
16
24
48
56
17
25
49
57
18
26
50
58
19
27
51
59
12
28
44
60
13
29
45
61
14
30
46
62
15
31
47
63
36
44
52
60
37
45
53
61
38
46
54
62
39
47
55
63
6o¯
20
28
52
60
21
29
53
61
22
30
54
62
32
40
48
56
23
31
55
63
33
41
49
57
34
42
50
58
35
43
51
59
Como? O segredo consiste em adicionar os primeiros números em cada cartão dado. A soma é
o número escolhido.
Porquê? Esses números são as potências base 2 que na representação base 2 do número escolhido
correspondem a dı́gitos 1.
Por exemplo, se o número for 44, ele aparece nos cartões 3o¯ , 4o¯ , e 6o¯ e portanto
4 + 8 + 32 = 22 + 23 + 25 = 25 × 1 + 24 × 0 + 23 × 1 + 22 × 1 + 21 × 0 + 20 × 0 = (101100)2 = 44
Como são construı́dos os cartões? O 1o¯ cartão contém os números que na representação
em base 2 têm um 1 na posição correspondente a 20 . O 2o¯ cartão contém os números que na
representação em base 2 têm um 1 na posição correspondente a 21 , etc. O 6o¯ cartão contém os
números que na representação em base 2 têm um 1 na posição correspondente a 25 .
Assim basta considerar os números de 1 a 63 em binário para saber que números devem estar
em cada cartão. Por exemplo o número 7 terá de estar nos três primeiros cartões.
1
N. decimal
0
1
2
3
4
5
6
7
8
9
10
..
.
1.1
25
0
0
0
0
0
0
0
0
0
0
0
24
0
0
0
0
0
0
0
0
0
0
0
23
0
0
0
0
0
0
0
0
1
1
1
22
0
0
0
0
1
1
1
1
0
0
0
21
0
0
1
1
0
0
1
1
0
0
1
20
0
1
0
1
0
1
0
1
0
1
0
N. decimal
50
51
52
53
54
55
56
57
58
59
60
61
62
63
25
1
1
1
1
1
1
1
1
1
1
1
1
1
1
24
1
1
1
1
1
1
1
1
1
1
1
1
1
1
23
0
0
0
0
0
0
1
1
1
1
1
1
1
1
22
0
0
0
1
1
1
0
0
0
0
1
1
1
1
21
1
1
1
0
1
1
0
0
1
1
0
0
1
1
20
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Objectivo
Pretende-se um programa que implemente este jogo permitindo que:
• O computador adivinhe um número pensado pelo utilizador. O programa deve gerar e
mostrar os cartões um a um. Para cada cartão pedir ao utilizador para indicar se o número
que pensou está ou não nesse cartão (por exemplo, consoante o utilizador introduza o valor
1 ou 0). Com essa informação pode calcular o número e indicar ao utilizador.
Nota: Os cartões têm de ser calculados pelo programa e não pré-definidos (p.e num ficheiro).
A melhor maneira, inspirada na tabela acima, é gerar para o 1o¯ cartão todos os números
que têm a parcela 20 , para o 2o¯ todos os números que têm a parcela 21 , etc. Usa uma
instrução switch()...
• O utilizador adivinhe um número que o computador ”pense”: o computador deve gerar
um número entre 1 e 63 e indicar ao utilizador em que cartões ele se encontra (neste caso
devem ser escritos todos os cartões ao mesmo tempo). Neste modo, será pedido ao utilizador
para adivinhar o número que depois poderá ser confirmado, por comparação com o número
gerado.
• ambos os modos do jogo possam ser jogados várias vezes
• inicialmente deve aparacer um menu que permita escolher qual o modo em que o jogo é
jogado ou se se deseja terminar.
Nota que este jogo pode ser generalizado para números maiores que 63 e outras bases. Pensa
como fazê-lo! E se quisseres apresenta o programa para outros valores...
2
2
Quando é a Páscoa?
O domingo de Páscoa é o primeiro domingo depois da primeira lua cheia depois do equinócio da
Primavera.
Apenas com esta definição não é fácil construir um algoritmo...
Na realidade o seu cálculo é bastante mais complicado e está ligado ao calendário (lunar)
hebraico.
No mundo cristão, a Páscoa celebra a morte de Jesus Crito. Jesus Cristo foi crucificado,
imediatamente antes da data em que os judeus celebram o Êxodus de Moisés do Egipto, que
começa no 14-ésimo ou 15-ésimo dia do mês de Nisan (primavera). Os meses judaicos começam na
lua nova, portanto será imediatamente depois duma lua cheia. Assim, decidiu-se que o domingo
de Páscoa seria o primeiro domingo depois da lua cheia depois do equinócio da Primavera.
O equinócio da Primavera é a 21 de Março.
A lua cheia que precede a Páscoa chama-se Paschal. Para a calcular são necessárias duas
quantidades: o número de ouro e o Epact.
Número de ouro A relação entre as fases da lua e os dias do ano repete-se todos os 19 anos.
Assim pode-se associar um número entre 1 e 19 a cada ano. Esse número é o Número de Ouro,
NO:
N O = (ano%19) + 1
onde % é o resto da divisão inteira.
Nos anos com o mesmo número de ouro, a lua nova ocorre aproximadamente no mesmo dia.
Epact Cada ano é associado com um Epact. O Epact é uma medida da idade da lua (i.e do
número de dias desde a lua nova) numa dada data.
Esse valor é
(11 × (N O − 1))%30
acrescido de correções associadas aos anos bissextos, resultando
((11 × (N O − 1))%30 − (3 × seculo)/4 + (8 × seculo + 5)/25 + 8)
onde as divisões são divisões inteiras.
Ao qual se tem ainda que somar ou subtrair 30 para garantir que fica um valor entre 1 e 30.
O valor obtido é o Epact.
Lua cheia Paschal Se 1 ≤ Epact ≤ 23 então é 23 − Epact dias depois de 21 de Março. Se
Epact = 24 é o dia 18 de Abril (28 dias depois de 21 de Março). Se Epact = 25 e se N O > 11 é
17 de Abril (27 dias depois de 21 de Março), senão é 18 de Abril. Se 26 ≤ Epact ≤ 30, então é
53 − Epact dias depois de 21 de Março.
Domingo de Páscoa Primeiro domingo a seguir à lua cheia Paschall. Se a lua cheia for num
domingo, o domingo de Páscoa é no domingo seguinte.
2.1
Objectivo
Pretende-se um programa que:
• defina uma função que dado um ano determine e imprima a data do domingo de Páscoa
(dia do mês, mês e ano). O formato de escrita deverá ser "%d de Março de %d\n" ou
"%d de Abril de %d\n", como em:
15 de Abril de 2001
31 de Março de 2002
3
Para essa tarefa será ainda conveniente definir funções para as seguintes sub-tarefas:
– dado um ano retorne o Epact.
– dado o Epact e o Número de Ouro (NO) retorne a distância em dias do Paschal a 21 de
Março.
– dado um ano A (≥ 1582), mês M (1 a 12) e dia D (1 a 31), retorne qual o dia da
semana. Para tal, poderá ser usado o seguinte algoritmo:
Se o mês for Janeiro ou Fevereiro,
f actor = 365 × A + 31 × (M − 1) + D + (A − 1)/100 + 1
senão
f actor = 365×A+31×(M −1)+D −int(0.4×M +2.3)+A/4−int(0.75×(A/100+ 1))
O dia da semana é dado por
S = f actor%7
, sendo 0=sábado, 1=domingo, 2=segunda, etc.
Esta última função deverá ser usada para determinar o dia da semana da lua cheia Paschal,
depois de determinado qual o seu mês e dia do mês. Depois só é necessário determinar a
data (mês e dia do mês) do domingo seguinte!
Para testar se a tua função da Páscoa está correcta, poderás comparar os valores produzidos
pelo teu programa com os do ficheiro pascoas.txt que tem uma listagem de todas as Páscoas
entre 1582 e 10000.
• O programa deve no inı́cio apresentar um menu que permita o utilizador:
1. introduzir um ano (superior a 1582) e para esse ano ser impressa a data do domingo de
Páscoa.
2. introduzir dois anos (sendo o segundo superior e ambos superiores a 1582) e serem
impressas todas as Páscoas entre esses dois anos.
3. Sair do programa
Nas duas primeiras hipóteses, depois de executada a tarefa o programa deve voltar a apresentar o menu.
4
3
Coelhos e Raposas
Este trabalho tem como objectivo a realização de um simulador que ilustre a evolução de duas
populações de predadores e de presas. Neste caso particular temos uma população raposas que
são os predadores naturais de uma população de coelhos: Para a simulação vamos assumir que:
• o nascimento de coelhos tem uma taxa fixa (não depende de outros factores ambientais).
• a morte de coelhos é apenas provocada pelos actos predadores das raposas.
• a morte das raposas deve-se apenas a causas naturais.
• o nascimento de raposas é função da quantidade de comida disponı́vel (num. de coelhos).
Baseando-nos nestes pressupostos, a interacção entre estas duas espécies num ecossistema isolado,
pode ser descrita por um modelo constituı́do por duas equações diferencias que traduzem a forma como estas populações evoluem. Considerando PC (t) e PR (t) respectivamente como sendo o
número de coelhos e de raposas, num instante t, temos:
PC0 (t) = a × PC (t) − b × PC (t) × PR (t)
PR0 (t) = e × b × PR (t) × PC (t) − c × PR (t)
Onde:
• a é a taxa de crescimento dos coelhos (na ausência de actos predatórios).
• c é a taxa de mortalidade das raposas na ausência de comida (coelhos).
• b é a taxa de mortalidade de coelhos (devida a actos predatórios).
• e é a eficiência com que os actos predatórios das raposas se traduzem no crescimento da sua
população.
Como simplificação para facilitar a nossa simulação e considerando que
PC (t + D) − PC (t)
D→0
D
PC0 (t) = lim
vamos transformar as equações anteriores nas sucessões:
PCn+1 = PCn + (a × PCn − b × PCn × PRn ) × D
PRn+1 = PRn + (e × b × PRn × PCn − c × PRn ) × D
Em que:
• PCn o número de coelhos na iteração n
• PRn o número de raposas na iteração n
• D é o intervalo de tempo entre duas iterações
e sendo PC0 e PR0 os valores iniciais das populações.
5
3.1
Objectivo
Pretende-se um programa que, baseado nas equações anteriormente descritas, e nos dados introduzidos pelo utilizador, faça uma simulação da evolução das populações de coelhos e de raposas.
O resultado deverá ser uma tabulação por dia, do número de coelhos e de raposas. O programa
deverá conter funções para:
1. a leitura dos dados da simulação. Os dados de entrada serão as populações iniciais de
coelhos PC0 e de raposas PR0, os parâmetros a, b, c e e, que caracterizam a evolução das
populações e a interacção entre elas, o intervalo de tempo D entre duas interações e o número
de dias durante o qual se pretende analisar a evolução das populações. Nota: para efeitos
de simulação considere que as raposas e os coelhos podem assumir valores fraccionários.
2. realização da simulação
3. cálculo do novo número de coelhos (baseado nas equações definidas anteriormente). Na
eventualidade de o valor calculado ser menor que zero, considere-o igual a zero.
4. cálculo do novo número de raposas (baseado nas equações definidas anteriormente). Na
eventualidade de o valor calculado ser menor que zero, considere-o igual a zero.
5. impressão do dia, correspondente número de coelhos e de raposas. O formato de escrita
deverá ser "%d\t%6.4f\t6.4f\n"
O programa deve no inı́cio apresentar um menu que permita ao utilizador:
1. introduzir os dados da simulação.
2. realizar a simulação.
3. sair do programa.
Como exemplo, teste o programa com os seguintes parâmetros:
• PC0 = 4
• PR0 = 3
• a = 0.1
• c = 0.1
• b = 0.1
• e = 0.1
• D =0.01
• dias = 1000
Poderá comparar os resultado, para estes dados, s como os do ficheiro output.txt
Referências
6