Previous Up Next
Programação de Computadores em C

Capítulo 8  Exercícios

Este capítulo descreve a solução de diversos exercícios, que mostram como usar e decidir quando usar os diversos comandos e estruturas de dados abordados neste livro.

Os enunciados dos exercícios são obtidos da página Web http://br.spoj.pl/problems/. SPOJ (Sphere Online Judge) é um sistema disponível na Internet (na página http://br.spoj.pl/) que permite o registro de novos problemas e a submissão de soluções de problemas registrados. Há dezenas de milhares de usuários e milhares de problemas já registrados. A solução pode ser submetida em dezenas de linguagens de programação, incluindo, é claro, C.

8.1  ENCOTEL


Considere que uma representação alfanumérica de um número de telefone é uma sequência de caracteres tal que cada caractere pode ser: uma letra maiúscula (de A a Z), um hifen (-) ou um dígito 1 ou 0, sendo que letras maiúsculas representam dígitos de 2 a 9, de acordo com a tabela abaixo.

Letras Número
ABC 2
DEF 3
GHI 4
JKL 5
MNO 6
PQRS 7
TUV 8
WXYZ 9

Escreva um programa que leia várias linhas, cada linha contendo uma tal representacão alfanumérica de número de telefone, e imprima uma sequência de representações para os números de telefone, novamente uma em cada linha, que substitua letras maiúsculas por dígitos de acordo com a tabela mostrada.

Considere que cada representacão alfanumérica possui entre 1 e 30 caracteres. A entrada é terminada por fim de arquivo (EOF).

Por exemplo, para a entrada:

1-HOME-SWEET-HOME
MY-MISERABLE-JOB

A saída deve ser:

1-4663-79338-4663
69-647372253-562


A solução mostrada abaixo usa um arranjo que armazenada, para cada letra maiúscula, seu código, segundo a tabela apresentada. De fato, como em C o primeiro índice de um arranjo tem que ser 0, para cada letra maiúscula corresponde um índice entre 0 e o número de letras maiúsculas menos um.

#include <stdio.h> #include <stdlib.h> const int n = 26; // Numero de letras maiusculas char* mkCodLetras() { char i='A', codigo='2', *cod = malloc(n*sizeof(char)); int j, k; while (i<='W') { k = (i == 'P' || i == 'W') ? 4 : 3; for (j=0; j<k; j++) cod[i-'A'+j] = codigo; codigo++; i += k; } return cod; } int main() { const int max = 31; // 31 devido a terminacao com '\0' char *codLetras = mkCodLetras(), *exp = malloc(max*sizeof(char)); int numValLidos; while (1) { numValLidos = scanf("%s", exp); if (numValLidos != 1) break; int i = 0, c_A; char c; while (exp[i] != '\0') { c = exp[i]; c_A = c - 'A'; printf("%c", c_A>=0 && c_A<n? codLetras[c_A] : c); i++; } printf("\n"); } }

Essa solução evita escrever um programa, relativamente ineficiente e mais longo, que testa, após a leitura de cada caractere, se o caractere é uma letra pertencente a um grupo específico de letras na tabela mostrada, para impressão do dígito correspondente a esse grupo de letras na tabela.

8.2  PAPRIMAS


Um número primo é um número que possui somente dois divisores: ele mesmo e o número 1. Exemplos de números primos são: 1, 2, 3, 5, 17, 101 e 10007.

Neste problema você deve ler um conjunto de palavras, onde cada palavra é composta somente por letras no intervalo a-z e A-Z. Cada letra possui um valor específico, a letra a vale 1, a letra b vale 2 e assim por diante, até a letra z, que vale 26. Do mesmo modo, a letra A vale 27, a letra B vale 28 e a letra Z vale 52.

Você deve escrever um programa para determinar se uma palavra é uma palavra prima ou não. Uma palavra é uma palavra prima se a soma de suas letras é um número primo.

Entrada: Conjunto de palavras; cada palavra em uma linha, com L letras, onde 1 ≤ L ≤ 20. Término com fim de arquivo (EOF).

Saída: Para cada palavra imprimir: It is a prime word., se a soma das letras da palavra é um número primo, senão imprimir It is not a prime word.

Exemplo: Para a entrada:

UFRN
contest
AcM

a saída dever ser:

It is a prime word.
It is not a prime word.
It is not a prime word.


Uma solução completa é mostrada na Figura 8.1. A função main lê diversas palavras, até encontrar fim-de-arquvo, e imprime mensagem indicando se cada palavra lida é uma palavra prima ou não. O tamanho de cada palavra é restrito a um tamanho máximo de 20 caracteres.

A função primo verifica se um dado número n é primo ou não. Essa função pode ser implementada de diversos modos. A Figura 8.1 usa o método simples de divisões sucessivas, por todos os números menores que √n. Para valores grandes de n, esse método gasta mais tempo do que outros algoritmos existentes. Os programas mostrados a seguir usam o algoritmo conhecido como crivo de Eratóstenes. O leitor interessado pode consultar e.g.:

http://en.wikipedia.org/wiki/Prime_number#Verifying_primality
#include <stdio.h> // define scanf, printf #include <math.h> // define sqrt const int max = 21; // Um caractere a mais do que o tamanho máximo de uma palavra // porque um caractere ('\0') é usado para indicar final da cadeia de caracteres int prima (char* palavra); int ler (char* palavra); int main () { char palavra[max]; while (ler(palavra)) printf("It is%s a prime word.\n", prima(palavra) ? "" : " not"); } int minusc (char let) { return (let >= 'a' && let <= 'z'); } int valor (char let) { return (minusc(let) ? let - 'a' + 1 : let - 'A' + ('z'-'a'+1)+1); } int prima (char* palavra) { int i, somaLet=0; for (i=0; i < max && palavra[i] != '\0'; i++) somaLet += valor(palavra[i]); return primo(somaLet); } int primo (int n) { if (n%2 == 0) return 0; int k = 3, sqrtn = sqrt((double)n); // Se existir divisor próprio de n, tem que existir divisor próprio menor que raiz de n. while (k <= sqrtn) { if (n%k == 0) return 0; k += 2; } return 1; } int ler (char* palavra) { // Retorna verdadeiro sse leitura com sucesso. return (scanf("%s", &palavra) == 1);\\ }
Figura 8.1: Solução de PAPRIMAS com teste simplificado de primalidade

Uma solução que usa um teste de primalidade baseado no algoritmo conhecido como crivo de Eratóstenes é mostrada a seguir:

#include <stdio.h> // define scanf, printf #include <stdlib.h> // define malloc const int max = 21; int prima(char* palavra, int* primos, int); int ler(char* palavra); int* listaDePrimos(int); // Criada com o algoritmo "Crivo de Eratóstenes" int main () { const int m = max*(2*('z'-'a'+1)); // Primalidade deve ser testada para valores menores ou iguais a m\\ char palavra[max]; int *primos = listaDePrimos(m); while (ler(palavra)) printf("It is%s a prime word.\n", prima(palavra,primos,m) ? "" : " not"); } int minusc (char let) { … como na Figura 8.1 … } int valor (char let) { … como na Figura 8.1 … } int* listaDePrimos(int m) { int p=2, m2=m+2, nums[m2], *primos = malloc(m), // nums[0],nums[1] não usados (por simplicidade, i.e. // para que índice de nums corresponda a número entre 2 e m); i,j,k; for (i=2,j=0; i<m2; i++,j++) { nums[i]=0; primos[j] = 0; } j = 0; do { // marca múltiplos de p for (i=p; i<m2; i+=p) nums[i] = 1; // procura próximo valor não marcado a partir de j for (k=p+1; k<m2; k++) if (! nums[k]) break; p = k; // p é o próximo primo primos[j] = p; j++; } while (p<m2); return primos; } int primo (int n, int* primos, int m) { int i; for (i=0; i<m; i++) if (primos[i] >= n) return (primos[i]==n); else if (primos[i] == 0) return 0; return 0; } int ler (char* palavra) { … como na Figura 8.1 … } int prima (char* palavra, int* primos, int $m$) { int i, somaLet=0; for (i=0; i < max && palavra[i] != '\0'; i++) somaLet += valor(palavra[i]); return primo(somaLet, primos, m); }

O algoritmo do Crivo de Eratóstenes, inventado por Eratóstenes em 350 A.C., cria uma lista de todos os primos menores que um valor máximo m. Para o problema PAPRIMAS, existe tal valor máximo, que pode ser definido como vinte vezes o valor máximo possível para uma eletra (uma vez que podem ocorrer no máximo 20 letras em uma palavra). O algoritmo de Eratóstenes consiste no seguinte:

  1. Criar lista l com todos os inteiros de 2 a m.
  2. Atribuir, inicialmente, 2 a p.
  3. Repetir o seguinte, até que não exista valor não removido em l a partir de p:
  4. Retornar a lista dos números não removidos.

O programa cria um arranjo contendo todos os primos de 3 até m e, para verificar se um dado número n é primo, percorre esse arranjo usando uma pesquisa sequencial (de componente a componente), até encontrar um número primo igual ou maior a n ou até chegar ao final do arranjo.

Essa pesquisa sequencial em um arranjo ordenado é ineficiente. Um algoritmo mais eficiente, chamado de pesquisa binária, é usado a seguir.

struct ListaETamanho { int* lista; int tam; }; typedef struct ListaETamanho ListaETamanho; ListaETamanho listaDePrimos (int m) { int p = 2, m2 = m+2, nums[m2], *primos = malloc(m), i,j,k; for (i=2,j=0; i<m2; i++,j++) { nums[i]=0; primos[j] = 0; } j = 0; do { for (i=p; i<m2; i+=p) nums[i] = 1; for (k=p+1; k<m2; k++) if (! nums[k]) break; p = k; // p é o próximo primo primos[j] = p; j++; } while (p<m2); ListaETamanho l; l.lista = primos; l.tam = j; return l; } int primo (int n, ListaETamanho primos) { int linf = 0, lsup = primos.tam-1, meio = (linf+lsup)/2; while (linf<lsup-1) { if ((primos.lista)[meio] > n) { lsup = meio; meio = (linf+lsup)/2;} else if ((primos.lista)[meio] < n) { linf = meio; meio = (linf+lsup)/2;} else return 1; } return ((primos.lista)[linf]==n || (primos.lista)[lsup]==n); }

O algoritmo de pesquisa binária compara o elemento que está sendo procurado com o valor que está na metade do arranjo ordenado, permitindo assim que a busca prossiga ou na metade inferior ou na superior do arranjo, conforme o elemento a ser procurado seja menor ou maior, respectivamente, do que o valor que está na metade do arranjo. Se o elemento a ser procurado é igual ao elemento na metade, então, é claro, a busca termina com sucesso.

São mostradas apenas as funções modificadas, que são listaDePrimos e primo. A função listaDePrimos é modificada apenas para retornar, além do arranjo contendo os primos, o número de primos de fato armazenado nesse arranjo. A função primo percorre esse arranjo usando pesquisa binária.

Previous Up Next