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; }
C#
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:
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:
def is_palindrome(s): 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
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:
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:
is_palindrome(A, A). is_palindrome([_|A], A). is_palindrome([H|T], L) :- is_palindrome(T, [H|L]).
21 komentarzy
// 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");
}
}
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
kz_x: oszukujesz, odwracasz całość :P
Jeżeli tak na to patrzeć to:
Python:
PHP:
Boję się pomyśleć, jak to w perlu by wyglądało...
Tak dla zabawy. Jednolinijkowiec [PHP]:
Tak dla zabawy. Jednolinijkowiec [Python]:
:) 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): <b>p(x):=(x=str_revert(x));</b> (nie za szybkie, ale krótkie)
Kto da mniej?
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 ??