Метод динамічного програмування для задачі пошуку найбільших спільних послідовностей

курсова робота з інформатики

ЗМІСТ

Вступ

Мова програмування Pascal була розроблена в 1968-1971 рр. Ніклаусом Віртом в Цюріхському Інституті інформатики (Швейцарія), і названа на честь Блеза Паскаля – видатного математика, філософа і фізика 17-го століття. Первинна мета розробки мови диктувалася необхідністю створення інструменту "для навчання програмуванню як систематичній дисципліні". Проте дуже скоро виявилася надзвичайна ефективність мови Pascal в найрізноманітніших додатках, від вирішення невеликих задач чисельного характеру до розробки складних програмних систем – компіляторів, баз даних, операційних систем і т.п. До теперішнього часу Pascal належить до групи найбільш поширених і популярних у світі мов програмування:

При рішенні практично будь-яких задач автоматизації і моделювання постає проблема отримання, збереження (накопичення) і представлення інформації, властивій вирішуваній задачі. Наприклад, при автоматизації бухгалтерського обліку інформація про переміщення грошових коштів та інших активів підприємства за деякий період часу повинна зберігатися яким-небудь чином і бути доступна для перегляду бухгалтеру або директору підприємства, а також піддаватися обробці автоматизуючою програмою з метою складання звітної документації.

Об'єм інформації в таких системах наперед невідомий, що викликає певні труднощі при описі структур даних в програмі.

Всі глобальні змінні і типізовані константи розміщуються в одній безперервній області оперативної пам'яті, яка називається сегментом даних. Довжина сегменту визначається архітектурою процесора 8086 і складає 64 Кілобайт (65536 байт), що може викликати певні труднощі при описі і обробці великих масивів даних.

З другого боку об'єм стандартної пам'яті – 640 Кілобайт. Вихід – використовувати динамічну пам'ять.

Динамічна пам'ять – це оперативна пам'ять ЕОМ, що надається Турбо-Паскалевій програмі при її роботі, за вирахуванням сегменту даних (64 К), стека (звичайно 16 К) і власне тіла програми.

За умовчанням розмір динамічної пам'яті визначається всією доступною пам'яттю ЕОМ і, як правило, складає не менше 200-300 Кбайт.

Динамічну пам'ять звичайно використовують при:

1. обробці великих масивів даних;

2. розробці САПР;

3. тимчасовому запам'ятовуванні даних при роботі з графічними і звуковими засобами ЕОМ.

Розміщення статичних змінних в пам'яті здійснюється компілятором в процесі компіляції.

Динамічні змінні – розміщуються в пам'яті безпосередньо в процесі роботи програми.

При динамічному розміщенні наперед невідомі ні тип, ні кількість розміщуваних даних, до них не можна звертатися по іменах, як до статичних змінних. Турбо-Паскаль представляє засіб управління динамічною пам'яттю: покажчики.

Розділ 1. Динамічні структури даних

Структури даних, які не змінюють свого розміру протягом усього часу існування, називають статичними. Так регулярні і комбіновані типи мови Паскаль визначають статичні дані. Розмір статичних даних можна завжди визначити за описами цих даних, розміщеними в розділі опису типів або в розділі опису змінних. На відміну від статичних даних, дані динамічної структури змінюють свої розміри в процесі виконання програми. Може трапитись, що наперед не відомий не тільки розмір деякого об'єкта, а взагалі чи цей об'єкт буде. Дані, які виникають уже в процесі виконання програми або ж їхній розмір під час виконання програми змінюється, називають динамічними.

Розглянемо таку задачу. В деякому тексті треба визначити перше слово, яке має певні властивості: довжину більшу, ніж п'ять символів, і починається з букви г. Зрозуміло, що такого слова може взагалі не бути, тоді для розміщення його не потрібно виділяти пам'ять. А якщо таке слово і є, то наперед не відома його довжина. Звичайно, у такому випадку можна обійтися і статичними структурами даних. Тут на початку програми доцільно зарезервувати пам'ять під масив символів завдовжки з максимальний розмір слова. Однак такий підхід призводить до нераціонального використання пам'яті комп'ютера.

1.1. Вказівний тип

У мові Паскаль для роботи з динамічними об'єктами передбачено спеціальний тип значень – вказівний. Це такий же простий тип, якими є цілий, дійсний, логічний. Однак для нього в мові не зарезервовано жодного стандартного ідентифікатора. Загальний вигляд опису вказівного типу такий:

type

<ім'я_вкaзiвнoгo_типy>=^<iм'я_типy>

Значенням вказівного типу є вказівка на деякий програмний об'єкт – дина-мі-чну структуру даних, за якою відбувається доступ до цього об'єкта. Після стрі-л-ки "^" зазначають тип цього динамічного об'єкта. Важливо пам'ятати, що цей тип можна задавати тільки за допомогою імені типу – стандартного чи попередньо описаного, однак у жодному разі не за допомогою безпосереднього задания типу.

Наведемо приклад опису змінних вказівного типу:

type

vect=array [1.. 10] of char;

mas^vect;

var p: ^real;

q: ^integer;

m: mas;

За допомогою наведених вище описів уведено три змінні вказівного типу: p, q і m. Для однієї з них (m) тип заданий явно, для двох інших – неявно. Згідно з цими описами значення змінної р в програмі буде вказівкою на деякий динамічний об'єкт дійсного типу, значення q – на динамічний об'єкт цілого типу, а значення т – вказівкою на динамічний об'єкт, що є масивом з 10-ти літер. Читати наведені вище описи треба так:

"Тип mas є вказівкою на vect", "Змінна p є вказівкою на дійсну змінну" тощо. Про те, що описуваний об'єкт є вказівного типу, свідчить стрілка "^" в описі цього типу. Значення кожної із змінних вказівного типу визначають місце в пам'яті відповідного динамічного об'єкта.

Схематично зв'язок вказівника (значення вказівної змінної) і об'єкта, на який він вказує, показаний на рис. 1.

Рис. . Зв'язок вказівника з динамічним об'єктом

Іноді потрібно мати вказівник, що не вказує на жодний об'єкт,