MAC110  PROVA 1  29/4/99

1. [2 pontos] Escreva um programa que recebe como entrada um inteiro n (n ≥ 2) e n inteiros x_{1}, …, x_{n} e que decide se estes n inteiros formam uma seqüência crescente, decrescente, ou não-monotônica (isto é, nem crescente nem decrescente). Nesta questão, o termo crescente significa

x_{1} ≤ ⋯ ≤ x_{n},

e o termo decrescente significa

x_{1} ≥ ⋯ ≥ x_{n}.

2. [2 pontos] Escreva um programa que recebe como entrada um inteiro n (n ≥ 1) e n inteiros não-negativos x_{1}, …, x_{n} e que determina o máximo divisor comum destes n inteiros.

3. [2 pontos] Escreva uma função de protótipo

      double cos_aprox(double x, int n);

que calcula uma aproximação para cos x usando a fórmula

∑_{0≤k≤n}(−1)^{k} \frac{x^{2k}}{(2k)!}.

Você pode assumir que a função é sempre chamada para valores não-negativos de n.

4. [2 pontos] Escreva um programa que recebe como entrada inteiros não-negativos k e m, com k ≤ m, e que imprime os valores de

\binom{n}{k}

para todos os valores de n com k ≤ n ≤ m.

5. [2 pontos] Considere o seguinte algoritmo, visto em sala, associado ao teorema de Bezout (assuma que m e n são inteiros não-negativos dados).

Passo 1. Ponha a′ ← b ← 1, a ← b′ ← 0, c ← m, d ← n. Passo 2. Sejam q e r o quociente e resto da divisão de c por d: c = qd + r com 0 ≤ r < d. Passo 3. Se r = 0, termine o algoritmo e imprima a, b e d. Passo 4. Ponha c ← d, d ← r, t ← a′, a′ ← a, a ← t − qa, t ← b′, b′ ← b, b ← t − qb, e vá para o Passo 2.

(i) Implemente o algoritmo acima em C. (ii) Suponha que antes de realizarmos o Passo 4, temos am + bn = d, a′m + b′n = c = qd + r (0 < r < d),

e mdc(c, d) = mdc(m, n). Prove que após executarmos o Passo 4, temos am + bn = d, a′m + b′n = c, d > 0, e mdc(c, d) = mdc(m, n).

(iii) Deduza que os valores impressos por este algoritmo satisfazem am + bn = d, onde d = mdc(m, n).