Utilizando a linguagem
, escreva um programa que primeiro solicita ao usuário um conjunto de palavras e, em seguida, identifica e agrupa aquelas que são anagramas entre si. Anagramas são palavras formadas pelo rearranjo das letras de outra palavra, usando todas as letras originais exatamente uma vez (ex: “amor” e “roma”).
O programa deverá ter uma função com o protótipo:
ˋint sao_anagramas(char str1[], char str2[]);ˋ
Em seguida, escreva a função ˋmain()ˋ que:
- Assuma que o usuário irá inserir as palavras em letras minúsculas.
- Declare uma matriz de strings (ex: ˋchar palavras[20][100]; ') para armazenar as palavras.
- Implemente uma lógica para percorrer a matriz e comparar cada palavra com todas as outras palavras subsequentes.
- Primeiro, pergunte ao usuário quantas palavras ele deseja inserir (ex: limite de 20 palavras).
- Quando um grupo de anagramas for encontrado, o programa deve imprimi-lo.
- Recomenda-se o uso da função ˋ getsˋ para ler as palavras, pois ela lida bem com espaços e evita estouro de buffer. Lembre-se de remover o caractere ˋ \nˋ que o ˋ fgetsˋ adiciona ao final da string.
- Use um laço para solicitar que o usuário digite cada uma das palavras e armazene-as na matriz.
- Utilize a função ˋsao_anagramasˋ para verificar os pares.
Por exemplo, uma execução do programa pode ser assim:
⋯
Quantas palavras você deseja inserir? 6
Digite a palavra 1: amor
Digite a palavra 2: silent
Digite a palavra 3: ator
Digite a palavra 4: listen
Digite a palavra 5: roma
Digite a palavra 6: tora
Anagramas encontrados:
(amor, roma)
(silent, listen)
(ator, tora)
…
ˋint sao_anagramas(char str1[], char str2[]);ˋ
⋯
Digite a palavra 1: amor
Digite a palavra 2: silent
Digite a palavra 3: ator
Digite a palavra 4: listen
Digite a palavra 5: roma
Digite a palavra 6: tora
(amor, roma)
(silent, listen)
(ator, tora)
…
Passo 1
O que o problema pede e quais informações foram dadas:
- O programa deve ser escrito em linguagem C.
- Deve existir uma função com o protótipo:
- O programa principal (
main) deve:- Perguntar ao usuário quantas palavras ele quer inserir (máximo sugerido: 20).
- Ler cada palavra (assumir letras minúsculas).
- Armazenar as palavras em uma matriz de strings, por exemplo
char palavras[20][100];. - Comparar cada palavra com as subsequentes usando a função
sao_anagramas. - Ao encontrar um grupo de anagramas (duas ou mais palavras que formem um grupo), imprimir esse grupo.
- O enunciado recomenda usar
gets, mas também lembra de remover o ‘\ n’ quefgetsadiciona; por razões de segurança iremos usarfgetse remover o ‘\ n’. - O usuário inserirá palavras em letras minúsculas (isso facilita a implementação).
- Exemplo de saída desejada:
- Para entrada:
amor, silent, ator, listen, roma, torao programa deve imprimir os grupos(amor, roma),(silent, listen)e(ator, tora).
- Para entrada:
Passo 2
Como verificar se duas palavras são anagramas — explicação didática do método que vamos usar:
- Ideia principal: duas palavras são anagramas se elas têm exatamente as mesmas letras, cada letra com a mesma multiplicidade (ex: duas vezes ‘a’, uma vez ‘b’, …), e nenhum outro caractere extra.
- Método prático e eficiente em C (sem precisar ordenar strings):
- Criar um vetor de contagem de tamanho 26, um para cada letra do alfabeto:
int count[26] = {0};. - Percorrer a primeira string: para cada caractere entre ‘a’ e ‘z’, incrementar
count[c - 'a'], e contar quantas letras válidas existem nessa string (vamos chamar detotal1). - Percorrer a segunda string: para cada caractere entre ‘a’ e ‘z’, decrementar
count[c - 'a'], e contartotal2. - Se
total1 != total2, então as palavras têm números diferentes de letras válidas e não são anagramas. - Se algum elemento de
countfor diferente de zero, então as multiplicidades diferem e as palavras não são anagramas. - Caso contrário, são anagramas.
- Criar um vetor de contagem de tamanho 26, um para cada letra do alfabeto:
- Por que isso funciona? Porque a primeira string “adiciona” ao vetor de contagem e a segunda “retira”. Se ambas tiverem exatamente as mesmas letras nas mesmas quantidades, o vetor de contagem volta a zeros.
- Complexidade: cada verificação percorre as duas strings uma vez, então é linear no tamanho das strings, o que é eficiente para palavras curtas.
- Observações sobre caracteres: assumimos letras minúsculas e ignoramos qualquer caractere fora de ‘a’…‘z’ (caso apareça, será simplesmente ignorado). Se quiser considerar outros caracteres, o método pode ser adaptado.
Passo 3
Como ler as palavras do usuário com segurança e armazená-las:
- Em C, strings são vetores de caracteres terminados por ‘\0’. Para ler com segurança, usaremos
fgets(buffer, tamanho, stdin);que lê atétamanho-1caracteres e adiciona ‘\0’. O problema é quefgetsinclui o ‘\ n’ se houver espaço; então precisamos removê-lo. - Procedimento para cada palavra:
- Chamar
fgets(palavras[i], 100, stdin);(supondo que cada palavra caiba em 100). - Verificar o comprimento com
strlene, se o último caractere for ‘\ n’, substituí-lo por ‘\ 0’ para remover a quebra de linha.
- Chamar
- Depois de ler todas as palavras, vamos comparar cada palavra com as subsequentes. Para formar grupos (não só pares), faremos:
- Ter um vetor
int usado[20] = {0};para marcar palavras já colocadas em algum grupo. - Para cada índice
inão marcado, verificar todos osj > inão marcados; sesao_anagramas(palavras[i], palavras[j])for verdadeiro, acumularjno grupo e marcarj. - Se encontrar pelo menos um
jpara oi, imprimir o grupo incluindoie osjs e marcaritambém.
- Ter um vetor
- Assim imprimimos cada grupo de anagramas apenas uma vez, e grupos com mais de duas palavras aparecem completos (ex:
(amor, roma, mora)). - Exemplo de interação (fluxo de leitura):
- Perguntar número
ncomscanf("%d", &n);(validar 1 <=n<= 20). - Consumir o ‘\ n’ restante com
getchar();antes de usarfgetsno loop de leitura das palavras. - Ler cada palavra com
fgetse remover o ‘\ n’.
- Perguntar número
Passo 4
Implementação da função
sao_anagramas (explicando linha a linha):- Protótipo requerido:
- Implementação (lógica explicada anteriormente):
- Inicializa
count[26]a zeros. - Percorre
str1, para cada letra de ‘a’ a ‘z’ fazcount[c - 'a']++e incrementatotal1. - Percorre
str2, para cada letra de ‘a’ a ‘z’ fazcount[c - 'a']--e incrementatotal2. - Se
total1 != total2retorna 0. - Verifica se todos os
count[k]são zero; se algum não for, retorna 0. - Caso contrário, retorna 1 (são anagramas).
- Inicializa
- Esse método não usa funções pesadas e é fácil de escrever numa prova.
Passo 5
Explicação do restante do programa (main) passo a passo:
- Includes necessários:
stdio.h(entrada/saída),string.h(strlen),stdlib.h(opcional). - Declaração da matriz de palavras:
char palavras[20][100];— 20 palavras, cada uma com espaço para até 99 caracteres mais ‘\ 0’. - Lemos o número de palavras
ne limitamos a 20 se o usuário pedir mais. - Limpamos o buffer de entrada com
getchar()apósscanfpara evitar que a primeirafgetsleia o restante da linha. - Leitura das palavras com
fgetse remoção do ‘\ n’. - Comparações e impressão dos grupos conforme descrito no Passo 3.
- O formato de impressão será
(palavra1, palavra2, ...)para cada grupo. - Ao final, o programa termina retornando 0.
Passo 6
Código completo e testado (coloque este código como resposta final do problema)
- O código abaixo implementa tudo que expliquei: a função
sao_anagramascom contagens de letras, leitura segura comfgets, agrupamento e impressão dos grupos de anagramas.
Resposta
#include <stdio.h>
#include <string.h>
/* Protótipo exigido */
int sao_anagramas(char str1[], char str2[]);
/* Implementação da função que verifica anagramas */
int sao_anagramas(char str1[], char str2[]) {
int count[26] = {0};
int i;
int total1 = 0, total2 = 0;
/* Conta letras em str1 */
for (i = 0; str1[i] != '\0'; i++) {
char c = str1[i];
if (c >= 'a' && c <= 'z') {
count[c - 'a']++;
total1++;
}
}
/* Subtrai letras de str2 */
for (i = 0; str2[i] != '\0'; i++) {
char c = str2[i];
if (c >= 'a' && c <= 'z') {
count[c - 'a']--;
total2++;
}
}
/* Se o número total de letras difere, não são anagramas */
if (total1 != total2) return 0;
/* Se algum contador não for zero, as multiplicidades diferem */
for (i = 0; i < 26; i++) {
if (count[i] != 0) return 0;
}
return 1; /* São anagramas */
}
int main(void) {
char palavras[20][100];
int usado[20] = {0};
int n, i, j;
printf("Quantas palavras você deseja inserir? ");
if (scanf("%d", &n) != 1) return 1;
if (n < 1) return 0;
if (n > 20) n = 20; /* limita a 20 palavras como sugerido */
/* Consumir o '\n' remanescente depois de scanf */
getchar();
/* Leitura das palavras com fgets e remoção do '\n' final */
for (i = 0; i < n; i++) {
printf("Digite a palavra %d: ", i + 1);
if (fgets(palavras[i], sizeof(palavras[i]), stdin) == NULL) {
palavras[i][0] = '\0';
} else {
size_t len = strlen(palavras[i]);
if (len > 0 && palavras[i][len - 1] == '\n') {
palavras[i][len - 1] = '\0';
}
}
}
printf("---\nAnagramas encontrados:\n");
/* Para cada palavra, procurar anagramas entre as subsequentes.
Quando encontrar pelo menos um, imprimir o grupo completo. */
for (i = 0; i < n; i++) {
if (usado[i]) continue;
int encontrou = 0;
for (j = i + 1; j < n; j++) {
if (!usado[j] && sao_anagramas(palavras[i], palavras[j])) {
if (!encontrou) {
/* imprime o primeiro elemento do grupo */
printf("(%s", palavras[i]);
encontrou = 1;
}
/* imprime os demais elementos do grupo */
printf(", %s", palavras[j]);
usado[j] = 1; /* marca como já agrupado */
}
}
if (encontrou) {
printf(")\n");
usado[i] = 1; /* marca também o elemento inicial do grupo */
}
}
return 0;
}