Departamento de Ciência de Computadores
Introdução à Programação CC111
FCUP
2010/11
Folha 3
Em todos os problemas desta folha, todos os dados são lidos do standard input.
1. Sem usar o computador, siga o funcionamento de cada um dos programas seguintes anotando
a variação dos valores das variáveis, e indique qual o valor que escreve para o standard output (por
defeito, o ecrã). Diga ainda qual é o objectivo do programa. Descreva o que guarda cada variável.
a) Considere que os valores dados no input são 26 4.
// Surpresa 3.1
#include <stdio.h>
int main() {
int n, k, i, r;
printf("Indique dois inteiros positivos\n");
scanf("%d %d",&n,&k);
r = 0;
for (i = n; i > 0; i--)
if (i%k == 0)
r += i;
printf("resultado = %d\n",r);
return 0;
}
b) Considere que os valores dados no input são 1032 8 (e, noutro caso, 1032 2)
// Surpresa 3.2
#include <stdio.h>
int main() {
int n, b, aux, p;
scanf("%d %d",&n,&b);
if (n > 0 && b >= 2 && b <= 10){
p = 1;
for (aux = n; aux >= b; aux = aux/b)
p *= b;
while (p != 1) {
printf("%d ",n/p);
n %= p;
p /= b;
}
printf("%d\n",n);
}
return 0;
}
1
c) Considere que os valores dados no input são 12 10 9 15 16 8 13 10 14 5 8 19 20
// Surpresa 3.3
#include <stdio.h>
int main() {
int n, k, v, c=0;
scanf("%d",&n);
for (k=0; k<n; k++) {
scanf("%d",&v);
if (v >= 10)
c++;
}
printf("%d/%d\n",c,n);
return 0;
}
2. Siga o programa seguinte para a sequência de valores 10 5 0 4 16 -8 1 3 -1 -10 7 8 3 e
justifique que escreveria no standard output o que está na coluna da direita.
>>>>
9
-16
>>>>
4
-6
>>>>
0
>>>>
3
-4
>>>>
15
-28
>>>>
-8
>>>>
>>>>
2
-2
>>>>
-1
#include <stdio.h>
int main() {
int n;
scanf("%d",&n);
while (n != -10) {
printf(">>>> Para %d\n",n);
if (--n > 0) {
printf("%d\n",n++);
n = -2*n+3;
}
if (n++ < 0)
printf("%d\n",n);
scanf("%d",&n);
}
return 0;
}
Para 10
Para 5
Para 0
Para 4
Para 16
Para -8
Para 1
Para 3
Para -1
Para uma outra sequência à sua escolha, siga o programa e escreva o resultado. Depois, execute o
programa no computador, com redireccionamento do standard output para um ficheiro (não existente
no directório corrente), e verifique se a sua resposta está correcta.
3. Escreva um algoritmo para analisar uma sequência de n inteiros, com n ≥ 2, sendo n dado
antes, e indicar a menor diferença em valor absoluto entre elementos consecutivos. Por exemplo,
para 5 4 7 9 1 -8 o resultado seria 2. Indique a interpretação dada a cada variável e codifique o
algoritmo em linguagem C.
4. Escreva um programa para calcular o factorial de um inteiro n não negativo dado. Recorde que:
n! = n × (n − 1) × · · · × 2 × 1, se n ≥ 1, e 0! = 1. A partir de que valor de n o resultado produzido
pelo programa pode não estar correcto? Explique.
2
5.
Escreva um algoritmo para analisar uma sequência de n inteiros, com n ≥ 1, e verificar se
existe alguma subsequência não decrescente que tenha pelo menos k elementos, sendo k e n dados
antes. Deve obter como resultado Sim ou Nao. Por exemplo, para 3 10 9 7 14 7 9 1 -8 -15 -5 8
escreveria Sim e para 4 10 9 7 4 7 9 1 -8 15 5 8 escreveria Nao.
Indique a interpretação dada a cada variável e codifique o algoritmo em linguagem C.
6. Escreva um programa para determinar, por qualquer ordem, os divisores positivos de um dado
inteiro positivo n, que
a) considere apenas todos os inteiros d de 1 até n
b) considere apenas todos os inteiros d de 1 até n/2, e ainda n.
√
c) considere apenas inteiros d de 1 até d, ou seja, tais que d × d ≤ n, e ainda n.
Justifique a correcção do algoritmo em cada caso.
7. Adapte o programa que escreveu em 6c) para determinar apenas mdc(a, b) e mmc(a, b), sendo
a e b inteiros positivos. Para 45 e 126, o programa deve escrever no standard output apenas as duas
linhas seguintes (execute o programa com redireccionamento de output e verifique que o faz):
mdc(45,126) = 9
mmc(45,126) = 630
Para recordar (e saber):
Um número inteiro a é divisı́vel por um inteiro d 6= 0 sse existir um inteiro q tal que a = q × d,
dizendo-se que d é divisor de a e a é múltiplo de d.
Qualquer que seja o inteiro positivo a:
• os divisores de a pertencem a [−a, −1] ∪ [1, a]; os divisores positivos de a pertencem a [1, a].
• se d é divisor positivo de a então a/d também é (assim, por exemplo, os divisores positivos de
100 são 1, 100, 2, 50, 4, 25, 5, 20, e 10)
• os múltiplos de a são os inteiros da forma k × a, com k inteiro (negativo, positivo, ou zero); os
múltiplos positivos de a são os inteiros da forma k × a, com k ≥ 1.
Quaisquer que sejam os inteiros positivos a e b:
• mmc(a, b) designa o mı́nimo multiplo comum (positivo) de a e b, ou seja, o menor múltiplo
positivo de a que também é múltiplo de b, sendo mmc(a, b) = mmc(b, a).
• mdc(a, b) designa o máximo divisor comum de a e b, ou seja, o maior divisor de a que é divisor
de b, sendo mdc(a, b) = mdc(b, a).
• Pode-se mostrar que: max(a, b) ≤ mmc(a, b) ≤ a × b, 1 ≤ mdc(a, b) ≤ min(a, b) e
mmc(a, b) =
a×b
mdc(a, b)
sendo max(a, b) e min(a, b) o máximo e o mı́nimo entre a e b.
• Um inteiro positivo a é primo se tem exactamente dois divisores positivos 1 e a e é composto
se tem outros divisores positivos além de 1 e a. Qualquer inteiro positivo diferente de 1, ou é
primo ou é composto.
3