[Resolvido] Anagrama

[askazy]

Escreve um programa que leia duas palavras e verifique se a segunda é um anagrama da primeira. Exemplos: ROMA, MORA, ORAM, AMOR, RAMO são anagramas entre si.

Minha idéia é:

1)Armazenar a primeira palavra em um vetor e a segunda em outra (2 vetores)

2) Descobrir o tamanho das 2 palavras

3) Fazer um for para cada uma das palavras e verificar quantas vezes cada letra aparece. (Aqui está o problema, como eu faço para contar quantas letras a,b,c,etc aparecem?)

4) Armazenar a quantidade de vezes que cada letra aparece em outros 2 vetores.

5) Comparar a quantidade de vezes que cada letra aparece entre os dois vetores.

Alguém pode me dar uma ajuda nos passos 3 e 5?

ps: Só pode usar a biblioteca <stdio.h>

[eatg75]

Se tiveres acesso a este livro http://books.google.pt/books/about/Matem%C3%A1tica_Discreta_Cole%C3%A7%C3%A3o_Schaum.html?id=2S9bwDmD1P0C&redir_esc=y no capitulo 6 (Contagem) e abordada a teoria de contagem com ou sem repeticoes o que auxiliara a resolver esse problema, tinha que fazer algo semelhante na disciplina de Programacao Avancada e segui essa abordagem e no final tive de calcular todos os anagramas de uma palavra com 8 caracteres e guarda-las numa lista e no fim o meu programa utilizava 2GB de memoria, apesar disso gostei muito dessa abordagem pois recori a matematica para resolve-lo e aprendi bastante.

Depois numa conversa com um colega ele me disse que o professor tinha dito nas aulas que a solucao era simplesmente ordenar as duas strings lexicograficamente e depois compara-las utilizando a funcao strcmp().

[HappyHippyHippo]

https://www.portugal-a-programar.pt/topic/65551-duvida-topas-treinos-2009-anagramas/page__hl__%2Bclint+%2Beastwood

[askazy]

http://www.portugal-a-programar.pt/topic/65551-duvida-topas-treinos-2009-anagramas/page__hl__%2Bclint+%2Beastwood

Nao consegui entender nada, é muito complexo da maneira que eles escreveram e não aprendi a maioria dos recursos que eles usaram.

[HappyHippyHippo]

Nao consegui entender nada, é muito complexo da maneira que eles escreveram e não aprendi a maioria dos recursos que eles usaram.

o mesmo que isto :

Depois numa conversa com um colega ele me disse que o professor tinha dito nas aulas que a solucao era simplesmente ordenar as duas strings lexicograficamente e depois compara-las utilizando a funcao strcmp().

[askazy]

Se eu desenvolver de acordo com aqueles passos que descrevi não é possível chegar em uma solução?

[HappyHippyHippo]

sim é

[askazy]

Estou travado no passo 3, HELP.

[HappyHippyHippo]

amostra o código que tens

[askazy]

O que tenho parcialmente:

#include <stdio.h>
int main()
{
int cont = 0, cont2 = 0; /*cont e cont2, número de letras das palavras 1 e 2*/
char p1[30], p2[30]; /* p1 = palavra1 e p2 = palavra2*/
scanf("%s %s", p1, p2);
for (cont = 0; p1[cont] != '\0'; cont++); /*descobre o número de letras da primeira palavra*/
cont2 = cont;	 /* como as duas são anagramas, ambas tem que ter o mesmo número de letras*/
 /* o problema agora é como eu descubro o número de vezes que cada letra aparece para eu poder comparar*/

return 0;
}

Edited March 31, 2014 by askazy

[HappyHippyHippo]

necessitas de uma lista com o número de ocorrências de cada uma

[askazy]

Na verdade eu tenho que fazer um vetor de tamanho 256 para contar todos os caracteres ne?

Edited March 31, 2014 by askazy

[askazy]

Acho que funciona:

/*A parte mais difícil de perceber era como eu iria contar a ocorrência de cada letra, mas supondo que eu li
a palavra amor, o vetor p1 seria p1[0]=a,p1[1]=m,p1[2]=o,p1[3]=r, assim se eu fizesse cont[p1[1]] por exemplo,
eu iria saber que a letra 'a' ocorreu uma vez, pois eu teria cont[a]++, e assim sucessivamente.*/

#include <stdio.h>
int main()
{
int cont[256], cont2[256], i, flag = 0; /*cont e cont2 servem para ver o numero de vezes que cada letra aparece*/
char p1[30], p2[30];					/* palavra 1 e palavra 2*/
scanf("%s %s", p1, p2);
for (i = 0; i < 256; i++)	 /*zera o vetor que conta as letras da primeira palavra*/
	cont[i] = 0;
for (i = 0; i < 256; i++)	 /*zera o vetor que conta as letras da segunda palavra*/
	cont2[i] = 0;
for (i = 0; p1[i] != '\0'; i++) {	   /*percorre a primeira palavra*/
	cont[p1[i]]++;					   /*conta quantas vezes cada letra da palavra aparece*/
}
for (i = 0; p2[i] != '\0'; i++) {		 /*percorre a segunda palavra*/
	cont[p2[i]]++;						/* conta quantas vezes cada letra da palavra aparece*/
}
for (i = 0; i < 256; i++) {				  /*percorre o vetor que conta letras*/
	if (cont[i] != cont2[i])	 /* se o numero de vezes que uma letra ocorre na palavra 1 eh diferente da palavra 2 flag recebe1*/
		flag = 1;				/* significa que não são anagramas*/
}
if (flag == 0)
	printf("As palavras %s e %s sao anagramas\n", p1, p2);
else
	printf("As palavras %s e %s nao sao anagramas\n", p1, p2);

return 0;
}

Edited March 31, 2014 by askazy

[HappyHippyHippo]

nop .... tem um pequeno erro de distracção ..

[askazy]

erro de que não entendi?

[HappyHippyHippo]

erro de que não entendi?

é assim

a ideia do código está correcta, em teoria daria tudo ok, mas não dá ... a razão foi pura distracção da tua parte

olha bem e verás onde está errado ...

testaste o código ? quantas vezes é que dá a resposta anagrama para palavras que realmente são anagramas ?

[askazy]

Ah é a flag que ta errada ne?

[HappyHippyHippo]

nao

[askazy]

creio ser isso;

for (i = 0; p2[i] != '\0'; i++) {			    /*percorre a segunda palavra*/
		    cont2[p2[i]]++;										  /* conta quantas vezes cada letra da palavra aparece*/
    }

[HappyHippyHippo]

yep ... era isso