resolucao_primeira_prova_2005-1 [araujo]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
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**

<code c>
/*
  Enquanto não for fim de arquivo {
    Lê linha;
    Soma linha;
    Criptografa linha;
    Imprime linha criptografada;
  }
  Imprime soma;
*/
</code>

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**
<code c>
/*
  Solução
  Enquanto (há outra linha) {
    filtra tabulações e novas linhas;
    Soma linha;
    Criptografa linha;
    Imprime linha criptografada;
  }
  Imprime soma;
*/
</code>

===== 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  <sdtio.h>
#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**

<code c>
#include <stdio.h>
#include <ctype.h>
#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[]){
}
</code>

===== 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()**

<code c>
int lelinha(char s[],int lim)
{
  int c,i;
  
  for (i=0; i <lim-1 && (c=getchar())!=EOF && c!='\n';++i)
    s[i]=c;
  if (c=='\n')
   {
    s[i]=c;
    ++i;
   }
  s[i]='\0';
  return i;
}
</code>

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**

<code c>
//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<lim-1) s[i]=c;
  if (i<lim-1 && c=='\n')
   {
    s[i]=c;
    ++i;
   }
  s[i]='\0';
  return i;
}
</code>

Depois modificamos main() ([[c:p1versao3|versão 3]]) .

**Exemplo 1.7. main() modificado para detectar erro de excesso de caracteres**

<code c>
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);
}
</code>

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()**

<code c>
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++;
  }
}
</code>

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**

<code c>
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++;
  }
}
</code>

===== 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()**

<code c>
void filtraespacos(char s[])
{
   int i;
   for (i=0; s[i]!='\0'; i++)
    if (s[i]=='\n' || s[i]=='\t')
       s[i]=' ';
}
</code>

===== 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()**

<code c>
int sumchar(char s[])
{
   int i, soma=0;
   for (i=0;s[i]!='\0';i++)
     soma+=(int)s[i];
   return soma;
}
</code>

===== 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**

<code c>
char mat[]="199112340567";
int tamMat=12;
</code>

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[]**

<code c>
char letras[]=" abcdefghijklmnopqrstuvwxyz"; 
int tamLetras=27;
</code>

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()**

<code c>
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++;
  }
}
</code>

===== 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**

<code c>
#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;
}
</code>

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**

<code c>
#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++;
  }
}
</code>

===== 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**

<code c>
#include <ctype.h>
</code>

e usamos as seguintes expressões:

**Exemplo 1.19. Variáveis estáticas**

<code c>
...
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.
...
}
</code>
Retornar para [[Primeira Prova - 2005-1]]