Меню

Първи стъпки в правене на сайтове

Влез Излез

Тестване на палиндроми – част 3

Във втора част на урока намерихме най-добрия начин за премахване на всички символи, освен букви, за да можем да тестваме палиндрома.

В този урок ще разгледаме начин за проверка дали в прав и обратен ред текстът, който тестваме е еднакъв (с други думи – дали е палиндром).

Сравняваме буква по буква, като вземем първата и последната, после втората и предпоследната и т.н.

Взимане на буква от string може да стане чрез функцията substr() (би трябвало вече да е позната от урока функции за текст).

Аргументите, които тази функция приема са 3:

  1. string-а, от който искаме да „отрежем“ парче

  2. начална позиция

  3. дължина на отрязъка

Последният аргумент не е задължителен, и ако не е зададен ще върне текста до край.

Така че:

substr('some text', 5);

ще върне „text“, защото ще прескочим първите 5 знака (включва се празният интервал) и ще върне текста до края.

Ако имаме:

substr('some text', 0, 1);

това ще върне „s“ – няма да прескочим никакви знаци (ще започнем от самото начало) и ще върнем string с дължина 1 буква.

По този начин можем да вземем първата, втората и т.н. буква от даден текст.

Можем да използваме същата функция, за да вземем последната, предпоследната и т.н. буква, със съвсем малка промяна.

substr('some text', -1, 1);

ще върне „t“ – последната буква.

Функцията работи така, че ако вторият аргумент (този, който определя колко букви трябва да прескочим) е отрицателно число, ще започнем толкова знака преди края.

Може да си го представите все едно, че текстът е увит около нещо кръгло и когато от първата буква се върнем 1 назад отиваме на последната. Само, че тази аналогия не е напълно правилна, тъй като:

substr('some text', -2);

ще върне само „xt“ – отново при достигане до края на текста функцията спира и връща резултата – без да се взима предвид „кръговата“ функционалност, която е описано по-горе.

Значи първа буква (аргумент 0), трябва да сравняваме с -1, втората буква (1), трябва да сравняваме с -2. Хубаво е човек да си разиграе на ум 1-2 примерни цикъла, преди да започне да пише код, тъй като тази разлика в абсолютните стойности (модул) от числата трябва да се вземе предвид.

Освен това трябва да се обмисли и вариантът за последна буква – в единия случай ще е 11, но в другия не можем да имаме -12, тъй като няма 12 букви и не можем да се върнем толкова назад.

В този случай трябва да се направи проверка и да се вземе първата буква с индекс 0.

Значи трябва да сравняваме резултатите от тази функция, викани по подобен начин, толкова пъти колкото букви имаме в първоначалния текст. Тъй като ще извършваме една и съща операция неколкократно най-добре това би било с цикъл. Единственото, което трябва да се уточни е колко пъти ще бъде изпълнен цикъла. Всъщност – вече го казахме – толкова пъти, колкото букви има в текста. А това можем да го разберем с функцията strlen():

# подготваме string за тестване
$test = 'If I Had a Hi-Fi';

# премахваме всички знаци, освен букви
$simplified = preg_replace('/\W/', '', $test);

# по презюнкция текстът е палиндром; в моментът в който установим, че не е ще променим и този флаг
$is_palindrome = true;

# изпълняваме тялото на цикъла толкова пъти, колкото букви има в $simplified
for ($i = 0; $i < strlen($simplified); $i++) {
    $index_b = -($i+1);

    if ($index_b < - (strlen($simplified)) ) {
        $index_b = 0;
    }

    # взимаме първата буква
    $a = substr($simplified, $i, 1);

    # взимаме последната буква
    $b = substr($simplified, $index_b, 1);

    # проверяваме дали първата и последната буква са еднакви
    if ($a != $b) {
        # ако не са -- отбелязваме, че текстът, който тестваме не е палиндром
        $is_palindrome = false;
    }
}

# извеждаме резултата
var_dump($is_palindrome);

Само че това не работи, защото изкарва false накрая.

Защо се получава това? Защото буквите може да са малки и главни и тогава не са еднакви. Това можем да оправим с обикновено strtolower(), след като премахнем излишните знаци (нищо не пречи да го направим и преди това де).

Преди да сме разгледали обновения код – нека видим какво още можем да оптимизираме.

Можем да намалим броя на повторенията на цикъла. Ако първата буква е същата като последната, втората – като предпоследната, и т.н. до средата – няма нужда да правим повече проверки, тъй като ние реално повтаряме тези, които вече сме направили.

Затова можем условието $i < strlen($simplified) да го променим да е два пъти по-малко.

В този случай отпадат и проверките за $index_b, което също скъсява кода.

Освен това можем да прекратим цикъла още първия път, когато установим, е текстът не е палиндром – няма нужда да правим повече проверки.

$test = 'If I Had a Hi-Fi';

$simplified = preg_replace('/\W/', '', $test);
$simplified = strtolower($simplified);

$is_palindrome = true;

$repetition = strlen($simplified);

# достатъчно е да проверим до средата, тъй като се очаква да е огледално
$repetition = $repetition / 2;

for ($i = 0; $i < $repetition; $i++) {
    $a = substr($simplified, $i, 1);
    $b = substr($simplified, -($i+1), 1);

    # стриктната проверка работи маааалко по-бързо
    if ($a !== $b) {
        $is_palindrome = false;

        # няма нужда да правим повече проверки -- вече е ясно, че не е палиндром
        break;
    }
}

var_dump($is_palindrome);

Въпреки, че направихме няколко оптимизации, като цяло вършим доста работа и тази проверка не е най-добрата, която можем да постигнем.

В следващия урок ще разгледаме друг начин, който не само е по-бърз за изпълнение от компютрите, но и е доста по-кратък (следователно – лесен и за програмистите).

Вашият коментар

Вашият имейл адрес няма да бъде публикуван. Задължителните полета са отбелязани с *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax