[C++] Sprawdzenie czy słowo jest palindromem


(adriano765) #1

Mam problem z tym programem gdyż każde słowo podaje że jest palindromem.

#include 

#include 

using namespace std;


int main()

{

    bool pal=false;

    string slowo;

    short int a;

    cout << "Podaj slowo ktore sprawdzic: ";

    cin >> slowo;

    a=slowo.length();

    a--;

    for (int i=0;i<=a;i++)

    {

    if (slowo.at(i) = slowo.at(a))

    pal=true;

    else

    {

    pal = false; break;}

    }


    if (pal = true) cout << "Slowo jest palindromem";

        else cout << "Slowo nie jest palindromem";

    return 0;

}

(Sawyer47) #2

W pętli for zmienna i przybiera wartość z zakresu [0, a] i porównujesz czy litera na i-tej pozycji jest taka sama jak litera na ostatniej pozycji (a-tej). W ostatnim przebiegu pętli i równa się a, więc zawsze dostajesz wartość true. Ogólnie ten kod nie ma wiele wspólnego ze sprawdzaniem czy słowo jest palindromem.

Jeśli chcesz to zrobić poprawnie to możesz zrobić tak: mieć dwie zmienne całkowite - indeksy pierwszej i ostatniej litery. Następnie w pętli porównujesz znaki spod tych indeksów. W kolejnych krokach pętli inkrementujesz jedną zmienną i dekrementujesz drugą. Jeśli w którymkolwiek kroku znaki są różne to pętle można przerwać. Jeśli indeksy się zrównają lub wyminą (zależnie od liczby liter w słowie), iterację można przerwać - jeśli wszystkie litery odpowiadały sobie, słowo jest palindromem.

PS Staraj się dbać o czytelne formatowanie kodu.


([alex]) #3
bool pal=true;

(Yuri20) #4

Algorytm jest bezsensu, bo w każdym słowie dochodzi do momentu, w którym zmienna “i” jest równa a, a “a” jest ostatnią literą, więc nie ma szansy, żeby zmienić cokolwiek przez te else.

Napisz sobie funkcję, która przyjmuja za parametr stringa i zwraca innego stringa, w której kolejność liter jest odwrócona względem tego parametru, potem sprawdzisz czy słowo jest palindromem w mainie sprawdzając czy słowo == odwrocSlowo(slowo)

@UP:

Też dobre, jakby dało się z tego cokolwiek zrozumieć, a priorytetem jest zrozumienie jak sądzę, a nie ilośc linijek.


(adriano765) #5

Taka funkcja odwracająca słowo będzie dobra?

string odwoc (string &slowo)

{

    int a=slowo.length();

    string odwrocslowo;

    for (int i=0;i<=a;i++)

    {

        odwrocslowo.at(i)=slowo.at(a-i);

    }

    return odwrocslowo;

}

(Kubakuderski) #6
string bar = string(foo.rbegin(), foo.rend());

(adriano765) #7

Prosiłbym bardziej o wskazanie poprawności lub nie tego kodu, a nie wklejanie poleceń których nie rozumiem.


(Kubakuderski) #8

Nie, bo odwołujesz się do indeksów, których nie ma. Poza tym w cpp tablice są indeksowane od 0, a at działa inaczej (http://www.cplusplus.com/reference/string/string/at/), więc powinno to wyglądać mniej więcej tak po twojemu:

string odwroc (const string &slowo)

{

    int a=slowo.length();

    string odwrocslowo;

    odwrocslowo.resize(a);

    for (int i=0;i<=a;i++)

    {

        odwrocslowo[i] = slowo[a-i-1];

    }

    return odwrocslowo;

}

A po mojemu:

string bar = string(foo.rbegin(), foo.rend());

tworzysz stringa na podstawie “zakresu”, który zaczyna się na końcu, a kończy na początku. Poczytaj sobie o iteratorach, bardzo ułatwiają życie. http://www.cplusplus.com/reference/iterator/


(Rolek0) #9

W .at() też się indeksuje od 0.

Właściwie jedyna różnica między .at() a [] na _string_u jest taka, że .at() rzuci wyjątek jeśli podasz indeks spoza zakresu, a [] pozwoli Ci wykonać błędną operację :wink:

@OP Możesz sprawdzić bez robienia kopii.

bool palindrom = true; //na początek przyjmujesz, że napis jest palindromem

for(size_t i = 0; i < napis.size() / 2; ++i)

	if(napis[i] != napis[napis.size() - 1 - i])

	{

		palindrom = false;

		break; //jeśli już wiadomo, że nie jest palindromem to można nie sprawdzać dalej

	}

//Jeśli test nie wykaże, że nie jest, to znaczy, że jest ;)

([alex]) #10

Rolek0, za takie kody powinno dawać sądowy zakaz wykonywania zawodu.

Podałem wcześniej na iteratorach, poniżej to samo z użyciem indeksów:

bool palindrom=true;

(Rolek0) #11

Rozumiem, że piszesz o swoich słaboczytelnych (szczególnie dla początkujących) kodach :stuck_out_tongue:


([alex]) #12

Rolek0 , jeżeli tak proste kody są dla ciebie słabo czytelne to powinieneś nie odpowiadać zaś zadawać pytania na tym forum.

Natomiast jak niepotrzebnie na każdym kroku pętli wykonujesz dzielenie w pętle która powinna jedynie co zrobić to porównać dwa znaki to powinieneś zastanowić czy programowanie jest dla ciebie.


(kostek135) #13

@[alex], nie ma się co unosić. @Rolek0 ma rację (nie napisał, że dla niego, ale dla osób, które są początkujące - za takiego można uznać autora - patrz post #1). Większość kompilatorów (być może trzeba będzie ustawić odpowiednią flagą optymalizacyjną) widząc, że napis.size() / 2 nie ulega zmianie “wyciągnie go przed pętle” na poziomie asemblera.

Nie ma się co spinać, dla rozluźnienia atmosfery, może inny problem:

Załóżmy, że mamy podany ciąg (dowolny) liter niezerowej długości, ile liter należy wstawić na koniec tego ciągu, aby słowo utworzyło palindrom.

@down dokładnie o to chodziło. Mimo wszystko myślałem o “liniówce”, ale tak to zależy tylko od sposobu w jaki będziemy szukać palindromu. :slight_smile:


(Kubakuderski) #14

Szuakmy najdłuższego sufiksu, który jest palindromem i sprawdzamy ile znaków jest przed nim. Złożoność zależy od algorytmu wyszukiwania najdłuższego palindromu, ja mam kwadratowo, bo liniowo mi się nie chciało pisać…

#include 

#include 

using namespace std;


bool isPalin(const string &s)

{

	bool drome = true;

	for(int i=0, j=a.size()-1; i
	return drome;

}


unsigned int longestPalindrome(const string &s)

{

	unsigned int res = 1;

	for(int i=1; i
	return res;

}


unsigned int toBeAdded(const string &input)

{

	return input.size() - longestPalindrome(string(input.rbegin(), input.rend()));

}


int main()

{

	ios::sync_with_stdio(0);

	string input;

	while(cin >> input)

	{

		cout << toBeAdded(input) << endl;

	}


	return 0;

}