Introdução à Programação - Poli - P3 - em C - 2004

Prévia do material em texto

MAC2166 Introdução à Computação para a Engenharia
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 f0 (int v[4], int n)
{
 int i;
 for (i = 0; i < 4; i++)
 v[i] = v[i] + n;
}
void f1 (int v[4], int m[2][2])
{ 
 int i;
 for (i = 0; i < 4; i++)
 v[i] = m[i/2][i%2];
}
int f2 (int k, int *n)
{ 
 int i, j;
 i = 12; 
 j = 2;
 k = k + 1;
 *n = *n + 1;
 return k;
}
int main()
{
 int nusp, i, j, k, n;
 int a[2][2], v[4];
 printf ("Entre com seu no. USP: ");
 /* NA LINHA ABAIXO USE O SEU No. USP */
 scanf ("%d", &nusp); 
 printf ("nusp = %d\n", nusp);
 k = nusp / 10;
 n = k % 10; 
 printf ("1: k=%d n=%d\n", k, n);
 for (i = 0; i < 4; i++) 
 v[i] = i;
 printf("2: %d %d %d %d\n",v[0],v[1],v[2],v[3]);
 f0(v,n);
 printf("3: %d %d %d %d\n",v[0],v[1],v[2],v[3]);
 a[0][0] = 4; a[0][1] = 3; 
 a[1][0] = 2; a[1][1] = 1; 
 
 f1(v,a);
 printf("4: %d %d %d %d\n",v[0],v[1],v[2],v[3]);
 i = 0; j = 0;
 i = f2(j,&v[j]);
 printf("5: i=%d j=%d, k=%d\n",i, j, k);
 printf("6: %d %d %d %d\n",v[0],v[1],v[2],v[3]);
 i = 0; j = 0;
 i = f2(v[j],&j);
 printf("7: i=%d j=%d, k=%d\n",i, j, k);
 printf("8: %d %d %d %d\n",v[0],v[1],v[2],v[3]);
 return 0;
}
SOLUÇÃO
A resposta depende do penúltimo dígito do seu número USP. Teste com o seu no. USP e compare com a
resposta abaixo.
(0) (nusp/10) % 10 == 0.
Entre com seu no. USP: 1234501
nusp = 1234501
1: k=123450 n=0
2: 0 1 2 3
3: 0 1 2 3
4: 4 3 2 1
5: i=1 j=0, k=123450
6: 5 3 2 1
7: i=6 j=1, k=123450
8: 5 3 2 1
(1) (nusp/10) % 10 == 1.
Entre com seu no. USP: 1234511
nusp = 1234511
1: k=123451 n=1
2: 0 1 2 3
3: 1 2 3 4
4: 4 3 2 1
5: i=1 j=0, k=123451
6: 5 3 2 1
7: i=6 j=1, k=123451
8: 5 3 2 1
(2) (nusp/10) % 10 == 2.
Entre com seu no. USP: 1234521
nusp = 1234521
1: k=123452 n=2
2: 0 1 2 3
3: 2 3 4 5
4: 4 3 2 1
5: i=1 j=0, k=123452
6: 5 3 2 1
7: i=6 j=1, k=123452
8: 5 3 2 1
(3) (nusp/10) % 10 == 3.
Entre com seu no. USP: 1234531
nusp = 1234531
1: k=123453 n=3
2: 0 1 2 3
3: 3 4 5 6
4: 4 3 2 1
5: i=1 j=0, k=123453
6: 5 3 2 1
7: i=6 j=1, k=123453
8: 5 3 2 1
(4) (nusp/10) % 10 == 4.
Entre com seu no. USP: 1234541
nusp = 1234541
1: k=123454 n=4
2: 0 1 2 3
3: 4 5 6 7
4: 4 3 2 1
5: i=1 j=0, k=123454
6: 5 3 2 1
7: i=6 j=1, k=123454
8: 5 3 2 1
(5) (nusp/10) % 10 == 5.
Entre com seu no. USP: 1234551
nusp = 1234551
1: k=123455 n=5
2: 0 1 2 3
3: 5 6 7 8
4: 4 3 2 1
5: i=1 j=0, k=123455
6: 5 3 2 1
7: i=6 j=1, k=123455
8: 5 3 2 1
(6) (nusp/10) % 10 == 6.
Entre com seu no. USP: 1234561
nusp = 1234561
1: k=123456 n=6
2: 0 1 2 3
3: 6 7 8 9
4: 4 3 2 1
5: i=1 j=0, k=123456
6: 5 3 2 1
7: i=6 j=1, k=123456
8: 5 3 2 1
(7) (nusp/10) % 10 == 7.
Entre com seu no. USP: 1234571
nusp = 1234571
1: k=123457 n=7
2: 0 1 2 3
3: 7 8 9 10
4: 4 3 2 1
5: i=1 j=0, k=123457
6: 5 3 2 1
7: i=6 j=1, k=123457
8: 5 3 2 1
(8) (nusp/10) % 10 == 8.
Entre com seu no. USP: 1234581
nusp = 1234581
1: k=123458 n=8
2: 0 1 2 3
3: 8 9 10 11
4: 4 3 2 1
5: i=1 j=0, k=123458
6: 5 3 2 1
7: i=6 j=1, k=123458
8: 5 3 2 1
(9) (nusp/10) % 10 == 9.
Entre com seu no. USP: 1234591
nusp = 1234591
1: k=123459 n=9
2: 0 1 2 3
3: 9 10 11 12
4: 4 3 2 1
5: i=1 j=0, k=123459
6: 5 3 2 1
7: i=6 j=1, k=123459
8: 5 3 2 1
QUESTÃO 2
 Esta questão consiste na implementação de duas funções. Uma das funções é o main e a outra é uma função de
nome VetorLecker.
Dizemos que uma seqüência de números inteiros, sem elementos repetidos, é lecker se ela tem apenas 1
elemento que é maior que seus vizinhos. Por exemplo,
2 5 10 46 25 12 7 é lecker, pois 46 é único elemento que é maior que seus vizinhos, que são 10 e 25.
13 5 4 2 3 0 -3 -14 não é lecker, porque 13 é maior que 5 (5 é o único vizinho do 13) e 3 é maior que 2
e 0 (2 e 0 são os vizinhos do 3);
6 7 8 9 10 é lecker, pois apenas 10 é maior que seus vizinhos (9 é o único vizinho do 10).
7 6 é lecker, pois apenas 7 é maior que seus vizinhos (6 é o único vizinho de 7).
item (a) Escreva uma função de protótipo
 int VetorLecker(int vet[MAX], int n);
que recebe um número inteiro n, n >= 2, e um vetor vet com n elementos, sem elementos repetidos, e devolve 1
se o vetor é lecker e 0 em caso contrário.
A sua função não precisa fazer consistência dos dados. Em particular, ela não precisa verificar se o vetor contém
ou não elementos repetidos.
SOLUÇÃO
 #define TRUE 1
 #define FALSE 0
 int VetorLecker(int vet[MAX], int n)
 {
 int i;
 int no_maximos; 
 if (vet[0] > vet[1])
 {
 no_maximos = 1;
 }
 else
 {
 no_maximos = 0;
 }
 for (i = 1; i < n-1; i++)
 {
 if (vet[i-1] < vet[i] && vet[i] > vet[i+1]) 
 {
 no_maximos = no_maximos + 1; 
 }
 }
 if (vet[n-2] < vet[n-1])
 {
 no_maximos = no_maximos + 1;
 }
 if (no_maximos == 1) 
 {
 return TRUE;
 }
 else
 {
 return FALSE;
 }
 }
Uma matriz é lecker se suas linhas e colunas forem seqüências lecker.
item (b) Faça um programa que leia inteiros m e n, 2 <= m,n <= 100 e uma matriz Am x n de números inteiros, sem
elementos repetidos, e verifique se a matriz é lecker Utilize obrigatoriamente a função do item anterior mesmo
que você não a tenha feito.
O seu programa não precisa fazer consistência dos dados. Em particular, o seu programa não precisa verificar
se a matriz contém ou não elementos repetidos.
 numero de linhas = 3
 numero de colunas = 4
 matriz:
 1 2 3 4
 8 7 6 5
 9 10 11 12
 A matriz e lecker!
 numero de linhas = 3
 numero de colunas = 4
 matriz:
 1 2 3 5
 8 7 6 4
 9 10 11 12
 A matriz nao e lecker!
 numero de linhas = 4
 numero de colunas = 3
 matriz:
 1 2 3
 5 8 7
 6 4 9
 10 11 12
 A matriz nao e lecker!
 numero de linhas = 4
 numero de colunas = 3
 matriz:
 1 2 3
 5 8 7
 6 9 13
 10 11 12
 A matriz e lecker!
SOLUÇÃO
 #include <stdio.h>
 #define MAX 100
 #define TRUE 1
 #define FALSE 0
 int main()
 {
 int a[MAX][MAX];
 int v[MAX];
 int e_lecker;
 int i;
 int j; 
 int no_linhas;
 int no_colunas;
 /* leia as dimensoes da matriz */ 
 printf("Digite o numero de linhas: ");
 scanf("%d", &no_linhas);
 printf("Digite o numero de colunas: ");
 scanf("%d", &no_colunas);
 /* leia a matriz */
 for (i = 0; i < no_linhas; i++)
 {
 for (j = 0; j < no_colunas; j++) 
 {
 printf("Digite o elementos (%d,%d)"
 " da matriz: ", i, j);
 scanf("%d", &a[i][j]);
 }
 }
 
 /* verifique se cada linha e lecker */
 e_lecker = TRUE;
 i = 0;
 while (e_lecker == TRUE && i < no_linhas) 
 {
 /* verifique se a linha i e' lecker */
 for (j = 0; j < no_colunas; j++) 
 {
 v[j] = a[i][j];
 }
 e_lecker = VetorLecker(v, no_colunas);
 /* vamos para proxima linha */
 i = i + 1;
 }
 
 /* verifique se cada coluna e lecker */
 j = 0;
 while (e_lecker == TRUE && j < no_colunas) 
 {
 /* verifique se a coluna j e' lecker */
 for (i = 0; i < no_linhas; i++) 
 {
 v[i] = a[i][j];
 }
 e_lecker = VetorLecker(v, no_linhas);
 /* vamos para a proxima coluna */
 j = j + 1;
 }
 if (e_lecker == TRUE) 
 {
 printf("A matriz e lecker!\n");
 }
 else
 {
 printf("A matriz nao e lecker!\n");}
 return 0;
 }
QUESTÃO 3
 Esta questão consiste na implementação de quatro funções. Todas as funções são simplificações muito
grandes de alguns trechos de código que você escreveu para o seu EP4. Os nomes das funções são BeDeu,
Codifica, DeBeDeu, e DeCodifica.
Em computação é comum representar-se números naturais (inteiros >= 0) gigantescos através de vetores.
Considere as seguintes declarações:
 #define MAX 100
 #define MAX2 10000
 int Num[MAX2];
Nessa representação de números naturais gigantescos cada dígito decimal (algarismos entre 0 e 9) do número é
armazenado em uma posição do vetor Num e o total k de dígitos do número é guardado na posição Num[0]. Por
exemplo, o número 123456789012345678, de 18 dígitos, é armazenado da seguinte maneira
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Num ... 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 8 18
Ocultaremos um número natural gigantesco, armazenado em um vetor Num, através de uma matriz de inteiros D de
m linhas e n colunas. A ocultação consistirá em, a partir de Num e D, produzir uma matriz D1, também de m linhas e n
colunas. Cada dígito do número gigantesco será codificado numa única posição da matriz D1. O total kúnica
posição da matriz. Nem todas as posições da matriz D1 serão usadas pela codificação. Os valores nas
posições de D1 não usadas pela codificação serão idênticos aos respectivos valores de D.
Para a codificação será usado um esquema bastante simples. Suponha que o número a ser ocultado é
7389 que tem a representação
5 4 3 2 1 0
Num ... 7 3 8 9 4
Uma matriz D e a matriz D1 obtida pela ocultação de 7389 em D, estão logo a seguir. As posições em
destaque são as usadas para codificar o número total k de dígitos (=Num[0]}=4) e cada um dos k
dígitos de Num. 
D 0 1 2 3 4 5 6
0 11 12 13 14 15 16 17
1 21 22 23 24 25 26 27
2 31 32 33 34 35 36 37
3 41 42 43 44 45 46 47
D1 0 1 2 3 4 5 6
0 11 12 13 14 15 16 17
1 21 26 23 33 25 34 27
2 31 32 33 34 35 36 37
3 41 45 43 51 45 46 47
Note que,
 26 = D1[1][1] = D[1][1] + Num[0] = 22 + 4 = 26, 
 33 = D1[1][3] = D[1][3] + Num[1] = 24 + 9 = 33,
 34 = D1[1][5] = D[1][5] + Num[2] = 26 + 8 = 34, . . .
Em geral, se Num[t] é ocultado na posição (i,j) da matriz D1, então tem-se que
 D1[i][j] = D[i][j] + Num[t] e (1)
 Num[t] = D1[i][j] - D[i][j] (2)
Seja d >= 1 o espaçamento entre linhas e colunas das posições da matriz D1 que receberão a
codificação de Num. No exemplo acima tem-se que d = 2 e as posições que receberam codificação foram
(1,1), (1,3), (1,5), (3,1) e (3,3). Em geral, nem todas as posições da matriz D1 recebem
codificação, mas apenas as primeiras k+1 dentre as posições
 ( d-1,d-1), ( d-1,2d-1), ... , (d-1,(n/d)d-1),
 (2d-1,d-1), (2d-1,2d-1), ... , (2d-1,(n/d)d-1),
 . . . .
 . . . .
 . . . .
((m/d)d-1,d-1), ((m/d)d-1,2d-1), ... , ((m/d)d-1,(n/d)d-1),
e nesta ordem. A posição (d-1,d-1) receberá a codificação de Num[0] (= k), a posição (d-1,2d-1)
receberá a codificação de Num[1], a posição (d-1,3d-1) receberá a codificação de Num[2]... Isto dá
um total de (m/d)(n/d) posições disponíveis para receber uma codificação dos k+1 números (Num[0],
Num[1],..., Num[k]).
Portanto, para codificarmos Num através D deve-se ter que
 (m/d)(n/d) >= k + 1 (3)
Em nosso exemplo, d=2, as posições disponíveis são (1,1), (1,3), (1,5), (3,1), (3,3), (3,5), o que
dá um total de (m/d)(n/d) = (4/2)(7/2) = 2 x 3 = 6 posições, que por sua vez é maior ou igual a 5 =
k+1, que é o número de inteiros de Num a serem codificados. Das 6 posições disponíveis, apenas as 5
primeiras foram utilizadas na codificação.
Durante a decodificação, a partir de D1 e D, obtém-se o vetor Num.
item (a) Escreva uma função de protótipo
 int BeDeu (int m, int n, int k);
que devolve o maior valor inteiro d >= 1 que satisfaça à equação (3) ou devolve 0 caso não exista
um tal d.
SOLUÇÃO
/*
 * SOLUÇÃO 1
 */
 int BeDeu (int m, int n, int k) 
 {
 int d; /* espacamento entre as codificacoes */
 if (m*n < k+1) 
 {
 d = 0;
 } 
 else 
 {
 d = m;
 while ((m/d)*(n/d) < k+1)
 {
 d = d - 1;
 }
 }
 return d;
 }
/*
 * SOLUÇÃO 2
 */
 int BeDeu (int m, int n, int k) 
 {
 int d; /* espacamento entre as codificacoes */
 d = 1;
 while ((m/d)*(n/d) >= k+1)
 {
 d = d + 1;
 }
 d = d - 1;
 return d;
 }
item (b) Escreva uma função de protótipo
 int Codifica (int D[MAX][MAX], int m, int n, int Num[MAX2],
 int Dl[MAX][MAX]);
Esta função deve usar obrigatoriamente a função BeDeu para calcular o espaçamento d e deve devolver
d. Se d > 0 a função devolve em Dl a matriz com a codificação dos Num[0]+1 inteiros de Num a partir
da matriz D. A codificação utiliza a equação (1). Você pode usar a função BeDeu mesmo que não a
tenha feito.
SOLUÇÃO
/*
 * SOLUÇÃO 1
 */
int Codifica (int D[MAX][MAX], int m, int n, int Num[MAX2],
 int D1[MAX][MAX]) 
 {
 int d; /* espacamento entre as codificacoes */
 int k; /* total de digitos do numero */
 int i; /* indice das linhas */
 int j; /* indice das colunas */
 int t; /* indice de Num */
 k = Num[0];
 d = BeDeu(m, n, k);
 /* copie D em D1 (pode fazer isto dentro do if abaixo) */ 
 for (i = 0; i < m; i++) 
 for (j = 0; j < n; j++)
 D1[i][j] = D[i][j];
 if (d > 0) 
 { 
 i = d - 1;
 j = d - 1;
 for (t = 0; t <= k; t++) 
 {
 D1[i][j] = D[i][j] + Num[t];
 j = j + d;
 if (j >= n) 
 {
 i = i + d;
 j = d - 1;
 }
 }
 }
 return d;
 }
/*
 * SOLUÇÃO 2
 */
int Codifica (int D[MAX][MAX], int m, int n, int Num[MAX2],
 int D1[MAX][MAX]) 
 {
 int k; /* total de digitos do numero */
 int d; /* espacamento entre as codificacoes */
 int i; /* indice das linhas */
 int j; /* indice das colunas */
 int t; /* indice de Num */
 k = Num[0];
 d = BeDeu(m, n, k);
 /* copie D em D1 (pode fazer isto dentro do if abaixo) */ 
 for (i = 0; i < m; i++) 
 for (j = 0; j < n; j++)
 D1[i][j] = D[i][j];
 if (d > 0) 
 { 
 /* versao mais popular */
 t = 0;
 for (i = d-1; i < m && t <= k; i = i+d)
 { /* pode apagar o i < m acima */ 
 for (j = d-1; d < n && t <= k; j = j+d) 
 {
 D1[i][j] = D[i]D[j] + Num[t] ;
 t = t + 1;
 }
 }
 }
 return d;
 }
item (c) Escreva uma função de protótipo
 void DeBeDeu (int D[MAX][MAX], int m, int n, int Dl[MAX][MAX],
 int *pd, int *pk);
que devolve em *pd o valor do espaçamento d usado na codificação e em *pk o valor do total de
dígitos k (=Num[0]) do número codificado. A matriz de inteiros D é a matriz original e Dl é a
matriz codificada. A decodificação utiliza a equação (2). Observe que d-1 é o menor inteiro i tal
que
 D[i][i] != D1[i][i].
SOLUÇÃO
 void DeBeDeu (int D[MAX][MAX], int m, int n, int Dl[MAX][MAX],
 int *pd, int *pk);
 {
 int k; /* total de digitos do numero */
 int d; /* espacamento entre as codificacoes */
 int i; /* indice das matrizes */
 i = 0;
 while (D[i][i] == D1[i][i]) /* na representacao de 0 
 { * k == Num[0] == 1 
 i = i + 1 */
 }
 d = i + 1;
 k = D1[i][i] - D[i][i];
 *pd = d;
 *pk = k;
 }
 }
item (d) Escreva uma função de protótipo
 void DeCodifica(int D[MAX][MAX],int m, int n, 
 int Dl[MAX][MAX], int Num[MAX2]);
que devolve em Num o vetor de inteiros que foi usado na codificação que resultou na matriz
codificada D1, obtida a partir da matriz original D. Ambas as matrizes têm m linhas e n colunas. A
decodificação utiliza a equação (2). Esta função deve usar obrigatoriamente a função DeBeDeu do
item (c). Você pode usar a função DeBeDeu mesmo que não a tenha feito.
SOLUÇÃO
/*
 * SOLUÇÃO 1
 */
 void DeCodifica(int D[MAX][MAX], int m, int n, 
 int Dl[MAX][MAX], int Num[MAX2]);
 {
 int d; /* espacamento entre as codificacoes */
 int k; /* total de digitos do numero */
 int i; /* indice das linhas */
 int j; /* indice das colunas */
 int t; /* indice de Num */
 DeBeDeu(D, m, n, Dl, &d, &k);
 i = d - 1;
 j = d - 1;
 for (t = 0; t <= k; t++) 
 {
 Num[t] = D1[i][j] - D[i][j];
 j = j + d;
 if (j >= n) 
 {
 i = i + d;
 j = d - 1;
 }
 }
 }
/*
 * SOLUÇÃO 2
 */
 void DeCodifica(int D[MAX][MAX], int m, int n, 
 int Dl[MAX][MAX], int Num[MAX2]);
 { 
 int d; /* espacamento entre as codificacoes */
 int k; /* total de digitos do numero */
 int i; /* indice das linhas */
 int j; /* indice das colunas */
 int t; /* indice de Num */
 DeBeDeu(D, m, n, Dl, &d, &k);
 t = 0;
 for (i = d-1; i < m && t <= k; i = i+d)
 { /* pode apagar o i < m acima */
 for (j = d-1; j < n && t <= k; j = j+d) 
 {
 Num[t] = D1[i][j] - D[i][j];
 t = t + 1;
 }
 }
 }
 
 
 
Last modified: Wed Jul 7 09:34:15 BRT 2004
	Prova 3
	QUESTÃO 1
	QUESTÃO 2
	QUESTÃO 3