MAC 115 – Introdução à Computação Instituto de Física – Primeiro Semestre de 2004 - Noturno

Prova 2 – 24/06/2004

Instruções:

1. A prova pode ser feita a lápis. Cuidado com a legibilidade.

2. Não é permitido o uso de folhas avulsas para rascunho.

3. Não é necessário apagar rascunhos no caderno de soluções.

\underline{Questão 1} (valor: 4 pontos)

Simule a execução do programa abaixo destacando a sua saída (o que “vai sair na tela”). Não apague seus rascunhos. Dados de entrada (a serem lidos):

8
1 1 -1 2 1 3 -1 4
/*************************************************************
 Programa a ser simulado
 *************************************************************/
#include <stdio.h>
#define NMAX 10
void leia_vetor(int a[], int n);
void imprima_vetor(int a[], int n);
void Laplace(int b[], int a[], int n);
int main()
{
  int n, a[NMAX], b[NMAX];
  scanf("%d", &n);  leia_vetor(a, n);
  Laplace(b, a, n);  imprima_vetor(b, n);
  Laplace(a, a, n);  imprima_vetor(a, n);
  return 0;
}
void leia_vetor(int a[], int n)
{
  int i;
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
}
void imprima_vetor(int a[], int n)
{
  int i;
  for (i = 0; i < n; i++)
    printf("%d ", a[i]);
  printf("\n");
}
void Laplace(int b[], int a[], int n)
{
  int i;
  b[0] = -3; b[n - 1] = -3;
  for (i = 1; i < n - 1; i++)
    b[i] = a[i - 1] + a[i + 1];
}

\underline{Questão 2} (valor: 3 pontos)

Nesta questão, você deve escrever três funções para manipular conjuntos finitos de inteiros. Para representar um conjunto A, você deve usar um vetor, digamos a, seguindo a convenção vista em sala: se A tem n elementos, então a[0] = n e A = {a[1], …, a[n]}.

(i) Escreva uma função de protótipo

  int pertence(int x, int a[]);

que, ao ser chamado com pertence(x, a), devolve “verdadeiro” se e só se o inteiro x pertence ao conjunto representado pelo vetor a.

(ii) Escreva uma função de protótipo

  int contido(int a[], int b[]);

que, ao ser chamado com contido(a, b), devolve “verdadeiro” se e só se o conjunto representado pelo vetor a está contido no conjunto representado pelo vetor b. Você deve usar a função pertence() de (i) acima, mesmo que você não a tenha feito.

(iii) Escreva uma função de protótipo

  int igual(int a[], int b[]);

que, ao ser chamado com igual(a, b), devolve “verdadeiro” se e só se o conjunto representado pelo vetor a é igual ao conjunto representado pelo vetor b. Você deve usar a função contido() de (ii) acima, mesmo que você não a tenha feito.

\underline{Questão 3} (valor: 4 pontos)

Um quadrado latino n × n é uma matriz n × n em que cada linha e cada coluna é uma permutação da seqüência de inteiros 1, 2, …, n.

(i) Escreva uma função de protótipo

  int pertence(int x, int v[], int n);

que, ao ser chamado com pertence(x, v, n), devolve “verdadeiro” se e só se x ocorre na seqüência v[0], …, v[n − 1].

(ii) Escreva uma função de protótipo

  int eh_falho(int v[], int n);

que, ao ser chamado com eh_falho(v, n), devolve “verdadeiro” se e só se v[0], …, v[n − 1] não é uma permutação de 1, …, n. Você deve usar a função pertence() de (i) acima, mesmo que você não a tenha feito.

(iii) Escreva uma função de protótipo

  int eh_latino(int a[][NMAX], int n);

que, ao ser chamado com eh_latino(a, n), devolve “verdadeiro” se e só se a é um quadrado latino n × n. Você deve usar a função eh_falho() de (ii), mesmo que você não a tenha feito.