MAC 2166 - Introdução à Computação para Engenharia
ESCOLA POLITÉCNICA - PRIMEIRO SEMESTRE DE 2001
Gabarito da Terceira Prova - 27 de junho de 2001

1. (valor 3.5 pontos)
   

   a) Faça uma função com protótipo

   
     void quadrado(int n, double A[MAX][MAX], double B[MAX][MAX]);
   

   que recebe um inteiro n, uma matriz real A de dimensões n $\times$ n e calcula a matriz B = A$^2$.
   

   SOLUÇÃO:
   

    
   #define MAX ###
   void quadrado(int n, double A[MAX][MAX], double B[MAX][MAX]) {
      int lin, col, k;
      for (lin = 0; lin < n; lin++) 
         for (col = 0; col < n; coll++) {
            B[lin][col] = 0.0;
            for (k = 0; k<n; k++)
               B[lin][col] = B[lin][col] + A[lin][k] * A[k][col];
         }
   }
   

   b) Utilizando obrigatoriamente a função do item anterior, faça um programa que lê um inteiro n e uma matriz real A de dimensões n $\times$ n e determina se a matriz é ou não idempotente (veja Obs1). Para ler a matriz utilize a função

   
     void le(int n, double A[MAX][MAX])
     {
       int i, j;
       for (i=0; i<n; i++)
         for (j=0; j<n; j++)
           scanf("%lf",&A[i][j]);
     }
   

   Obs1: Uma matriz $A$ é idempotente se $A=A^2$.

   Obs2: Você não precisa reescrever a função do item (a) no item (b). Suponha também que o programa já contenha os ``include''s adequados e a definição da constante MAX.

   Dica: O teste A==B para testar se as matrizes A e B são iguais NÃO funciona na linguagem C!
   

   SOLUÇÃO:
   

    
   #include <stdio.h>
   #define MAX ###
   #define TRUE 1
   #define FALSE 0
   void le(int n, double A[MAX][MAX]);
   void quadrado(int n, double A[MAX][MAX], double B[MAX][MAX]);
   
   int main() {
      int lin, col, resp, n;
      double A[MAX][MAX], B[MAX][MAX];
   
      /* entrada dos dados */
      printf("Entre com n\n");
      scanf("%d", &n);
      printf("Entre com os elementos da matriz real A:\n");
      le(n, A);
   
      /* eleva a matriz ao quadrado */
      quadrado( n, A, B );
   
      /* verifica se as matrizes sao iguais */
      resp = TRUE;
      for (lin = 0; lin < n; lin++) 
         for (col = 0; col < n; coll++)
            if (A[lin][col] != B[lin][col])
               resp = FALSE;
   
      /* imprime a resposta */
      if (resp == TRUE) 
         printf ("A matriz e idempotente\n");
      else
         printf("A matriz nao e idempotente\n");
   
      return 0; /* FIM */
   }
   

2. (valor 3.5 pontos)
   

   Faça uma função elimina que recebe um inteiro n$>0$, um vetor inteiro v com n elementos e um inteiro k$>0$ e elimina do vetor todos os múltiplos próprios de k, e devolve o número de elementos eliminados do vetor. Sua função terá o protótipo:

   
     int elimina(int v[MAX], int n, int k);
   

   A ordem relativa dos elementos não eliminados do vetor deve ser mantida. Suponha que MAX é uma constante definida apropriadamente no programa.

   Obs1: Dados dois inteiros $a$ e $b$, dizemos que $a$ é múltiplo próprio de $b$ se $a$ é múltiplo de $b$ e $a>b$.

   Obs2: Note que a função não altera o valor de n.

   
   
   

   Exemplo: Seja k$=3$, n$=8$ e um vetor v com os n elementos a seguir

   
   

   $$1,\;5,\;3,\;27,\;9,\;8,\;19,\;6.$$
   
   

   Após a execução da função o vetor v deverá conter, nas primeiras posições, os elementos

   
   

   $$1,\;5,\;3,\;8,\;19,$$
   
   

   e a função devolve 3, que é o número de elementos eliminados.
   

   SOLUÇÃO:
   

   
   /* todos os valores de v são positivos (>0). */
   int elimina(int v[MAX], int n, int k) {
     int i, j, conta;
     i = 0;
     conta = 0;
     while (i<n) {
        if ( (v[i] > k) && (v[i] % k == 0) ) {
           n--; 
           for (j=i; j<n; j++)
               v[j] = v[j+1];  /* desloca o vetor */
           conta++;
        }
        else i++;
     }
     return conta;
   }
   

3. (valor 3.0 pontos)
   

   Faça um programa que leia um inteiro $n$, com $2 \leq n \leq$ MAX, e imprime todos os números primos entre $2$ e $n$ usando a técnica do crivo de Eratóstenes. A idéia do método é começar com todos os inteiros no intervalo $[2,n]$ e eliminar, em cada iteração, os múltiplos próprios do primeiro primo considerado.

   
   
   

   Obs1: Dados dois inteiros $a$ e $b$, dizemos que $a$ é múltiplo próprio de $b$ se $a$ é múltiplo de $b$ e $a>b$.

   Obs2: Use a função da questão anterior, mesmo que você não a tenha feito. Não é necessário reescrever a função nesta questão.

   
   
   

   Exemplo: Seja $n=25$, consideremos o vetor $v$ com os $n-1$ elementos a seguir

   
   

   $$2,\;3,\;4,\;5,\;6,\;7,\;8,\;9,\;10,\;11,\;12,\;13,\;14,\;15,\;16,\;17,\; 18,\;19,\;20,\;21,\;22,\;23,\;24,\;25.$$
   
   

   Eliminando-se os múltiplos próprios de $2$ restam:

   
   

   $$2,\;3,\;5,7,\;9,\;11,\;13,\;15,\;17,\;19,\;21,\;23,\;25.$$
   
   

   Eliminando-se os múltiplos próprios de $3$ restam:

   
   

   $$2,\;3,\;5,\;7,\;11,\;13,\;17,\;19,\;23,\;25$$
   
   

   Eliminando-se os múltiplos próprios de $5$ restam:

   
   

   $$2,\;3,\;5,7,\;11,\;13,\;17,\;19,\;23$$
   
   

   Considerando os múltiplos próprios de $7$, $11$, $13$, $17$, $19$ e $23$ nenhum novo número é eliminado.
   

   
   
   

   SOLUÇÃO:
   

    
   #include <stdio.h>
   #define MAX 10000
   int elimina(int v[MAX], int n, int k);
   
   int main() {
      int i, n;
      int v[MAX];
   
      /* entrada dos dados */
      printf("Entre com n\n");
      scanf("%d", &n);
   
      /* carrega vetor */
      for (i=2; i <= n; i++)
        v[i-2] = i;
   
      /* elimina multiplos */
      i=0;
      while (i <= n-2) {
        printf("%d ", v[i]);
        n = n - elimina(v, n, v[i]);
        i++;
      }   
      printf("\n");
   
      return 0; /* FIM */
   }