Retornar para [[Primeira Prova - 2005-1]]
====== Resolução da Primeira Prova de 2005-1 ======
===== Algoritmo de solução =====
Para resolver este problema vamos começar por criar um algoritmo. Ele é bem simples:
**Exemplo 1.1. Algoritmo de Solução**
/*
Enquanto não for fim de arquivo {
Lê linha;
Soma linha;
Criptografa linha;
Imprime linha criptografada;
}
Imprime soma;
*/
Vamos começar pelo mais fácil. Do livro temos a estrutura básica do programa no **item 1.9** e temos a //função lelinha()// (getline na versão em inglês). Também é dito no enunciado que os caracteres de nova linha e tabulação devem ser tratados como espaço em branco. De acordo com o item 1.9 podemos modificar nosso algoritmo inicial:
**Exemplo 1.2. Algoritmo melhorado**
/*
Solução
Enquanto (há outra linha) {
filtra tabulações e novas linhas;
Soma linha;
Criptografa linha;
Imprime linha criptografada;
}
Imprime soma;
*/
===== Primeira versão =====
Do enunciado do texto, podemos inferir algumas constantes como **MAXLINHA** e **MAXPRINT**, nosso cabeçalho seria este:
**Exemplo 1.3. Primeiras definições**
#include
#define MAXLINHA 100
#define MAXPRINT 80
A criação de variáveis é bem simples: do **item 1.9** tiramos **"tam"** e a string **"linha"**. Também criamos a variável **"soma"**, para guardar a soma de todas as letras do texto. Comecemos a programar ([[c:p1versao1|versão 1]]):
**Exemplo 1.4. Primeira versão**
#include
#include
#define MAXLINHA 100
#define MAXPRINT 80
int lelinha(char s[],int lim);
void imprime(char s[],int lim);
void filtraespacos(char s[]);
void criptografa(char s[]);
int sumchar(char s[]);
int main()
{
int tam, soma=0;
char linha[MAXLINHA];
while ((tam=lelinha(linha,MAXLINHA))>0)
{
filtraespacos(linha);
soma+=sumchar(linha);
criptografa (linha);
imprime (linha, MAXPRINT);
}
// printf("\nSoma é %d\n",soma);
}
int lelinha(char s[],int lim){
}
void imprime(char s[],int lim){
}
void filtraespacos(char s[]){
}
void criptografa(char s[]){
}
int sumchar(char s[]){
}
===== Primeiro ponto: Versões 2 e 3 =====
Este programa ainda não faz nada de útil. Vamos completar o que falta. Primeiro //lelinha()// que copiamos diretamente do **item 1.9** do livro ([[c:p1versao2|versão 2]]) .
**Exemplo 1.5. lelinha()**
int lelinha(char s[],int lim)
{
int c,i;
for (i=0; i
Vamos garantir o primeiro ponto: **tratamento correto para linhas com mais de 100 caracteres**. Para isso, basta tratar este caso em //main()// e em //lelinha()//. Este caso é semelhante ao exercício dado em sala de aula (**ex 1.16**). Como o enunciado não diz se devemos parar o programa ou não, escolhemos continuar o processamento após a mensagem de erro.
Primeiro modificamos lelinha() para ele não parar de contar após ter atingido seu limite. Usaremos uma variável **j**.
**Exemplo 1.6. lelinha() modificado**
//Função para ler linha até encontrar caracter de nova linha ou fim de arquivo.
//Versão modificada para continuar lendo após final de espaço em s[]
int lelinha(char s[],int lim)
{
int c,i;
for (i=0; (c=getchar())!=EOF && c!='\n';++i)
if (i
Depois modificamos main() ([[c:p1versao3|versão 3]]) .
**Exemplo 1.7. main() modificado para detectar erro de excesso de caracteres**
int main()
{
int tam, soma=0;
char linha[MAXLINHA];
while ((tam=lelinha(linha,MAXLINHA))>0)
{
if (tam>=MAXLINHA )
printf("\nErro: linha maior que o permitido\n");
filtraespacos(linha);
soma+=sumchar(linha);
criptografa (linha);
imprime (linha, MAXPRINT);
}
printf("\nSoma é %d\n",soma);
}
Esta versão já faz algo: Lê do teclado até encontrar o final do arquivo e detecta erro de excesso de caracteres na entrada.
Segundo ponto: saída formatada
Agora, vamos garantir mais 1 ponto na prova. Fazemos o mais fácil: **imprimir em 80 letras por linha ([[c:p1versao4|versão 4]])** .
**Exemplo 1.8. Função imprime()**
void imprime(char s[], int lim)
{
int i=1;
int j=0;
while( s[j]!='\0')
{
printf((i%lim)? "%c":"%c\n",s[j++]);
i++;
}
}
Começamos a variável **"i"** com o valor **1** para que ela conte exatamente **"lim"** caracteres antes de escrever a nova linha. Se ela começasse com **0**, no primeiro teste da linha o resto seria zero e seria escrito a nova linha.
Vamos compilar e testar. Para isso, é melhor reduzir a constante **MAXPRINT** para um valor mais baixo, digamos **20**.
Um teste simples mostra que funciona mas... e se tentarmos com várias linhas? Oops.. o ponto ainda não é nosso.
neste caso vemos que a cada nova linha ele recomeça a contar de zero a posição na linha. Devemos usar uma variável que preserve seu valor entre as chamadas. Poderíamos usar uma variável global, assim ([[c:p1versao5|versão 5]]) :
**Exemplo 1.9. imprime() melhorado**
int posicaoPrint=1;
void imprime(char s[], int lim)
{
int j=0;
while( s[j]!='\0')
{
printf((posicaoPrint%lim)? "%c":"%c\n",s[j++]);
posicaoPrint++;
}
}
===== Extraindo tabulações e novas linhas =====
O resultado ainda não é satisfatório, pois temos os caracteres de final de linha em todas as linhas. Então vamos melhorar nosso programa eliminando os caracteres de final de linha e tabulação com a função //filtraespacos()//. Ela também é bem simples: ([[c:p1versao6|versão 6]])
**Exemplo 1.10. filtraespacos()**
void filtraespacos(char s[])
{
int i;
for (i=0; s[i]!='\0'; i++)
if (s[i]=='\n' || s[i]=='\t')
s[i]=' ';
}
===== Mais um ponto: soma de caracteres =====
Partimos para mais um ponto: soma correta dos caracteres. Como já eliminamos os caracteres de tabulação e nova linha, esta rotina será assim ([[c:p1versao7|versão 7]]) :
**Exemplo 1.11. sumchar()**
int sumchar(char s[])
{
int i, soma=0;
for (i=0;s[i]!='\0';i++)
soma+=(int)s[i];
return soma;
}
===== Finalmente a criptografia! =====
Agora chegamos ao mais difícil: a criptografia do texto.
Vamos começar definindo algumas strings. Primeiro, vamos usar a string com a matrícula e seu tamanho:
**Exemplo 1.12. String da matrícula**
char mat[]="199112340567";
int tamMat=12;
A segunda string vai ser essencial no processo de criptografia. Escolhemos o meio mais fácil, ou seja, uma que permita fazer apenas criptografia em avanço, para garantir um ponto:
**Exemplo 1.13. string letras[]**
char letras[]=" abcdefghijklmnopqrstuvwxyz";
int tamLetras=27;
Para calcular o índice que vai ser usado, para letras entre **'a'** e **'z'**, usamos a expressão:
**novaletra= letra[pos_em_letras + deslocamento]**
O deslocamento é calculado usando a string **mat**. Para isso precisamos de um contador que vai manter o índice de mat entre as várias linhas. Como este valor deve ficar entre **0** e **11**, podemos usar a fórmula: **pos%tamanho_de_mat**.
O tamanho da matrícula é **12**. Criamos a variável **tamMat**, que guarda este valor.
**deslocamento= mat[j%tamMat]**.
A posição em letras é dada pela fórmula:
**s[i]-'a'+1 **(O valor 1 é por causa do caracter espaço inicial).
Juntando tudo, temos:
**s[i]= letras[(s[i]-'a'+1+(mat[j%tamMat]-'0'))%tamLetras]**
Veja que usamos o resto da expressão pelo tamanho da string letras de modo que se o valor ultrapassar 26, o índice seja calculado corretamente, voltando para o início da string.
Façamos um teste. Se a letra a ser convertida for **'b'** e o dígito da matrícula for **'2'**, **s[i]-'a'** dá **1**. Somando 1, temos 2.
Na matrícula **'2'-'0'** dá **2** e o resultado final é **4**. então o resultado será a letra de índice **4** em **letras[]**. Isto dá **'d'**. O resultado está correto.
Peguemos o final da string. Com a letra sendo **'z'**. **s[i]-'a'** dá **25**. Mais 1, dá **26**, mais 2(de mat[j%tamMat]-'0'), dá **28** cujo resto por **27** dá **1**. A letra com índice **1** é **'a'** e a criptografia foi correta.
Isto ainda não contempla o espaço em branco, que deve ser tratado como um caso à parte. Para o espaço, já sabemos que seu índice na string **letras[]** é **0**. O cálculo fica:
**s[i]=letras[mat[j%tamMat]-'0']**
Nestes casos, **j** deve manter seu valor entre várias chamadas. Ele será feito global com o nome de **'pos'**. ([[c:p1versao8|versão 8]])
**Exemplo 1.14. primeira versão de criptografa()**
int pos=0;
void criptografa(char s[])
{
char mat[]="199112340567";
char letras[]=" abcdefghijklmnopqrstuvwxyz";
int tamLetras=27;
int tamMat=12;
int i=0;
while (s[i]!='\0'){
if (s[i] >='a' && s[i]<='z')
s[i]= letras[(s[i]-'a'+1+(mat[pos%tamMat]-'0'))%tamLetras];
else if (s[i]==' ')
s[i]=letras[mat[pos%tamMat]-'0'];
pos++;
i++;
}
}
===== Tratando maiúsculas =====
Em nossa solução ainda não tratamos o caso de maiúsculas.
Isto pode ser feito da seguinte forma, usando uma variável booleana que vai guardar este valor, definindo antes **TRUE** e **FALSE** e testando no fim o valor de **"maiuscula"**:
**Exemplo 1.15. Testa maiúsculas**
#define TRUE 1
#define FALSE 0
int maiuscula=FALSE;
...
if (s[i]>='A' &&s[i]<='Z'){
maiuscula=TRUE;
s[i]=s[i]-'A' + 'a';
}
...
if (maiuscula){
s[i]=s[i]-'a'+'A';
maiuscula=FALSE;
}
Juntando tudo obtemos a nova versão de nossa solução ([[c:p1versao9|versão 9]]).
===== Tratando o retrocesso =====
Nossa solução funciona para todos os casos, menos o caso de retrocesso da criptografia. Vamos ver como se faz.
Aqui podemos tomar vários caminhos. O mais simples é usar uma outra string, só que invertida:
**letrasInv="zyxwvutsrqponmlkjihgfedcba "**
E uma variável global que guarda se devemos avançar ou recuar. Se avanca for **TRUE** usamos a string **letras[]**; se for **FALSE**, usamos **letrasInv**; Cada vez que encontramos um espaço em branco, invertemos o sentido da criptografia. Devemos apenas tomar cuidado para achar a posição correta de **s[i]** em **letrasInv**. ([[c:p1versao10|versão 10]])
**Exemplo 1.16. criptografa() com teste de retrocesso**
#define TRUE 1
#define FALSE 0
int pos=0;
int avanca=TRUE; // variável para controlar o avanço ou recuo.
void criptografa(char s[])
{
char mat[]="199112340567";
char letras[]=" abcdefghijklmnopqrstuvwxyz";
char letrasInv[]="zyxwvutsrqponmlkjihgfedcba ";
int tamLetras=27;
int tamMat=12;
int i=0;
int maiuscula=FALSE;
while (s[i]!='\0'){
if (s[i]>='A' && s[i]<='Z'){
maiuscula=TRUE;
s[i]=s[i]-'A' + 'a';
}
if (s[i]>='a' && s[i]<='z')
if (avanca)
s[i]= letras[(s[i]-'a'+1+(mat[pos%tamMat]-'0'))%tamLetras];
else
s[i]= letrasInv[((tamLetras-1)- (s[i]-'a'+1)+(mat[pos%tamMat]-'0'))%tamLetras];
else if (s[i]==' '){
if (avanca)
s[i]=letras[mat[pos%tamMat]-'0'];
else
s[i]=letrasInv[(mat[pos%tamMat]-'0'+(tamLetras-1))%tamLetras];
avanca= !avanca;
}
if (maiuscula){
s[i]=s[i]-'a'+'A';
maiuscula=FALSE;
}
pos++;
i++;
}
}
===== Testando tudo =====
Agora testamos com um conjunto de dados simples e com os valores de MAXLINHA e MAXPRINT corretos.. Usaremos o arquivo de testes: ([[c:p1teste|teste]])
**Exemplo 1.17. Arquivo de teste**
**#aaaa #aaaa
#aaaa #aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa\\
#aaaa #aaaa #aaaa\\
#aaaa #aaaa**
que fornece o seguinte resultado ([[c:p1saida|saída]]):
****Exemplo 1.18. Arquivo de saída
**#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#x\\
awvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjb\\
bb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbbb#xawvt#jjbb\\
**
===== Melhorando nossa solução =====
Vamos melhorar nosso programa, retirando as variáveis globais. Usaremos variáveis estáticas, que, declaradas dentro de funções mantêm seu valor entre as chamadas. Também podemos eliminar alguns números mágicos e tornar nossa solução mais genérica. ([[c:p1versao11|versão 11]])
Para isso, incluimos **ctype.h**
#include
e usamos as seguintes expressões:
**Exemplo 1.19. Variáveis estáticas**
...
void imprime(char s[], int lim)
{
int j=0;
static int posicaoPrint=1; // deixou de ser global
while( s[j]!='\0')
{
printf((posicaoPrint%lim)? "%c":"%c\n",s[j++]);
posicaoPrint++;
}
}
...
void criptografa(char s[])
{
char mat[]="199112340567";
char letras[]=" abcdefghijklmnopqrstuvwxyz";
char letrasInv[]="zyxwvutsrqponmlkjihgfedcba ";
int tamMat=strlen(mat);
int tamLetras=strlen(letras);
int i=0;
int maiuscula=FALSE;
static int pos=0;
static int avanca=TRUE; // variável para controlar o avanço ou recuo.
...
}
Retornar para [[Primeira Prova - 2005-1]]