1 Востаннє редагувалося pETRUk (16.11.2014 19:21:50)

Тема: Алгоритм прямого пошуку підпослідовності.

Маю кілька задач задали як додаткове завдання. В паскалі останній раз програмували кілька років тому, основна спеціальність в мене вчитель трудового навчання тому для мене це складно по при те що інформатику вивчаемо з 1 курсу. Ось така задача.
Задача повинна бути виконана саме в Pascal.
1.Користуючись методом прямого пошуку підпослідовності у послідовності, встановити входження деякого образу у базовий рядок. Якщо співпадання має місце, то вказати порядковий індекс елемента в базі, починаючи з якого образ повністю співпадає з елементами бази, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.
a = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2),
b = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2)
Інші задачі дуже схожі, якщо підкажете як робити цю, думаю з рештою впораюсь.
Також буду вдячний якщо хтось підкаже підручник де ця тема добре висвітлена, з прикладами та описом різних методів пошуку. Решта задач по іншим методам( Кнута Моррі Пратта, і Баєра Мурра)
Знайшов готові коди в інеті підправте один під мої данні будь-ласка з всіма додатковими умовами а далі я вже сам буду намагатись)

2

Re: Алгоритм прямого пошуку підпослідовності.

Тут потрібні вкладені цикли. Зовнішнім перебираємо "a", а внутрішнім "a" (із зсувом) і "b" одночасно, і порівнюємо. Якщо внутрішній цикл дійшов до кінця, і усі елементи співпали, то задачу вирішено.
Спробуйте зробити хоч щось, а коли буде якийсь код, форумчанам буде легше підказати вам щось конкретне.

Подякували: pETRUk1

3

Re: Алгоритм прямого пошуку підпослідовності.

Підкажіть, хтось де можна почитати саме про пошук послідовностей в послідовності з прикладами, не пом'ятаю вже нічього, навіть ввести вхідні данні зарез для мене проблематично треба все освіжити в пам'яті.

4

Re: Алгоритм прямого пошуку підпослідовності.

Освіжити пам'ять можна тут: http://replace.org.ua/topic/814/
Іще непогано тут написано, але про Делфі (сучасний Паскаль): http://www.delphikingdom.com/lyceum/seminar.asp?id=4 http://www.delphikingdom.com/lyceum/seminar.asp?id=6

Подякували: Chemist-i, pETRUk2

5

Re: Алгоритм прямого пошуку підпослідовності.

Бачів готові коди але що і куди вписувати і виправляти незнаю. допоможіть хочаб з 1 зосвім не розумію шо і куди прописувати
http://www.cyberforum.ru/turbo-pascal/thread332711.html
http://www.cyberforum.ru/turbo-pascal/thread332711.html

6 Востаннє редагувалося Torbins (17.11.2014 10:57:34)

Re: Алгоритм прямого пошуку підпослідовності.

program xren;
var
  srav,sovpalo:integer;
const 
  a:array[1..18] of integer=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2);
  b:array[1..15] of integer=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2);
begin
  for var i:=1 to 18-15 do
  begin
    sovpalo:= 0;
    for var j:=1 to 15 do
    begin
      srav:= srav + 1;
      if (a[i+j] = b[j]) then sovpalo := sovpalo +1;
    end;

    if (sovpalo = 15) then 
    begin
      writeln(i);
      writeln(srav);
    end;
  end; 
end.

1 я осилив, допоможіть з кнутом і морісом баєром. Ато я якось недуже зрозумів ці методи.

7

Re: Алгоритм прямого пошуку підпослідовності.

Будь ласка, використовуйте тег code для оформлення коду.
Крім того, для кожної нової задачі бажано створювати нову тему і приводити повністю умову.

8

Re: Алгоритм прямого пошуку підпослідовності.

a = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2),
b = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2)
2Користуючись методом Кнута – Моріса – Пратта (КМП) пошуку підпослідовності у послідовності, встановити входження деякого образу у базовий рядок. Якщо співпадання має місце, то вказати порядковий індекс елемента в базі, починаючи з якого образ повністю співпадає з елементами бази, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.
Користуючись методом Боуера – Мура (БМ) пошуку підпослідовності у послідовності, встановити входження деякого образу у базовий рядок. Якщо співпадання має місце, то вказати порядковий індекс елемента в базі, починаючи з якого образ повністю співпадає з елементами бази, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.
Повна умова.

9

Re: Алгоритм прямого пошуку підпослідовності.

В Вікіпедії непогано описані обидва алгоритма: Алгоритм Кнута—Моріса—Прата, Алгоритм Бойера — Мура. Якщо виникнуть якісь конкретні проблеми - пишіть.
І усе ж таки бажано під кожну задачу створювати окрему тему.