Delphi FAQ

Czy wyraz jest palindromem

Coldpeer

Palindrom (tudzież anagram odwrotny) jest to wyraz, liczba, który odczytany zarówno normalnie (od przodu), jak i wspak (od tyłu) daje taki sam ciąg, np. palindromem jest wyraz "kajak", czy liczba 656. Ponadto ciąg składający się z mniej niż dwóch znaków jest palindromem (np. litera K).

Pokażę za chwilę, jak napisać prosty algorytm, który będzie sprawdzał, czy dany wyraz bądź liczba jest palindromem.

Algorytm

<font name="Courier New"> 1. boolean is_palindrome(string S) 2. begin 3. integer I ← (ilość znaków z S) div 2 // przyjmujemy S[0] = pierwsza litera S 4. while I > 0 do 5. begin 6. I ← I - 1 7. if S[I] != S[ilość znaków z S - I - 1] then return false 8. end 9. return true 10. end</span> 3. Deklaracja zmiennej I i przypisanie do niej połowy długości ciągu (zaniedbując część ułamkową), przekazanego w parametrze funkcji. 7. Jeśli I-ty znak ciągu S jest różny od znaku na pozycji: ilość znaków z S - I - 1, zwróć false - ciąg nie jest palindromem. 9. Podczas działania pętli, nie została zwrócona wartość false, więc ciąg jest palindromem.

Implementacje

C/C++: ```cpp bool is_palindrome(char* s) { int n = strlen(s); //strlen jest kosztowne czasowo, warto zapamiętać int i = n / 2; while( i-- ) if( s[i] != s[n - i - 1] ) return false; return true; } ``` C++: ```cpp bool isPalindrome(const std::string &s) { return std::equal(s.cbegin(), s.cbegin() + s.length() / 2, s.crbegin()); } ``` C# ```csharp static bool isPalindrome(string s) { int n = s.Length; int i = n / 2; while (i-- > 0) { if (s[i] != s[n - i - 1]) return false; } return true; } ``` Pascal: ```delphi function IsPalindrome(S: String): Boolean; var I : Integer; begin I := Length(S) div 2; IsPalindrome := True; while (I > 0) do begin Dec(I); if (S[I+1] < S[Length(S) - I]) then begin IsPalindrome := False; Exit; end; end; end; ``` Python: ```python def is_palindrome(s): i = len(s)/2 while i: i -= 1 if s[i] != s[-i-1]: return False return True ``` ```python def is_palindrome(s): return s[::-1] == s ``` Ruby: ```ruby def is_palindrome(s) i = s.size/2; while i > 0 i -= 1 if s[i] != s[s.size-i-1] then return false end end return true end ``` PHP: ```php function is_palindrome($s) { $i = (int)(strlen($s)/2); while($i--) if($s[$i] != $s[strlen($s)-$i-1]) return false; return true; } ``` JavaScript: ```javascript function isPalindrome(s) { var i = parseInt(s.length/2); while(i--) if(s.charAt(i) != s.charAt(s.length-i-1)) return false; return true; } ```

Implementacje w językach funkcyjnych

Ze względu na specyficzność języków funkcyjnych i deklaratywnych, implementacje tego algorytmu mogą wyglądać w nich zupełnie inaczej. Prolog: ```prolog is_palindrome(A, A). is_palindrome([_|A], A). is_palindrome([H|T], L) :- is_palindrome(T, [H|L]). ```

22 komentarzy

Można by to wykonać bez strlen i strrev - wystarczy najpierw znaleźć sąsiadujące takie same znaki w rodzaju "...bb..." lub "...bcb..." a potem już tylko porównywać następne znaki z tym co już było.

bool isPalindrome(string s)
{
int i = s.Lenght() / 2;
while (i > 0)
{
if(s[i] != s[n - i - 1] ) return false;
i--;
}
return true;
}

gdzie tutaj masz n zadeklarowane wcześniej ??

// w ANSI C
#include <stdio.h>
#include <stdlib.h>

int palindrom(int n,char napis[]){

for(int i=0;i<(n/2);i++){
if(napis[i]!=napis[n-1-i])
{
return 0;
}
}
return 1;

}

int main(){
system("cls");

char napis[]="ANA";
int n=sizeof(napis)-1;

if(palindrom(n,napis)==1){
printf("Anagram");
}else{
printf("Nie jest");
}

}

Jestem tu nowy i wygląda to dziwnie !!! :D

sorki ale naprawde niewiem jakie ma ograniczenia Pascal wzgledem delphi :(

@Jojersztajner: w obecnym GeSHi na 4p nie ma kolorowania składni dla Ruby, a składnia Pythona jest dość podobna.
PS. jest różnica w JS między string[x] a string.charAt(x)?
PS2. no i zamieniłeś isPalindrome w pętli w Pascalu na Result, które występuje chyba tylko w Delphi? (w TP nie, nie pamiętam jak np. FPC)

lol ale gafa, racja i prawda nie sprawdzalem :D sorki juz poprawiam

@sasio, czy nie stworzyłeś pętli nieskończonej? W końcu pred(i) nie obniży i, prawda?

Sprawdziłeś ten kod?

sasio: nie mówię, że jest coś w tym złego... ale po prostu kod powinien być też dla użytkowników np. Turbo Pascala.

a jest cos w tym zlego ? i-- to wkoncu wymysl C xD. Pozatym moj kod jest 100x szybszy (samo const daje speed-a :D). Ale zostawmy ten temat arytkul na 5 , prosty, niedlugi i wystarczajacy.

Warto wspomnieć, że Pred to wymysł Delphi.
PS. moja pierwsza wersja tego tekstu zawierała kod Pascala, zbliżony ideologią trochę do Twojego :)

function IsPalindrome(const s: string): Boolean;
var i,l: integer;
begin
  Result := False;
 
  l := Length(s);
  i := l div 2;
 
  while i <> 0 do
  begin
    Dec(i);
    if s[i+1] <> s[l-i] then Exit;
  end;
 
  Result := True;
end;

Tutaj macie a wieeeeele szybsza funkcje xD

haha, no fakt, przecież można całość odbić :D

kz_x: oszukujesz, odwracasz całość :P
Jeżeli tak na to patrzeć to:
Python:

p=lambda s:s==s[::-1]

PHP:

function p($s){ return $s==strrev($s));}

Boję się pomyśleć, jak to w perlu by wyglądało...

Tak dla zabawy. Jednolinijkowiec [PHP]:

function is_palindrome($w){return strlen($w) == 1 || substr($w, 0, strlen($w)/2) == strrev(substr($w, -strlen($w)/2));}

Tak dla zabawy. Jednolinijkowiec [Python]:

def is_palindrome(s): return len(s) <=1 or list(s[:len(s)/2])==list(reversed(s[-(len(s)/2):]))

:) Hmm, ale dlaczego tekstu nie ma w kategorii JavaScript/FAQ, pomimo, że dodałem {{Cat:JavaScript/FAQ}}?

Jak tu ładnie widać przewagę konstrukcji a'la C nad konstrukcją Pascala :)

Hmm, masz trochę racji, ale jak to wyglądałoby w dziale Delphi, gdzie jest głównie sam opis języka?
Usunąłem już z Algorytmów - teraz jest 1x.
// kurdę, znowu się coś z kategoryzacją skrzaczyło.

I to się nazywa art o algorytmie!
Pseudokod + implementacje w wielu językach - super!

Tylko dlaczego 2x w Algorytmach. I te 4 FAQ wygląda śmiesznie :/

Jednolinijkowiec w CLI (cli.up.pl): p(x):=(x=str_revert(x)); (nie za szybkie, ale krótkie)
Kto da mniej?