Programowanie w języku Delphi » FAQ

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++:
bool isPalindrome(const std::string &s) {
  return std::equal(s.cbegin(), s.cbegin() + s.length() / 2, s.crbegin());
}



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


def is_palindrome(s):
    return s[::-1] == s

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

cheox 2009-10-28 23:52

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 ??

ferdzikamil 2009-09-29 23:10

// w ANSI C

  1. include <stdio.h>
  2. 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");
}

}

damianromek 2007-12-18 12:26

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

sasio 2007-04-28 01:11

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

Coldpeer 2007-04-27 22:30

@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)

sasio 2007-04-27 20:24

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

TyDraniu 2007-04-05 18:11

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

Sprawdziłeś ten kod?

Coldpeer 2007-04-03 22:57

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.

sasio 2007-03-31 19:31

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.

Coldpeer 2007-03-31 14:35

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

sasio 2007-03-31 00:53

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

Marooned 2007-03-30 15:44

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

Dryobates 2007-03-28 21:58

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...

Marooned 2007-03-27 01:06

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));}

Dryobates 2007-03-26 21:53

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):]))

Coldpeer 2007-03-26 17:49

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

Marooned 2007-03-26 17:47

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

Coldpeer 2007-03-26 17:44

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.

Marooned 2007-03-26 17:38

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 :/

kz_x 2007-03-28 20:25

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