Anagramy

Kategoria: Zadania z programowania

Anagram jest to wyraz (lub całe zdanie) powstały w wyniku przestawiania liter innego wyrazu, wykorzystując wszystkie jego litery. Pojęcie anagramu jest podstawowym pojęciem jakie należy sobie przyswoić, przed przystąpieniem do matury z informatyki. Zadania związane z anagramami trafiają się bardzo często i wszystkie są do siebie podobne.

Anagramy informacje

Aby sprawdzić czy dany wyraz jest anagramem drugiego, należy sprawdzić czy ich długość jest taka sama. Następnie posortować obydwie zmienne za pomocą sortowania bąbelkowego. Jeżeli posortowane zmienne są takie same i mają taką samą długość, oznacza to że są anagramami.

Dla przykładu:

  • anagramem wyrazu karol jest wyraz rolka
  • anagramem wyrazu matura jest wyraz trauma.

Anagramy algorytm

Prosty algorytm w postaci listy kroków, sprawdzający czy wyraz jest anagramem drugiego:

  1. Początek algorytmu
  2. Wczytaj pierwsze słowo do zmiennej słowo1
  3. Wczytaj drugie słowo do zmiennej słowo2
  4. Jeżeli długości zmiennych słowo1 i słowo2 są różne, to wyrazy nie są anagramami
  5. Posortuj bąbelkowo zmienną słowo1 i zapisz do zmiennej słowo1
  6. Posortuj bąbelkowo zmienną słowo2 i zapisz do zmiennej słowo2
  7. Jeżeli słowo1=słowo2 to wyrazy są anagramami
  8. W przeciwnym wypadku nie są anagramami
  9. Koniec algorytmu

Kod programu w C++

Kod jest dość długi, jednak jest bardzo prosty. Funkcja sprawdzająca czy wyrazy są anagramami tak naprawdę tylko sprawdza długość wyrazów oraz sortuje je bąblekowo.

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

bool anagram(string wyraz1, string wyraz2)
{
    if (wyraz1.length() != wyraz2.length())
    {
        return false;   // dlugosc sie nie zgadza
    }

    // sortujemy babelkowo obydwa stringi
    // mozna za jednym razem, bo ich dlugosc jest taka sama
    for (int i = 0; i < wyraz1.length() - 1; i++)
    {
        for (int j = 0; j < wyraz2.length() - 1; j++)
        {
            if (wyraz1[j] > wyraz1[j+1])
                swap(wyraz1[j], wyraz1[j+1]);

            if (wyraz2[j] > wyraz2[j+1])
                swap(wyraz2[j], wyraz2[j+1]);
        }
    }

    return wyraz1 == wyraz2; //zwracamy true lub false
}

int main()
{
    string wyraz1, wyraz2;

    cout << "Podaj wyraz pierwszy" << endl;
    cin >> wyraz1;

    cout << "Podaj wyraz drugi" << endl;
    cin >> wyraz2;

    if (anagram(wyraz1, wyraz2))
    {
        cout << "Wyraz jest anagramem!" << endl;
    }
    else
    {
         cout << "Wyraz NIE jest anagramem!" << endl;
    }

    system("PAUSE >NUL");
    return 0;
}

Komentarze

Wuja

@mmtt
użycie tutaj sortowania bąbelkowego jest uzasadnione tym , że na pierwszej części matury z informatyki w zadaniach zabronione jest korzystanie z bibliotek.

mmtt

1) Jeśli jest taka możliwość zawsze warto korzystać z funkcji bibliotecznych zamiast pisania własnych odpowiedników. W tym przypadku pisanie sortowania bąbelkowego jest absurdalne, da się to zrobić w jednej linijce funkcją sort w duże lepszej złożoności.

2) Proponuję policzyć wystąpienia konkretnych liter i je porównać. Jest to rozwiązanie o optymalnej złożoności czasowej O(n) (rozwiązanie z artykułu O(n^2), sortowanie z biblioteki O(nlogn))

Alicja

Moja wersja 🙂

#include >algorithm< #include >iostream< using namespace std; bool anagram(string tekst1,string tekst2) { if(tekst1.size()!=tekst2.size()) return 0; sort(tekst1.begin(),tekst1.end()); sort(tekst2.begin(),tekst2.end()); if(tekst1==tekst2) return 1; return 0; } int main() { string napis1,napis2; cin>>napis1>>napis2; cout<<anagram(napis1,napis2); return 0; }

anonim

łatwiej po prostu sort()

Michał

Dziękuję za szybką odpowiedź. Szukając odpowiedzi na to pytanie natrafiłem jedynie na standardową listę kroków, gdzie używa się wyrażeń typowych dla programowania jak jeżeli, dopóki i zwrotów ze strzałkami. Więc niestety nadal nie wiem czy to co Ty podałeś jest poprawne. Chyba, niestety, zostało mi ogarnięcie tego standardowego typu.

Tak w ogóle to własnie zaczynam się uczyć do matury z informatyki :D. Jest ona dopiero 19 maja, więc może dam radę choćby na te 50%.

Karol

Nie zrozumiałeś mojej wypowiedzi. Gdyby to co podałem było błędne, to bym tego nie umieścił na stronie.

Szczegółowość listy kroków zależy od operacji jaką masz przedstawić. Jeżeli każą Ci napisać listę kroków dla sortowania liczb, to wiadomo że nie wystarczy napisać „1. Sortuję liczby”. Nigdzie nie znajdziesz odpowiedzi na pytanie, którego szukasz. Wynika to z faktu, że każde zadanie jest inne, nie każde da się przedstawić listą kroków, NIGDY nie wiesz co pisze w kluczu odpowiedzi.

Lista kroków nie jest językiem formalnym. Nie ma określonych zasad, składni ani semantyki. W odniesieniu do matury, dużo zależy od egzaminatora, który będzie oceniał Twoją pracę.

Lista kroków w tym artykule jest poglądowa.

Michał

Nie za bardzo na temat, ale czy lista kroków jaką tu przedstawiłeś jest poprawna i zostałaby zaliczona w zadaniu, w którym należy napisać listę kroków? Szczególnie chodzi mi o „posortuj bąbelkowo”.

Karol

Prawdopodobnie zostałoby to uznane, a żeby wiedzieć na pewno wystarczy zajrzeć do klucza odpowiedzi – tam przeważnie są opisane wszelkie wyjątki i to za co obcinać punkty. Wiadomo – trzeba się wbić w klucz. Lista kroków sama w sobie jest poprawna. Nie wyobrażam sobie aby konieczne było tutaj zagnieżdżanie kroków odpowiedzialnych za sortowanie. To nie na tym polegał problem aby udowodnić, że umiemy sortować, a na tym aby pokazać że rozumiemy anagramy.

Generalnie lista kroków umieszczona przeze mnie nie tyczy się żądnego konkretnego zadania. Wymyśliłem ją po prostu na potrzeby artykułu, aby pokazać jak sprawdzić czy x jest anagramem. Wszelkie wyjątki w kwestii listy kroków powinien zawierać klucz odpowiedzi, ewentualnie szczegóły powinien dostarczyć nauczyciel, który kazał nauczyć się anagramów (można go spytać czy zaakceptuje taką formę).

W artykule „Jak przygotować się do matury z informatyki” został W KOMENTARZACH poruszony taki sam problem o jakim wspomniałeś. Poszukaj.

Robert

Ciekawa stronka i bardzo użyteczna w przygotowaniach do matury. Polecę ją swoim znajomym. Pozdro.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *