Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Pascal
Перезагрузить страницу Нужно написать принцип работы программы
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
juicy juicy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.07.2011
По умолчанию Нужно написать принцип работы программы - 24.07.2011, 22:59

Pascal Код:
PROGRAM Boyer_Moore_2;
{ Алгоритм Бойера-Мура для определения  вхождения подслова P в слово S }
var Wrd1,Wrd2: String[255];
j,i,k,i0: Integer;
d : Array['a'..'z'] of Integer;
S : Array[0..255] of Char;
P : Array[0..255] of Char;
N,M : Integer; ch : Char;
BEGIN
        Write('Введите основное слово: ');
        ReadLn(Wrd1);
        Write('Введите слово для поиска: ');
        Read(Wrd2);
        n:=Length(Wrd1);
        m:=Length(Wrd2);
        For j:=0 to n-1 do S[j]:=Wrd1[j+1];
        For j:=0 to m-1 do P[j]:=Wrd2[j+1];
        { ------------------------------- }
        For ch:='a' to 'z' do d[ch]:=m;
        For j:=0 to m-2 do d[P[j]]:=m-j-1;
        i:=m;
        i0:=0;
        Repeat
                While i0<i do
                begin
                        Write(S[i0]);
                        i0:=i0+1
                end;
                j:=m;
                k:=i;
                Repeat
                        k:=k-1;
                        j:=j-1
                until (j<=0) OR (P[j]<>S[k]);
                i:=i+d[S[i-1]]
        until ((j<=0) OR (i>N)) AND ((i>n) OR (P[j]=S[k]));
        WriteLn;
        If (j=0) AND (S[k]=P[j]) then WriteLn('Подслово найдено.') else WriteLn('Подслово не найдено.')
END.
Ответить с цитированием
  (#2 (permalink)) Старый
Некит Некит вне форума
Member
 
Сообщений: 37
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.07.2011
По умолчанию 24.07.2011, 23:23

Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

ИМХО, лучше использовать функцию pos и не парить мозг
Ответить с цитированием
  (#3 (permalink)) Старый
juicy juicy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.07.2011
По умолчанию 24.07.2011, 23:30

эммм...а есть вариант, чтоб это как то подробней все описать? если не сложно, напишите пожалуйста!)
но все равно, огромное спасибо)
Ответить с цитированием
  (#4 (permalink)) Старый
Forestop Forestop вне форума
Member
 
Аватар для Forestop
 
Сообщений: 100
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 13.06.2011
По умолчанию 25.07.2011, 08:17

Я решил так:
Можно искать строку используя функцию pos и рекурсию:
Пусть sim = 1, где sim будет номером символа шаблона.
То есть мы сначала в программе проверяем есть ли первый символ шаблона в строке, и если есть передаём функции sim + 1.
Потом в функции делаем туже самую проверку, и если удача передаём снова функции новый sim + 1, и так пока совпадение не будет найдено или же sim будет равняться длине шаблона. Вот мой код:

Pascal Код:
program z1;
var text, st: string;
    sim: integer;
procedure Search ( sim: integer );
begin
 if pos ( st[sim], text ) <> 0 then begin
  if sim = length ( st ) then
   writeln ( 'Подстрока найдена' )
  else
   Search ( sim + 1 );
 end else
  writeln ( 'Подстрока не найдена' );
end;
begin
 sim:=2;
 readln ( text );
 readln ( st );
 if pos ( st[1], text ) > 0 then
  Search ( sim )
 else
  writeln ( 'Подстрока не найдена' );
end.
Ответить с цитированием
  (#5 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 25.07.2011, 09:38

Цитата:
Сообщение от Некит Посмотреть сообщение
лучше использовать функцию pos и не парить мозг
Цитата:
Сообщение от Forestop Посмотреть сообщение
Я решил так:
Можно искать строку используя функцию pos и рекурсию:
Однако, господа, думаю, что задача изначально на понимание алгоритма быстрого поиска Бойера-Мура (см. комментарий). Зря вы так от него отмахиваетесь, идея очень красивая. Я в свое время с удовольствием покопался.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
juicy juicy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.07.2011
По умолчанию 25.07.2011, 11:56

Цитата:
Сообщение от Alexiski Посмотреть сообщение
Однако, господа, думаю, что задача изначально на понимание алгоритма быстрого поиска Бойера-Мура (см. комментарий). Зря вы так от него отмахиваетесь, идея очень красивая. Я в свое время с удовольствием покопался.
=) так может тогда сможешь помочь с написание принципа работы программы(алгоритмом) ?
Ответить с цитированием
  (#7 (permalink)) Старый
Некит Некит вне форума
Member
 
Сообщений: 37
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 21.07.2011
По умолчанию 25.07.2011, 12:11

Вам нужно разъяснить каждую строчку данного алгоритма?
В принципе не проблема
Пиши experiencenek@mail.ru
Ответить с цитированием
  (#8 (permalink)) Старый
juicy juicy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 24.07.2011
По умолчанию 25.07.2011, 12:21

Цитата:
Сообщение от Некит Посмотреть сообщение
Вам нужно разъяснить каждую строчку данного алгоритма?
В принципе не проблема
Пиши experiencenek@mail.ru
ок, буду рада если поможешь)
Ответить с цитированием
  (#9 (permalink)) Старый
Виталик 1 Виталик 1 вне форума
Member
 
Сообщений: 1,286
Сказал(а) спасибо: 1
Поблагодарили 3 раз(а) в 2 сообщениях
Регистрация: 14.06.2006
По умолчанию 27.07.2011, 11:29

чем не устраивает объяснение тут: Алгоритм Бойера — Мура — Википедия ?
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
За три часа нужно написать три программы Студент_ Вопросы начинающих программистов 1 09.06.2011 13:58
Нужно написать алгоритм для программы С++ Undergrind Алгоритмы 0 29.05.2011 23:33
Принцип работы с GPSS LilyM Вопросы начинающих программистов 0 09.01.2011 17:53
Нужно объяснить принцип работы предиката zlob.jc Prolog 4 31.05.2010 03:14
Выручайте. Нужно 2 программы написать МОРФЕМА Pascal 9 05.08.2009 04:13
Какой принцип работы DC++? Bronks Любые вопросы от новичков 1 08.08.2008 23:23
Какой принцип работы FDD? mkr Любые вопросы от новичков 2 20.07.2008 00:37
Принцип работы sleep Shady С/С++ 2 31.03.2008 01:21
COM - Технология принцип работы с ней Saracin Visual C++ 12 13.03.2006 11:33
Принцип работы клиент сервер sq-Weezee C++ Builder 3 06.03.2006 19:52
В чем заключается принцип работы Autodesk Map 5 KISSKA Вопросы начинающих программистов 8 09.01.2006 14:05
Нужно написать программу для работы с LPT портом FireCrush Delphi 1 06.07.2005 11:25



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов