Palindromy

Kategoria: Zadania z programowania

Palindrom jest to pojedynczy wyraz (lub całe zdanie), który czytany od tył i od przodu brzmi tak samo. Palindromy w C++ są jednym z podstawowych zagadnień jakie należy poznać, przygotowując się do matury z informatyki. Wystąpiły one dotychczas na wielu wielu maturach, a zadania związane z palindromami są bardzo podobne.

Palindromy informacje

Przykładem palindromu jest wyraz kajak. Czytany od tył i od przodu brzmi tak samo. Aby sprawdzić czy dany wyraz jest palindromem, wystarczy go odwrócić i sprawdzić czy jest taki sam jak przed odwróceniem. Jest to najszybsza i najwydajniejsza metoda.

Palindromy algorytm

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

  1. Początek algorytmu
  2. Wczytaj wyraz do zmiennej słowo
  3. Odwróć zmienną słowo i zapisz wynik do zmiennej tymczasowa
  4. Jeżeli słowo=tymczasowa to wyraz jest palindromem
  5. W przeciwnym wypadku nie jest palindromem
  6. Koniec algorytmu

Palindromy program C++

Funkcja do sprawdzania czy wyraz jest palindromem jest bardzo prosta. Najtrudniejszą kwestią jest odwrócenie zmiennej string. Istnieje na to kilka sposobów. Najbardziej podstawowa metoda to użycie pętli, która będzie przepisywała zmienną do innej zmiennej, literka po literce, zaczynając od tył:

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

using namespace std;

bool palindrom(string wyraz)
{
    string odwrocony;   // tutaj zapiszemy wyraz odwrotnie
    int dlugosc = wyraz.length(); // dlugosc wyrazu

    // odwracamy wyraz
    for(int i = 0; i < dlugosc; i++)
    {
        odwrocony += wyraz[dlugosc - i - 1];
    }

    // zwracamy true lub false
    return wyraz == odwrocony;
}

int main()
{
    string wyraz;

    cout << "Podaj wyraz do sprawdzenia:" << endl;
    cin >> wyraz;

    if (palindrom(wyraz) == true)
    {
        cout << "Wyraz jest palindromem" << endl;
    }
    else
    {
        cout << "Wyraz NIE jest palindromem" << endl;
    }

    system("PAUSE");
    return 0;
}

Po wywołaniu funkcji palindrom zwraca ona true lub false.

Palindromy w C

Palindromy bardzo łatwo sprawdź w języku C. Istnieje w nim funkcja strrev() odwracająca wyraz. Dzięki temu nie trzeba bawić się z pętlą i liczeniem miejsc. Weź pod uwagę fakt, że na maturze deklarując język C++, możesz korzystać z funkcji języka C. Wystarczy zaimportować odpowiednie biblioteki. Niestety działają one tylko na zmiennych char, wymagana byłaby konwersja ze string:

#include <stdio.h>
#include <stdlib.h>

int palindrom(char* wyraz)
{
    char odwrocony[255];

    //kopiujemy wyraz do zmiennej pomocniczej
    strcpy(odwrocony, wyraz);

    //odwracamy wyraz
    strrev(odwrocony);

    //jezeli wyrazy sie zgadzaja zwroc 1
    if (strcmp(wyraz, odwrocony) == 0)
    {
        return 1;
    }

    return 0;
}

int main()
{
    char wyraz[255];

    printf("Podaj wyraz do sprawdzenia:\n");
    scanf("%s", wyraz);

    printf("%d\n", palindrom(wyraz));

    system("PAUSE");
    return 0;
}

Komentarze

Bielski

Ostatnio otrzymałem zadanie na sprawdzianie i nie wiedziałem kompletnie jak do tego się zabrać? Prosiłbym o pomoc.
Program miał wyszukać w zdaniu wprowadzonym z klawiatury wszystkie palindromy,wypisać je oraz zsumować ich ilość.

Karol

Sposób wygląda fajnie. Dostałem już tyle różnych rozwiązań palindromów, że chyba umieszczę je na tej stronie. Twoje rozwiązanie wydaje się najkrótsze, mimo że mało logiczne na pierwszy rzut oka, to łatwe do zapamiętania.

muttley

return (wyraz == string(wyraz.rbegin(), wyraz.rend()));
W sumie dużo łatwiejsza metoda na sprawdzenie czy wyraz jest palindromem.

Spoko stronka, przynajmniej wiem co muszę sobie przypomnieć przed maturą (jak kodzę coś to raczej mam gotową klasę do czytania plików :))

Karol

Zależy od umiejętności, często słyszę od ludzi że czasu na maturze z informatyki jest za mało. Ja wyrobiłem się na styk 🙂

Przykład trochę poprawiłem, teraz jest wydajny czasowo.

Lukas

Od kiedy na maturze brakuje czasu ? 😮

Przykład może i działa, ale bardzo niewydajny i zdaje mi się czy zadziała tylko dla 3 znakowych wyrazów? i+dl-1 wychodzi przy drugim obiegu poza zakres stringa.

Karol

Przykład działa bardzo dobrze, zawsze rozwiązuję palindromy w ten sposób. Masz rację że nie jest to wydajna pamięciowo metoda, jednak na maturze nie warto zwracać na to uwagi. Na wszystkie zadania i tak brakuje czasu.

cdev

Według mnie przykład nie zadziała. W dodatku pisze po pamięci jak leci.

Dodaj komentarz

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