Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:

Error. Page cannot be displayed. Please contact your service provider for more details. (16)


Проверка на вхождение в качестве подпоследовательности

Поиск:
(1 вариант) Будем сводить задачу к задаче меньшего размера.

  
Код

n1:=n;
  k1:=k;
  {инвариант:  искомый ответ <=> возможность из x[1]..x[n1] по-
   лучить y[1]..y[k1] }
  while (n1 > 0) and (k1 > 0) do begin
  | if x[n1] = y[k1] then begin
  | | n1 := n1 - 1;
  | | k1 := k1 - 1;
  | end else begin
  | | n1 := n1 - 1;
  | end;
  end;
  {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1 <>  0
   (и n1 = 0), то ответ - нет}
  answer := (k1 = 0);


Мы использовали то, что если x[n1] = y[k1] и y[1]..y[k1] - подпоследовательность x[1]..x[n1], то y[1]..y[k1-1] - подпоследовательность x[1]..x[n1-1].

(2 вариант) Функция x[1]..x[n1] |-< (максимальное k1, для которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) индуктивна.
Сайт: manual.ru






Просмотров: 1798

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную