Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Октябрь 2005   →
 1
 2
 3
03.10.2005
09:24:00
14:05:19
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП) Проверка на палиндромность


Информационный Канал Subscribe.Ru

Проверка на палиндромность

Многие участники для проверки того, является ли строка палиндромом, используют следующий алгоритм.

Пусть дана строка S
1. Создаём строку L, равную S записанной в обратную сторону.
2. Сравниваем строки S и L на равенство.
Назовём этот алгоритм алгоритм с переворачиванием. Разберём недостатки такого алгоритма.

Палиндром - строка символов, которая записывается одинаково слева направо и наоборот.

Т.е. если X1 X2 X3 ... Xn - строка, где Xi-символы, определение говорит, что X1 X2 X3 ... Xn = Xn Xn-1 ... X2 X1

Есть алгоритм, который работает значительно быстрее, чем алгоритм с переворачиванием. Для этого достаточно просматиривать строку начиная с краёв, но только до средины.

Обоснование того, что просмотр выполняется только до середины.
X1 X2 X3 ... Xn = Xn Xn-1 ... X2 X1
Следовательно
X1=Xn
X2=Xn-1
...
Xn=X1

Т.к. Xi=Xj то же что и Xj=Xi. Следовательно, можно рассматривать только равенства
X1=Xn
X2=Xn-1
...
Xk=Xn-k+1, где k=n div 2
Для нечётного n есть ещё одно равенство, но оно имеет вид Xk+1=Xk+1, а значит верно всегда и его можно не рассматривать.

Отсюда видно, что дольше всего алгоритм будет работать на палиндромах, около N/2 шагов. Алгоритм с переворачиваем строки: N шагов - переворот и N шагов - сравнение. Получается, что алгоритм с переворачиваем строки занимает в два раза больше памяти и работает в (N+N)/(N/2) = 4 раза дольше.

Ещё хуже алгоритм с переворачиванием ведёт себя в лучшем (самом быстром) случае. Это случай когда первый и последний символ различны. Если оптимальный алгоритм работает 1 шаг, то алгоритму с переворачиванием нужно N шагов на переворот.

Ниже приведена реализация на языке Turbo Pascal оптимального алгоритма. 
(******  Программа на PASCAL *****)

Program task01;
Var S     : String; {Строка}
    L,R   : byte;
Begin
  Write('Строка: '); ReadLn(S);
  L:=1; R:=Length(S);
  while (L < R) and (S[L]=S[R]) do
  begin
     L:=L+1; R:=R-1;
  end;
  if S[L]=S[R] then writeLn('Палиндром.') 
  else writeLn('Не палиндром.');
End.
(******  Конец программы *****)
Одно из преимуществ такой реализации - наглядность, сразу видно, что делает программа.

Автор: Пупышев Вячеслав Викторович   
e-mail: pvv@uni.udm.ru   
Web: http://colymp.da.ru   
Subscribe.Ru
Поддержка подписчиков
Другие рассылки этой тематики
Другие рассылки этого автора 		Подписан адрес:
Код этой рассылки: comp.soft.prog.comp
Архив рассылки 		Отписаться
Вспомнить пароль
В избранное