Come verificare se un INT è palindromo!C++

Messaggioda Alex7337 » 23/08/2019, 15:20

Salve ragazzi vorrei sapere come posso convertire una varibile int, per esempio int = 121 in un vettore in modo tale da poter verificare se è palindroma o meno. Poi volevo sapere se effettivamente esistono alternative al metodo prima citato. Grazie.
Alex7337
New Member
New Member
 
Messaggio: 23 di 61
Iscritto il: 25/01/2019, 16:42

Re: Come verificare se un INT è palindromo!C++

Messaggioda apatriarca » 23/08/2019, 16:30

Puoi probabilmente usare qualcosa come itoa. Oppure fare un ciclo in cui leggi una cifra per volta.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5286 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Come verificare se un INT è palindromo!C++

Messaggioda marco2132k » 24/08/2019, 14:30

Se devi farlo tu: il numero \( 121 \) è scrivibile come \( 1\cdot 10^2+2\cdot 10^1+1\cdot 10^0 \). Potresti pensare ad una funzione che determini i resti \( 1 \), \( 2 \) e \( 1 \), e confrontarne l'out quello di una reverse che rovescia una lista. Però penso che in C una cosa del genere debba passare per i puntatori :shock:

Anzi, nella STL c'è il template std::vector, quindi se ti è ammessa li puoi evitare.

Ad esempio, se \( n\in\mathbb{N} \) è scritto in base \( b \) come \( n=\sum_{i=0}^k n_kb^{k-i}\), così:
Codice:
std::vector<int> ns_b(const & int base, const & int n) {
  // codice ricorsivo
}

std::vector<int> reverse(const & std::vect<int> v) {
  // roba
}

bool palindrome (const & int base, const & int n) {
  return ns_b(base, n) == reverse(ns_b(base, n));
}


p.s. Non ho la minima idea riguardo alla correttezza del codice che ho scritto (in particolare non sono sicuro che l'uso di == per vedere se due std::vect<int> sono uguali è lecito). Se vuoi, ignora i const &.
marco2132k
Advanced Member
Advanced Member
 
Messaggio: 370 di 2053
Iscritto il: 18/02/2018, 23:52

Re: Come verificare se un INT è palindromo!C++

Messaggioda Super Squirrel » 24/08/2019, 17:19

Alex7337 ha scritto:Salve ragazzi vorrei sapere come posso convertire una varibile int, per esempio int = 121 in un vettore in modo tale da poter verificare se è palindroma o meno.

L'ultima cifra di un numero n può essere estrapolata semplicemente utilizzando l'operatore modulo (il secondo operando credo sia ovvio). Una volta salvata la cifra in un array di int o char bisogna eliminare l'ultima cifra da n utilizzando l'operatore divisione intera e ripetere il suddetto procedimento finché n>0.
Terminata la procedura, per verificare che n sia palindromo, ti basterà controllare che l'array ottenuto sia simmetrico rispetto al suo "centro", ossia confronti il primo elemento con l'ultimo, il secondo con il penultimo e così via...
Vale la pena precisare che il tutto può essere fatto senza scomodare puntatori e std::vector.
Alex7337 ha scritto:Poi volevo sapere se effettivamente esistono alternative al metodo prima citato. Grazie.

Volendo si può anche evitare di utilizzare un vettore, confrontando direttamente la prima e l'ultima cifra di n, ma risulta un po' più macchinoso dal punto di vista dei calcoli.
Chi dorme in democrazia, si sveglia in dittatura.
Super Squirrel
Senior Member
Senior Member
 
Messaggio: 375 di 1486
Iscritto il: 16/05/2013, 22:05

Re: Come verificare se un INT è palindromo!C++

Messaggioda vict85 » 26/08/2019, 17:32

Usando la libreria standard puoi fare qualcosa di questo tipo:
Codice:
#include <iostream>
#include <string>
#include <algorithm>

bool test_palindromo( int num )
{
    const auto number = std::to_string( num );
    return std::equal( number.begin( ), number.begin( ) + (number.size( )/ 2), number.rbegin( ) );
}
Seppur questo metodo sia del tutto equivalente a quello che usa gli array. Questo approccio usa però l'allocazione dinamica1. Il C++17 aggiunge anche la funzione to_chars che permette di evitare l'allocazione dinamica, ma complica un po' il codice.

È inoltre possibile farlo senza usare alcun vettore di appoggio, ma è meno immediato da fare e il vettore di appoggio è di appena 20 caratteri (quindi la versione che usa gli array è generalmente consigliata). Se ti interessa posso però scriverti quella versione.

Note

  1. Inoltre, l'approccio che usa l'array non ha bisogno di mettere le cifre nell'ordine corretto della stampa, cosa che invece fa questa versione.
vict85
Moderatore
Moderatore
 
Messaggio: 9787 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Come verificare se un INT è palindromo!C++

Messaggioda apatriarca » 27/08/2019, 08:08

Sinceramente non vedo come l'approccio che non fa uso di un array di appoggio sia più complicato di quello che ne fa uso, soprattutto volendo scriverlo senza fare uso di alcuna funzione standard. In effetti il codice è anche più corto.
Codice:
bool is_palindrome_noarray(unsigned value)
{
  unsigned reversed = 0;
  unsigned v = value;
 
  while (v > 0) {
    reversed = reversed * 10 + (v % 10);
    v /= 10;
  }

  return value == reversed;
}

bool is_palindrome_array(unsigned value)
{
  int digits[20];
  int ndigits = 0;
  while (value > 0) {
    digits[ndigits++] = value % 10;
    value /= 10;
  }

  for (int i = 0, j = ndigits-1; i < j; ++i, --j) {
    if (digits[i] != digits[j]) {
      return false;
    }
  }

  return true;
}

L'idea è semplicemente quella di estrarre le cifre dalla meno significativa e inserirle "al contrario" in un altro numero. Se alla fine delle cifre i due numeri sono uguali allora il numero è palindromo. Nota che ho usato unsigned perché non sono sicuro di come si dovrebbe trattare un numero negativo..
apatriarca
Moderatore
Moderatore
 
Messaggio: 5288 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Come verificare se un INT è palindromo!C++

Messaggioda vict85 » 28/08/2019, 12:33

Avevamo detto che era più complessa perché non avevamo pensato di usare un intero di appoggio per contenere il numero riflesso. D'altra parte, pensandoci un po', mi sono reso conto che quella soluzione ha un problema: alcuni interi a 32 bit hanno un numero riflesso che non può essere contenuto in un intero a 32 bit. Questi numeri non sono ovviamente palindromi, quindi è possibile adattare il codice per funzionare con tutti i valori positivi. Non saprei dire se, nel caso di unsigned (in cui l'overloading non è un UB), sia possibile ignorare il problema1.

Note

  1. In altri termini non saprei dire se \(r(n) \neq n \Rightarrow r(n) \not\equiv n \pmod{2^{32}}\) dove ho segnato con \(r\) la riflessione del numero in base \(10\).
vict85
Moderatore
Moderatore
 
Messaggio: 9793 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: Come verificare se un INT è palindromo!C++

Messaggioda apatriarca » 28/08/2019, 14:33

È possibile usare un intero a 64 bit per contenere il numero riflesso risolvendo il problema. In alternativa è anche possibile riscrivere l'algoritmo in modo da fermarsi a metà delle cifre. È più complicato perché è necessario considerare separatamente i casi in cui il numero di cifre è pari o dispari, ma non è impossibile e tutti i valori saranno rappresentabili.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5289 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: Come verificare se un INT è palindromo!C++

Messaggioda vict85 » 28/08/2019, 16:24

Hai ragione, ma basta ignorare una singola cifra.
Codice:
#include <stdint.h>
#include <iostream>

bool
is_palindrome( uint32_t value )
{
    uint32_t reversed = 0;
    uint32_t v = value;

    while ( v > 9 )
    {
        reversed = reversed * 10 + ( v % 10 );
        v /= 10;
    }

    return ( value / 10 ) == reversed;
}

int
main( )
{
    std::cout << std::boolalpha << is_palindrome( 121 ) << " " << is_palindrome( 123456 ) << " "
              << is_palindrome( 4294967295 ) << " " << is_palindrome( 4294884924 ) << " "
              << is_palindrome( 4 ) << " " << is_palindrome( 4294884925 ) << " "
              << is_palindrome( 3294884924 ) << std::endl;
}


Anche se con questi specifici esempi anche il vecchio codice non faceva errori.
vict85
Moderatore
Moderatore
 
Messaggio: 9794 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite