Departamento de Ciência da Computação - IME - USP

MAC2166 Introdução à Computação

Prova 3

QUESTÃO 1

Simule a execução do programa abaixo, destacando a sua saída. A saída do programa consiste em tudo que resulta dos comandos printf's e o número digitado pelo usuário. O dado de entrada (variável nusp) é o seu número USP.

#include <stdio.h>

void f1 (int v[4], int k) {
  int i;
  k= 2;
  for (i=0; i<4; i++)
    v[i] = v[i] / k;
}

void f2 (int m[2][2], int v[4]) {
  int i, j;
  for (i=0; i<2; i++)
    for (j=0; j<2; j++)
      m[i][j] = v[2*i+j];
}

int f3 (int *k, int *j) {
  int i;
  i = 1;
  *j = 1;
  *k = *k + i;
  return *k;
}

int main () {
  int nusp, k, n, i, j, d, a[2][2], v[4];
  char c;

  printf ("Entre com seu no. USP: ");
  /* na linha abaixo entre com o seu numero USP */
  scanf ("%d", &nusp);
  printf("nusp=%d\n", nusp);

  k = nusp / 10;
  n = k % 5;
  printf("1: k=%d n=%d\n", k, n);
  if (n > 4)
    n = 5;

  for (i = 0; i < 4; i++)
    v[i] = i + n;
  printf("2: n=%d v=(%d %d %d %d) \n", n, v[0], v[1], v[2], v[3]);

  f1(v, n);
  printf("3: n=%d v=(%d %d %d %d) \n", n, v[0], v[1], v[2], v[3]);

  for (i=0; i<4; i++)
    v[i] = i+n;
  printf("4: n=%d v=(%d %d %d %d) \n", n, v[0], v[1], v[2], v[3]);

  f2(a,v);
  printf("5: %d %d\n", a[0][0],  a[0][1]); 
  printf("6: %d %d\n", a[1][0],  a[1][1]); 

  i = 2;
  j = 3;
  v[i] = f3(&v[j], &j);
  printf("7: %d %d %d %d \n", v[0],v[1],v[2],v[3]);

  c = 'a'+n+1;
  printf("8: %c\n", c);
  return 0;
}

SOLUÇÃO
A resposta depende do resto da divisão do segundo dígito menos significativo do seu número USP por 5. Por exemplo, para no. USP = 1234569 o dígito 6 é o segundo menos significativo e o resultado da simulação depende do número 6%5 == 1, ou seja, depende do valor de (nusp/10)%5. Teste com o seu no. USP e compare a resposta.

(0) (nusp/10)%5 == 0. Veja os 2 exemplos abaixo.

Entre com seu no. USP: 1234509
nusp=1234509
1: k=123450 n=0
2: n=0 v=(0 1 2 3) 
3: n=0 v=(0 0 1 1) 
4: n=0 v=(0 1 2 3) 
5: 0 1
6: 2 3
7: 0 1 4 4 
8: b

Entre com seu no. USP: 1234559
nusp=1234559
1: k=123455 n=0
2: n=0 v=(0 1 2 3) 
3: n=0 v=(0 0 1 1) 
4: n=0 v=(0 1 2 3) 
5: 0 1
6: 2 3
7: 0 1 4 4 
8: b

(1) (nusp/10)%5 == 1. Veja os 2 exemplos abaixo.

Entre com seu no. USP: 1234519
nusp=1234519
1: k=123451 n=1
2: n=1 v=(1 2 3 4) 
3: n=1 v=(0 1 1 2) 
4: n=1 v=(1 2 3 4) 
5: 1 2
6: 3 4
7: 1 2 5 5 
8: c

Entre com seu no. USP: 1234569
nusp=1234569
1: k=123456 n=1
2: n=1 v=(1 2 3 4) 
3: n=1 v=(0 1 1 2) 
4: n=1 v=(1 2 3 4) 
5: 1 2
6: 3 4
7: 1 2 5 5 
8: c

(2) (nusp/10)%5 == 2. Veja os 2 exemplos abaixo.

Entre com seu no. USP: 1234529
nusp=1234529
1: k=123452 n=2
2: n=2 v=(2 3 4 5) 
3: n=2 v=(1 1 2 2) 
4: n=2 v=(2 3 4 5) 
5: 2 3
6: 4 5
7: 2 3 6 6 
8: d

Entre com seu no. USP: 1234579
nusp=1234579
1: k=123457 n=2
2: n=2 v=(2 3 4 5) 
3: n=2 v=(1 1 2 2) 
4: n=2 v=(2 3 4 5) 
5: 2 3
6: 4 5
7: 2 3 6 6 
8: d

(3) (nusp/10)%5 == 3. Veja os 2 exemplos abaixo.

Entre com seu no. USP: 1234539
nusp=1234539
1: k=123453 n=3
2: n=3 v=(3 4 5 6) 
3: n=3 v=(1 2 2 3) 
4: n=3 v=(3 4 5 6) 
5: 3 4
6: 5 6
7: 3 4 7 7 
8: e

Entre com seu no. USP: 1234589
nusp=1234589
1: k=123458 n=3
2: n=3 v=(3 4 5 6) 
3: n=3 v=(1 2 2 3) 
4: n=3 v=(3 4 5 6) 
5: 3 4
6: 5 6
7: 3 4 7 7 
8: e

(4) (nusp/10)%5 == 4. Veja os 2 exemplos abaixo.

Entre com seu no. USP: 1234549
nusp=1234549
1: k=123454 n=4
2: n=4 v=(4 5 6 7) 
3: n=4 v=(2 2 3 3) 
4: n=4 v=(4 5 6 7) 
5: 4 5
6: 6 7
7: 4 5 8 8 
8: f

Entre com seu no. USP: 1234599
nusp=1234599
1: k=123459 n=4
2: n=4 v=(4 5 6 7) 
3: n=4 v=(2 2 3 3) 
4: n=4 v=(4 5 6 7) 
5: 4 5
6: 6 7
7: 4 5 8 8 
8: f

QUESTÃO 2

Considere o seguinte fragmento de programa:

#include <math.h>

#define MAX 100
#define PI  3.141592654

float oscilador (int n, int R, float freq) {
  return sin(2*PI*freq*n/R);
}

(a) Escreva uma função somaosciladores que recebe dois inteiros n e R, um inteiro M <= MAX, um vetor f contendo os reais f₀,. . .,f_M-1 e um vetor a contendo os reais a₀,. . .,a_M-1, e devolve o valor da expressão

a₀ sin (2 PI f₀ n/ R) + a₁ sin (2 PI f₁ n/ R) + . . . + a_M-1 sin (2 PI f_M-1 n/ R)

Sua função deve utilizar a função oscilador definida acima.

SOLUÇÃO

/* 
 * Solucao:
 */
#define MAX 100

float oscilador (int n, int R, float freq);

float somaosciladores(int n, int R, int M, float f[MAX], float a[MAX]) {
  float soma = 0;
  int i;

  for (i = 0; i < M; i++)
    soma = soma + a[i]*oscilador(n, R, f[i]);
  return soma;
}

(b) Escreva uma função com protótipo

void processaevento (int N, int R, int M, float f[MAX], float a[MAX],
                            float beta_inicial, float beta_final);

que recebe como parâmetros um inteiro N, um inteiro R, um inteiro M <= MAX, um vetor f contendo os reais f₀,. . .,f_M-1, um vetor a contendo os reais a₀,. . .,a_M-1 e dois reais beta_inicial e beta_final, e escreve na tela uma lista de N amostras (valores reais) dadas pela expressão

beta(n) × (a₀ sin (2 PI f₀ n/ R) + a₁ sin (2 PI f₁ n/ R) + . . . + a_M-1 sin (2 PI f_M-1 n/ R))

para os valores n=0,. . .,N-1. Nesta expressão, beta(n) é o valor linearmente interpolado entre beta_inicial e beta_final, e é dado pela fórmula

beta(n)=(1-n/N)beta_inicial+ (n/N) beta_final}.

Você deve utilizar a função somaosciladores do item (a), mesmo que não a tenha feito. Se você não a fez, escreva o seu protótipo antes da resolução deste item.

SOLUÇÃO

/* 
 * Solucao:
 */
float somaosciladores (int n, int R, int M, float f[MAX], float a[MAX]); 

void processaevento(int N, int R, int M, float f[MAX], float a[MAX],
                    float beta_inicial, float beta_final) {
  float betan;
  int n;

  for (n = 0; n < N; n++) {
    betan=(1-(float)n/N)*beta_inicial+(float)n/N*beta_final;
    printf("%f\n",betan*somaosciladores(n, R, M, f, a));
  }
}

(c) Escreva um programa que leia do teclado um inteiro positivo E que representa o número de eventos, um inteiro positivo R que representa a taxa de amostragem e, depois, para cada evento j=0,. . ., E-1, leia um inteiro N que representa o número de amostras do evento j, um inteiro positivo M <= MAX que representa o número de osciladores do evento j, uma lista de M números reais f₀,. . .,f_M-1 e outra lista de M números reais a₀,. . . ,a_M-1 que representam freqüências e amplitudes de cada oscilador no evento j, bem como dois números reais beta_inicial e beta_final que representam os valores inicial e final do envelope do evento j. Seu programa deve imprimir na tela a lista de N amostras reais relativas a este evento. Você deve utilizar a função processaevento do item (b), mesmo que não a tenha feito.

SOLUÇÃO

/* 
 * Solucao:
 */
#include <stdio.h>
#define MAX 100

int main() {
  int E, M, R, N, j, i;
  float f[MAX], a[MAX], beta_inicial, beta_final;
  
  scanf("%d %d", &E, &R);
  for (j = 0; j < E; j++) {
    scanf("%d %d", &N, &M); 
    for (i = 0; i < M; i++)
      scanf("%f", &f[i]);
    for (i = 0; i < M; i++)
      scanf("%f", &a[i]);
    scanf("%f %f", & beta_inicial, & beta_final);
    processaevento(N, R, M, f, a, beta_inicial, beta_final);
  }
  return 0;
}

QUESTÃO 3

(a) Escreva uma função busca que recebe como parâmetros um inteiro x, dois inteiros m e n, 1 <= m <= 10, 1 <= n <= 10, uma matriz inteira A_m×n e um índice de linha i, 0 <= i < m. Sua função deve devolver -1 se x não aparece na linha i da matriz A e, caso contrário, deve devolver o menor j tal que A[i][j]=x e 0 <= j < n.

SOLUÇÃO

/*
 * Solucao:
 *
 */
int busca (int x, int n, int m, int A[10][10], int i) {             
  int j; 
  int resposta;

  j = 0;
  resposta = -1;
  while (j < n && resposta == -1)
    if (A[i][j] == x)
      resposta = j
    else
      j = j + 1;

  return resposta;
}

(b) Escreva uma função com protótipo

int ultimo (int t, int v[100], int m, int n, int A[10][10], int i, int *j);

que recebe como parâmetros de entrada

um inteiro t <= 100,
um vetor v contendo os inteiros diferentes v0,. . .,v_t-1,
dois inteiros m e n, com 1 <= m <= 10, 1 <= n <= 10,
uma matriz A_m×n contendo inteiros diferentes, onde cada um de seus elementos aparece entre v₀,. . .,v_t-1,
um inteiro i, com 0 <= i < m, indicando uma linha da matriz A.

Sua função deve devolver o maior k, 0 <= k < t, tal que v_k aparece na linha i da matriz A. Além disso, sua função deve colocar em *j o índice da coluna tal que A[i][*j] = v_k e 0 <= *j < n. Você deve utilizar a função busca do item (a), mesmo que não a tenha feito. Se você não a fez, escreva o seu protótipo antes da resolução deste item.

Exemplo:

Para t = 16, 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... v 11 17 50 10 14 99 80 33 18 42 15 34 72 51 45 35 ... m = 3, n = 4,

A 0 1 2 3

0 15 35 51 72

1 17 99 18 10

2 45 34 11 80

a função deve devolver 8 e *j deve receber 2.

SOLUÇÃO

/*
 * Solucao 1:
 *
 */
int ultimo (int t, int v[100], int m, int n, int A[10][10], int i, int *j){
  int k; 

  /* procura o último elemento de v que aparece na linha i */
  k = t-1; 
  *j = busca(v[k], n, m, A, i); 
  while (*j == -1) {
    k = k - 1; 
    *j = busca(v[k], n, m, A, i);
  }

  return k;
}

/*
 * Solucao 2:
 *
 */
int ultimo (int t, int v[100], int m, int n, int A[10][10], int i, int *j) {
  int k, aux, resp; 

  for (k = 0; k < t; k++) {
    aux = busca(v[k], n, m, A, i); 
    if (aux != -1) {
      *j = aux;
      resp = k; 
    }
  }

  return resp;
}

(c) Escreva um programa em C que leia

dois inteiros m e n tais que 1 <= m <= 10, 1 <= n <= 10,
uma matriz inteira BINGO_{m × n}, representando uma cartela de bingo: os números armazenados na matriz BINGO são inteiros entre 1 e 100, todos diferentes, e
um vetor SORTE com 100 números inteiros, contendo todos os inteiros de 1 a 100, que representa a ordem em que os números foram sorteados,

e que imprima

o índice da primeira linha da matriz BINGO a ser preenchida,
em que sorteio ela foi preenchida e
qual o último elemento da linha que foi sorteado.

No seu programa, você deve utilizar a função ultimo do item (b), mesmo que não a tenha feito. Se você não a fez, escreva o seu protótipo antes da resolução deste item.

Exemplo

Para m = 3, n = 4 e

BINGO 0 1 2 3

0 15 35 51 72

1 17 99 18 10

2 45 34 11 80

e

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
SORTE 11 17 50 10 14 99 80 33 18 42 15 34 72 51 45 35 ...
A linha 1 foi a primeira preenchida.
O últim elemento sorteado da linha foi o 18, que foi o 9-ésimo número sorteado.

SOLUÇÃO

/*
 * Solucao 1:
 *
 */
#include <stdio.h>

int main() {                                    
  int bingo[10][10], sorte[100], m, n, i, j, min, ult, lin, col; 

  scanf("%d %d", &m, &n); 
  for (i = 0; i < m; i++)
    for (j = 0; j < n; j++) 
      scanf("%d", &bingo[i][j]); 
  for (i = 0; i < 100; i++)
    scanf("%d", &sorte[i]); 

  /* procura a linha que é preenchida primeiro */
  min = 100;            
  for (i = 0; i < m; i++) {
    ult = ultimo(100, sorte, i, m, n, bingo, &j); 
    if (ult < min) {
      min = ult;
      lin = i; 
      col = j;
    }
  }
  printf("A linha %d foi a primeira preenchida!\n", lin);
  printf("O ultimo elemento sorteado da linha foi o %d,"
         " que foi o %d-esimo numero sorteado.\n", bingo[lin][col], min+1); 
  return 0;
}

/*
 * Solucao 2: Identica a solucao 1.
 *
 */
#include <stdio.h>

int main() {                                    
  int bingo[10][10], sorte[100], m, n, i, j, min, ult, lin; 

  scanf("%d %d", &m, &n); 
  for (i = 0; i < m; i++)
    for (j=0; j< n; j++) 
      scanf("%d", &bingo[i][j]); 
  for (i = 0; i < 100; i++)
    scanf("%d", &sorte[i]); 

  /* procura a linha que é preenchida primeiro */
  min = 100;            
  for (i = 0; i < m; i++) {
    ult = ultimo(100, sorte, i, m, n, bingo, &j); 
    if (ult < min) {
      min = ult;
      lin = i; 
    }
  }
  printf("A linha %d foi a primeira preenchida!\n", lin);
  printf("O ultimo elemento sorteado da linha foi o %d,"
         " que foi o %d-esimo numero sorteado.\n", v[min], min+1); 
  return 0;
}

Last modified: Fri Jul 12 16:58:08 BRT 2013

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
`v`	11	17	50	10	14	99	80	33	18	42	15	34	72	51	45	35	...

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
`SORTE`	11	17	50	10	14	99	80	33	18	42	15	34	72	51	45	35	...

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
`v`	11	17	50	10	14	99	80	33	18	42	15	34	72	51	45	35	...

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
`v`	11	17	50	10	14	99	80	33	18	42	15	34	72	51	45	35	...