Algorytmy, C++, Matura z informatyki - nauka i materiały.

Palindromy – implementacja w C++

palindromy c++

Palindromy obecnie funkcjonują chyba jedynie jako forma zabawy słowem, ale nigdy nie wiadomo kiedy umiejętność sprawdzenia, czy wyrażenie jest palindromem za pomocą jakiegoś algorytmu, nam się przyda. Być może nigdy, a być może ułatwi nam napisanie matury z informatyki lub da nam możliwość popisania się przed znajomymi znajomością nietypowych palindromów. Kto wie 🙂

Czym są palindromy i jak je rozpoznawać?

Palindromy są to zarówno słowa, jak i całe wyrażenia, które czytając normalnie (tzn. od lewej do prawej, nie dla każdego jest to oczywiste :D)  i wspak brzmią tak samo. Często bywa tak, że wyrażenia palindromiczne pozbawione są sensu.

Przykładami palindromów są:

  • „Ala”,
  • „Kajak”,
  • „Kobyła ma mały bok”,
  • „Może jutro ta dama da tortu jeżom”,
  • „Wódy żal dla Żydów”,
  • „Wół utył i ma miły tułów”,
  • „malajalam” – to taki język 🙂 jednocześnie jest to najdłuższe słowo palindrom w języku polskim,
  • „687454786” – liczba też może być palindromem.

Można by jeszcze wymieniać i wymieniać, ale regułę już znacie. Każdy z tych przykładów czytany od tyłu brzmi tak samo jak czytany normalnie.

 

Program sprawdzający, czy słowo jest palindromem.

Poniższy program napisany w języku C++ umożliwia sprawdzenie, czy wpisane przez użytkownika słowo jest palindromem. Przyjąłem następującą taktykę:  jeśli wyraz jest palindromem to jego pierwsza litera będzie taka sama jak ostatnia, druga będzie taka sama jak przedostatnia, trzecia będzie taka sama jak trzecia od końca […] itd. dopóki nie znajdę się w połowie wyrazu. Przy czym warto zauważyć, że dla słowa o parzystej liczbie liter N wykonamy tyle samo porównań ile dla wyrazu o nieparzystej liczbie liter N+1.

Pokażę to na przykładzie liczb.

Dla liczby o parzystej liczbie cyfr 456654 porównujemy pierwszą cyfrę z ostatnią, drugą z drugą od końca i szóstkę z szóstką. Łącznie trzy porównania.

Natomiast dla liczby o nieparzystej liczbie cyfr 4569654 wykonujemy tyle samo porównań, gdyż idąc od początku i od tyłu, koniec końców wylądujemy na środkowej cyfrze, której nie ma potrzeby porównywać.

Tutaj program:

 

Myślę, że warto sobie powyższy kod przyswoić szczególnie w kontekście matury z informatyki.

  • Przemek Wiczołek

    Krótsza implementacja :
    // reverse z biblioteki algorithm
    bool palin(string word){
    string word1=word;
    reverse(word1);
    return word1==word;
    }