C++ Algoritmisch Eenvoudige Recursieve Palindroom Checker

Ik heb een string palindroom checker geschreven die volgens mijn instructeur ingewikkelder is dan nodig is. Ik heb soortgelijke discussies gelezen en gegoogled, maar ik weet totaal niet hoe ik het kan laten werken met minder stappen dan dit…

void isPal(string str){
int length = str.length();
if(length <= 1) cout << "Palindrome" << endl;//check for zero or one digit numbers
else if(str.at(0) == str.at(length -1)) {
    str = str.substr(1, (length - 2));
    isPal(str);}
else cout << "Not a palindrome." << endl;{
    cin >> str;}

Antwoord 1, autoriteit 100%

Controleer dit:

int is_pal(int start, int end, string &str)
{
    if (start >= end)
        return 1;
    if (str[start] != str[end])
        return 0;
    return is_pal(++start, --end, str);   
}

Bel de methode aan vanuit main. Laat me weten of dat helpt.. 🙂

Antwoord 2, autoriteit 100%

Recursie gebruiken

Als je nog steeds recursie wilt gebruiken, doe dan zoiets als:

bool isPal(const string &str, int start, int end)
{
    if (start >= end)   
        return true;
    if (str[start] != str[end])
        return false;
    return isPal(str, ++start, --end);   
}

En bel isPal(str, 0, str.length()-1)in de hoofdtekst. Het idee is om twee indexen te gebruiken en ze te verplaatsen, omdat je niet elke keer in recursie substr()wilt gebruiken.

Zonder recursie

Eigenlijk is dit probleem eenvoudig op te lossen zonder recursie als volgt te gebruiken:

bool isPal(const string &str)
{
    int start=0, end=str.length()-1;
    while (start < end) {
        if (str[start++] != str[end--]) 
            return false;
    }
    return true;
}

Antwoord 3, Autoriteit 33%

Het moet een functie zijn die true of false retourneert en geen bericht afdrukt. De parameter moet een enkel string-object zijn.

bool isPalindrome( const std::string & word ){
  std::string::const_iterator fwd = word.begin();
  std::string::const_iterator rev = word.end();
  if( rev - fwd <= 1 ) return true;
  if( *fwd++ != *--rev ) return false;
  return isPalindrome( std::string( fwd, rev ) );
}

later

Dus een recursief oplossing met een enkele parameter vereist een nieuw string-object met elke recursie. Dit is gecritisiseerd als zijnde “vreselijk” – maar is het echt? Een algoritme moet worden beoordeeld in relatie tot het domein waarvoor het is bedoeld.

Laten we aannemen dat dit domein de woorden van de Engelse taal is. Er is meer dan 1.000.000 woorden in de Engelse taal, maar het aantal palindromen is minder dan 200. Dus de kans dat de recursie helemaal moet gaan naar N / 2-iteraties is bijna verwaarloosbaar. Ook is het percentage woorden met gelijke eerste en laatste letters erg klein, en daarom is in de meeste gevallen niet eens een enkele recursie vereist.

Een ander mogelijk domein is willekeurige snaren die zijn samengesteld uit de letters ‘A’ naar ‘Z’: meer dan 96% vereist zelfs geen enkele recursieve oproep. “Vreselijk”? Nauwelijks.

Als u deze “horror” wilt vermijden, heeft men drie opties: vermijd recursie, gebruik een tweede methode (om van de eerste te worden genoemd) of vereisen meer dan één argument.

De derde variant is door anderen voorgesteld, die niet minder dan drie argumenten vereist, die de gebruiker vragen om overtollige informatie te bieden met een nogal rommelige oproep, b.v.:

string word = "evitative";
bool res = isPal( word, 0, word.length()-1 );

Niet echt aangenaam, is het? – Maar men kan het beter doen dan dat!

bool isPal2( string::const_iterator fwd, string::const_iterator rev ){
    return rev - fwd <= 1 || *fwd++ == *--rev && isPal2( fwd, rev );
}

Met een matig complexe oproep:

string word = "reviver";
bool res = isPal2( word.begin(), word.end() );

Nu hebben we de oprichting van string-objecten vermeden, zelfs in die zeldzame gevallen van palindromen of “palindrogeens” ten koste van één extra parameter, tenminste zonder overbodig informatie.

Antwoord 4

Hmm maakt het niet recursief is een poging

int i = 0;
int j = str.length() - 1;
bool isPalindrome = true;
while(i < j && isPalindrome)
{
   if(str[i++] != str[j--]) isPalindrome = false;
}

Antwoord 5

Als u probeert te controleren of een string palindrome is of niet, kunt u het gemakkelijk doen als:

1. Steek de tekenreeks in een vector Stel dat V
2. Omgekeerd de vector v en plaats het op een andere vector genaamd Stele V1.
3. als v == v1, dan palindrome, anders niet.

Ik heb zojuist een methode voorgesteld om Palindrome te controleren. niets anders.

Antwoord 6

bool isPalindrome(char str[], int i) {
    int x=(strlen(str)-i);
       if (i==0) {
      return true;
   }
   if (str[x]!=str[i-1]) {
      return false;
   }
   return isPalindrome(str, i-1);
}