MAC2166 Introdução à Computação para a Engenharia
# 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;
}
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
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,
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.
#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!
|
#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;
}
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,
Em geral, se Num[t] é ocultado na posição (i,j) da matriz D1, então tem-se que26 = 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, . . .
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çõesD1[i][j] = D[i][j] + Num[t] e (1) Num[t] = D1[i][j] - D[i][j] (2)
( 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 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 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].
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 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;
}
}
}