Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Anagramy

powrót

Anagram to wyraz lub zdanie powstałe po przestawieniu liter innego wyrazu (zdania). Oba wyrazy składają się z tych samych liter, tylko w innym porządku. 

Kilka przykładów:

{tex}adam{/tex} {tex}dama{/tex}

{tex}fraktal{/tex} {tex}kartafl{/tex}

Żeby sprawdzić, czy dwa słowa są anagramami policzymy wystąpienia każdej litery z pierwszego słowa, a następnie będziemy odejmować wystąpienia liter z drugiego słowa. Jeśli liczniki zostaną wyzerowane, oznaczać to będzie, że podane słowa są anagramami.

Jeśli będzie taka sytuacja, że ciągi znaków są różnej długości, to możemy od razu stwierdzić, że to nie są anagramy.

Przykład

Przeanalizujemy pierwszy przykład. Wystąpienia liter w słowie {tex}adam{/tex}:

a - 2

d - 1

m - 1

Kody ASCII powyższych liter to: 

a - 97

d - 100

m - 109

a więc wartości komórek tablicy licz[97] = 2, licz[100] = 1, licz[109] = 1 (tablica licz[127] jest zadeklarowana i wyzerowana w poniższym programie, służy do zliczania liter). 

Teraz robimy odwrotnie w stosunku do drugiego słowa. Każde wystąpienie litery dekrementujemy (zmniejszamy o 1). Jeśli w rezultacie wszystkie komórki tablicy będą równe zero, oznaczać to będzie, że wystąpienie każdej litery w jednym i drugim wyrazie jest takie samo.

Implementacja algorytmu

 

//www.algorytm.edu.pl
#include<iostream>
#include<cstring>
using namespace std;
 
bool czy_anagram(char *a, char *b)
{
  //wyznaczenie liczby liter w slowie a i w slowie b
    int dl1 = strlen(a), dl2 = strlen(b);
    //jesli dlugosci wyrazów nie sa równe, to nie moga
    //byc anagramy
  if(dl1!=dl2)return false;
 
    int licz[127]={}; //zerujemy licznniki
    for(int i=0;i<dl1;i++)
      licz[a[i]]++; //zliczamy litery pierwszego wyrazu
    for(int i=0;i<dl1;i++)
      licz[b[i]]--; //odejmowanie wystapien liter
 
    for(int i=0;i<127;i++)
      if(licz[i]!=0) //jesli ktorys licznik sie nie wyzerowal
      return false; //to oznacza, ze słowa nie sa anagramami
 
  return true; //jesli wszystkie liczniki sie wyzerowały, to mamy anagramy
} 
 
int main()
{
 
   char a[101], b[101]; //dwa słowa, maksymalnie 100 znaków
   cout<<"Podaj dwa wyrazy: ";
   cin>>a>>b;
 
   if(czy_anagram(a,b))
     cout<<"Podane wyrazy sa anagramami\n";
   else
     cout<<"Podane wyrazy nie są anagramami\n";
 
    cin.ignore();
    cin.get();
    return 0;
}