[C++] Palindrom / Oglindit

[Andreigl]

Un palindrom sau un număr oglindit este acel număr care dacă este citit atât din dreapta, cât și din stânga, obținem același număr.

Exemplu: 1, 2, 3, ..., 9, 11, 22, 33, ..., 99, 111, 222, ..., 999, 121, 131, ..., 191 etc.

 

Avem următorul algoritm pentru a verifica dacă un număr este palindrom:

bool Palindrom(int Numar)
{
    int Oglindit, aux;
    Oglindit = 0, aux = Numar;

    while (Numar != 0)
    {
        Oglindit = Oglindit * 10 + Numar % 10;
        Numar /= 10;
    }

    if (aux == Oglindit)
        return true;
    else
        return false;
}

 

Să luăm ca exemplu numărul 515, vom încerca să folosim același algoritm ca și mai sus, doar că prin „vorbe”.

Avem variabila Oglindit = 0 și copiem numărul 515 într-o nouă variabilă numită aux.

Vom împărți numărul la 10 până acesta devine 0. În cazul de față, 515 se poate împărți de 3 ori la 10 (515/10 = 51, 51/10 = 5, 5/10 = 0).

De ce facem asta? Pentru a crea oglinditul unui număr, trebuie să luăm fiecare cifră din numărul inițial, cifrele din „spatele” numărului.

Pentru a lua ultima cifră a unui număr, se află restul împărțirii cu 10, exemplu: 513 % 10 va returna 3.

 

Pasul 1:

Avem Numar = 515, Oglindit = 0.

Oglindit = Oglindit * 10 + Numar % 10 = 0 * 10 + 515 % 10 = 0 + 5 = 5

Numar = Numar / 10 = 515 / 10 = 51

 

Pasul 2:

Avem Numar = 51, Oglindit = 5

Oglindit = Oglindit * 10 + Numar % 10 = 5 * 10 + 1 = 51

Numar = Numar / 10 = 51 / 10 = 5

 

Pasul 3:

Avem Numar = 5, Oglindit = 51

Oglindit = Oglindit * 10 + Numar % 10 = 51 * 10 + 5 = 515

Numar = Numar / 10 = 5 / 10 = 0 (bine, dă cu virgulă, dar noi avem o variabilă de tip întreg)

 

Funcția de mai sus poate fi apelată în felul următor:

if (Palindrom(Numar))
    std::cout << "Este palindrom!";
else
    std::cout << "Nu este palindrom!";

 

O altă variantă de algoritm ce poate verifica atât un număr dacă este palindrom, cât și un cuvânt, este următoarea:

bool Palindrom(std::string Cuvant)
{
    std::string Palindrom_Check;

    for (int contor = Cuvant.length() - 1; contor >= 0; contor--)
    {
        Cuvant[contor] = std::tolower(Cuvant[contor]);
        Palindrom_Check += Cuvant[contor];
    }

    if (!strcmp(Cuvant.c_str(), Palindrom_Check.c_str()))
        return true;
    else
        return false;
}

De menționat este că toate literele sunt transformate în litere mici pentru a putea verifica corect dacă este sau nu palindrom.  Pentru asta am folosit funcția „tolower” din librăria <cctype>.

De exemplu: Apa devine apa.

 

O problemă simplă (link: https://www.pbinfo.ro/probleme/88/palindrom)

Într-un fișier pe prima linie se află un număr N, iar în funcție de acel număr, se află alte N linii. Să se verifice dacă cuvântul / numărul de pe linia cutare este palindrom, sau nu. Programul va afișa într-un fișier un mesaj corespunzător pentru fiecare linie citită (1 sau 0, true or false).

 

Varianta mea de rezolvare pentru 100 de puncte este următoarea:

#include <fstream>
#include <cctype>
#include <string.h>

bool Palindrom(std::string myString)
{
    std::string Palindrom_Check;

    for (int contor = myString.length() - 1; contor >= 0; contor--)
    {
        myString[contor] = std::tolower(myString[contor]);
        Palindrom_Check += myString[contor];
    }

    if (!strcmp(myString.c_str(), Palindrom_Check.c_str()))
        return true;
    else
        return false;
}

int main()
{
    std::ifstream file_In("palindrom.in");
    std::ofstream file_Out("palindrom.out");

    int N;
    file_In >> N;

    std::string read_File;
    for (int contor = 0; contor < N; contor++)
    {
        file_In >> read_File;
        
        if (Palindrom(read_File))
            file_Out << 1 << "\n";
        else
            file_Out << 0 << "\n";
    }

    return 0;
}

 

 

Edited January 25, 2020 by shanker'

[MAMRETRAS]

O alta varianta mai eficienta ar fi:

#include <algorithm>
#include <iostream>
#include <string>

bool is_palindrome(std::string input) {
    std::string reversed_input = input;
    std::reverse(reversed_input.begin(), reversed_input.end());
    
    return reversed_input == input;
}

int main() {
    std::string input; std::cin >> input;
    
    if (is_palindrome(input)) {
        std::cout << "E palindrom!\n";
    }
    else {
        std::cout << "Nu e palindrom!\n";
    }
    
    return 0;
}

 

[Andreigl]

@Vesca,

 

Funcția reverse „face” același lucru ce am făcut și eu, adică funcționează sub același mod, altfel nu-mi explic cum ai putea inversa un cuvânt  

Deci varianta ta e mai scurtă doar, totuși ai uitat un lucru. Trebuie ca string-ul să fie lowercase în întregime pentru a putea verifica dacă este palindrom (așa este și în problema de mai sus de pe PbInfo).

 

Varianta 1, exact cum am făcut eu mai sus, sau ...

 

Varianta 2 cu o funcție internă:

std::transform(input.begin(), input.end(), input.begin(),
		[](char myChar) { return std::tolower(myChar); });

 

Deci codul final ar fi:

#include <algorithm>
#include <iostream>
#include <string>
#include <cctype>

bool is_palindrome(std::string input) {
	std::transform(input.begin(), input.end(), input.begin(),
		[](char myChar) { return std::tolower(myChar); });

	std::string reversed_input = input;
	std::reverse(reversed_input.begin(), reversed_input.end());

	return reversed_input == input;
}

int main() {
	std::string input; std::cin >> input;

	if (is_palindrome(input)) {
		std::cout << "E palindrom!\n";
	}
	else {
		std::cout << "Nu e palindrom!\n";
	}

	return 0;
}

 

[MAMRETRAS]

@shanker'

Problema de pe PBINFO:

Date de intrare

Fișierul de intrare palindrom.in conține pe prima linie un număr natural n, iar pe următoarele n linii câte un cuvânt alcătuit din litere mici ale alfabetului englez.

 

Dupa cum am mai zis si in alte topicuri, citeste enuntul problemei. Daca citesti enuntul cu atentie, vei ajunge sa eficientizezi toate programele pe care le scrii.

Oricum, nu de acolo am zis ca e mai eficient, ci din alta perspecitva.

 

Functia std::reverse face doar N / 2 operatii (unde N este dimensiunea stringului), functioneaza dupa modelul:

string: 1234 size: 4

PAS 1: inverseaza 1 cu 4 -> devine 4231

PAS 2: inverseaza 2 cu 3 -> devine 4321

2 pasi pentru size 4

 

Tu ce faci?

Pentru fiecare caracter noul string += cel mai din dreapta caracter:

string: 1234 size 4:

PAS 1: nou_string += 4 -> nou_string = 4

PAS 2: nou_string += 3 -> nou_string = 43

PAS 3: nou_string += 2 -> nou_string = 432

PAS 4: nou_string += 1 -> nou_string = 4321

 

Asta' e prima observatie, a 2-a fiind faptul ca operatorul "+=" de la std::string nu e O(1), ci worst case e O(N) unde N este dimensiunea stringului.

Ceea ce inseamna ca IN TOTAL (folosesti de N ori operatorul "+=") ai N * (N - 1) / 2) operatii, ceea ce inseamna O(N ^ 2) worst case, pe cand cu std::reverse worst case e O(N).

 

O(N) < O(N ^ 2), ai aici un articol despre complexitati: https://ro.wikipedia.org/wiki/Complexitate_în_timp

Oricum, recomand versiunea in engleza, deoarece cea in romana nu acopera toate subiectele, asta desigur, daca vrei sa progresezi.

 

Desigur, daca problema presupune ca sunt si litere mari (nu e cazul acum), sunt de acord cu functia std::transform cu o functie lambda inauntrul ei. Felicitari pentru idee

Edited January 27, 2020 by Vesca

[Andreigl]

@Vesca,

 

poți pune și un exemplu pt. funcția reverse, dar funcție externă? ?

 

E mai ok o funcție externă, mai ales pt. începători  

 

std::string reverse(std::string myString)
{
	int j = 0;
	for (int i = myString.length() - 1; i > j; i--)
	{
		char aux = myString[i];
		myString[i] = myString[j];
		myString[j] = aux;
		j++;
	}

	return myString;
}

 

Edited January 27, 2020 by shanker'

[MAMRETRAS]

15 minutes ago, shanker' said:

@Vesca,

 

poți pune și un exemplu pt. funcția reverse, dar funcție externă? ?

std::string custom_reverse(std::string input) {
	// se poate pune input.size() in for, deoarece e O(1)
	// nu e O(N) precum functia strlen()
	for (int npos = 0; npos < input.size() / 2; ++npos) {
		std::swap(input[npos], input[input.size() - npos - 1]);
	}
	return input;
}

P.S.

43 minutes ago, shanker' said:

string-ul

se scrie "stringul".

 

Sa nu crezi ca am ceva cu tine ca te tot corectez. Consider ca ai o gandire matura si nu te superi, ci dimpotriva, o iei ca atare si inveti din greseli. Un om intelept intodeauna cauta sa stie mai multe.

DOOM 2 (Dicționar ortografic ortoepic și morfologic al limbii române):

CRATIMA

...

 

Ai si in acest topic explicata utilizarea cratimei in cuvintele imprumutate din alte limbi:

 

Edited January 27, 2020 by Vesca

[Andreigl]

@Vesca,

 

Cum am zis mai sus, pentru un începător, cel mai bine ar fi să fie totul făcut manual, nu funcții interne ?

 

std::string reverse(std::string myString)
{
	int j = 0;
	for (int i = myString.length() - 1; i > j; i--)
	{
		char aux = myString[i];
		myString[i] = myString[j];
		myString[j] = aux;
		j++;
	}

	return myString;
}

 

[MAMRETRAS]

Dimpotriva, tin sa te contrazic.

 

E mai usor de inteles ce face:

int a = 5, b = 7;
std::swap(a, b);

(e limba engleza, swap = interschimbare, e ca si cum ai citi)

decat:

int a = 5, b = 7, temp;
temp = a;
a = b;
b = temp;

Desigur, e bine sa stii ce face functia in spate, dar e mai usor de inteles cu functii, de aceea limbajele de programare High Level (python, Java, C# etc.) sunt mai populare, deoarece au functii interne numeroase care ajuta programatorul sa scrie codul mai usor.

 

Asta' din nou, zic din experienta. Am avut ocazia sa predau unor studenti de la o facultate de prestigiu din Romania care dupa ce le-am aratat niste functii interne au venit cu intrebari precum:

 

"Vrei sa zici ca am facut cursul de P1 degeaba?",
"De ce la cursuri nu ne invata asa ceva si ne pune sa scriem 10 linii in loc de 1?" sau chiar

"Mai are rost sa merg la curs? Am invatat in 4 ore tot cursul."

 

Raspunsul meu a fost:
"La curs va invata logica din spate, intai trebuie sa ganditi, apoi sa o luati pe scurtatura cu functii de genul."

 

Deci nu sunt contra ce faci tu, chiar incurajez. Sunt contra gandirii care nu progreseaza.

Edited January 27, 2020 by Vesca

[Andreigl]

T/C.