Czy wyraz jest palindromem
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
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
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++:
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;
}
{
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;
}
Pascal:
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;
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:
def is_palindrome(s):
i = len(s)/2
while i:
i -= 1
if s[i] != s[-i-1]: return False
return True
i = len(s)/2
while i:
i -= 1
if s[i] != s[-i-1]: return False
return True
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
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:
function is_palindrome($s)
{
$i = (int)(strlen($s)/2);
while($i--)
if($s[$i] != $s[strlen($s)-$i-1]) return false;
return true;
}
{
$i = (int)(strlen($s)/2);
while($i--)
if($s[$i] != $s[strlen($s)-$i-1]) return false;
return true;
}
JavaScript:
function isPalindrome(s)
{
var i = (int)(s.length/2);
while(i--)
if(s.charAt(i) != s.charAt(s.length-i-1)) return false;
return true;
}
{
var i = (int)(s.length/2);
while(i--)
if(s.charAt(i) != s.charAt(s.length-i-1)) return false;
return true;
}
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)
Sprawdziłeś ten kod?
PS. moja pierwsza wersja tego tekstu zawierała kod Pascala, zbliżony ideologią trochę do Twojego
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
Jeżeli tak na to patrzeć to:
Python:
PHP:
Boję się pomyśleć, jak to w perlu by wyglądało...
Kto da mniej?
Usunąłem już z Algorytmów - teraz jest 1x.
// kurdę, znowu się coś z kategoryzacją skrzaczyło.
Pseudokod + implementacje w wielu językach - super!
Tylko dlaczego 2x w Algorytmach. I te 4 FAQ wygląda śmiesznie