L(v) R(v)

Рис 13.16. Структура бінарного дерева

Як і для списків, основними процедурами обробки дерев є пошук, вставка і вилучення вузла дерева. Ці процедури ми розглянемо на прикладі, в якому сортування послідовності реалізована за допомогою побудови і наступної обробки бінарного дерева.

Приклад 13.5: Нехай A = a₁, a₂,..., ,a_n - послідовність цілих чисел. Для того, щоб відсортувати послідовність А, що складається з елементів a_i

а) побудуємо бінарне дерево, що задовольняє наступній властивості: для будь-якого вузла дерева v будь-який елемент L(v) £ v £ будь-який елемент R(v)

б) побудуємо послідовність із вузлів дерева, в якій елементи розташовані у відповідності з цим же принципом: послідовність {L(v)}, v, послідовність {R(v)}.

Легко бачити, що вихідна послідовність буде впорядкованою.

Розв’язок.

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

· побудови списку з чисел, що вводяться з клавіатури;

· побудови дерева, що задовольняє властивості п. а);

· побудови списку, що задовольняє властивості п. б);

· виведення списку.

Типи елементів динамічних структур даних задачі:

Type

Point = ^ Item;

Item = Record

Key: Integer;

Next: Point

End;

Link = ^ Vertex;

Vertex = Record

Key: Integer;

Left, Right: Link;

End;

Програма розв’язку задачі:

Program ListSort;

{описання типів даних}

Var

A, B: Point;

LastB: Point; {кінець списку B}

Tree: Link;

{описання процедур}

{процедура введення списку}

{процедура побудови дерева з списку}

{процедура побудови списку з дерева}

{процедура виведення списку}

Begin {розділ операторів}

InpList(A); {процедура введення списку}

Tree := Nil;

TreeBild(Tree, A); {процедура побудови дерева Tree з списку A}

B := Nil;

ListBild(Tree, B); {процедура побудови списку B з дерева Tree}

OutList(B); {процедура виведення списку}

End. {кінець програми}

Procedure InpList(var P: Point); {процедура введення списку}

Var

Ch: Char;

Q: Point;

Begin

P := Nil; {порожній список}

Writeln('Для введення числа нажміть y');

ch := Readkey;

While ch = 'y' do begin

New(Q); {формування нового елемента списку}

Writeln('Input Item:');

Read(Q^.Key);

Q^.Next := P; {включення нового елемента в список}

P := Q; {покажчик списку - на початок списку}

Writeln('Продовжити введення? Y/N ');

ch:= Readkey

end

End;

{процедура побудови дерева з списку}

Procedure TreeBild(var T: Link; P: Point);

Var

x: Integer;

Procedure Find_Ins(var Q: Link; x: Integer);

Procedure Ins(var S: Link);

Begin {процедури вставки елемента}

New(S);

S^.Key := x;

S^.Left := Nil;

S^.Right := Nil

End; {процедури вставки елемента}

Begin {процедур пошуку і вставки елемента}

x := P^.Key;

If Q = Nil

then Ins(Q)

else if x < Q^.Key

then Find_Ins(Q^.Left, x)

else Find_Ins(Q^.Right, x)

End; {процедури пошуку і вставки елемента}

Begin {процедури побудови дерева з списку}

If P <> Nil

then begin

Find_Ins(T, P^.Key);

TreeBild(T, P^.Next)

end

End; {процедури побудови дерева з списку}

Зауважимо, що передача посилань на вершини структур, що оброблюються, здійснюється через параметри-змінні. Це дозволяє породжувати вузли дерева без використання додаткових покажчиків.

{процедура побудови списку з дерева}

Procedure ListBild(var T: Link; var F: Point);

Var

Temp: Point;

Begin

If T <> Nil

then begin

ListBild(T^.Left, F);

New(Temp); {породження нового елемента}

Temp^.Key := T^.Key;

Temp^.Next := Nil;

If F = Nil

then begin

F := Temp;

LastB := Temp

end

else begin

LastB^.Next := Temp;

LastB := Temp

end;

{змінна LastB - покажчик на останній елемент списку, що будується}

ListBild(T^.Right, LastB^.Next)

end

End; {процедури побудови списку з дерева}

Procedure OutList(var P: Point); {процедура виведення списку}

Var

x: Integer;

Begin

If P <> Nil

then begin

Write(P^.Key, ' ');

OutList(P^.Next)

end

End; {процедури виведення списку}

{процедура виведення дерева - використовувалась при налагодженні}

Procedure OutTree(var T: Link);

Begin

If T <> Nil

then begin

OutTree(T^.Left); {ліве піддерево}

Write('V = ', T^.Key); {корінь дерева}

OutTree(T^.Right); {праве піддерево}

end

End; {процедури виведення дерева}

У процедурах ListBild і OutTree використаний загальний принцип обробки дерева – так званий обхід дерева зліва - направо:

L(v) - обробка лівого піддерева;

v - обробка кореня;

R(v) - обробка правого піддерева.

Обробка L(v) і R(v) реалізована як рекурсивний виклик процедури обробки дерева. Крім обходу зліва направо, в задачах використовуються також і інші порядки переліку вузлів. Для бінарних дерев це:

L(v) - v - R(v) - зліва направо;

R(v) - v - L(v) - справа наліво;

v - L(v) - R(v) - зверху вниз;

L(v) - R(v) - v - знизу вверх.

Якщо в процедурі ListBild застосувати обхід справа наліво, елементи списку B будуть упорядкованими за зменшенням. У процедурі Find_Ins по суті застосований обхід зверху донизу у модифікації: v - L(v) або R(v) (у залежності від результату порівняння x < Q^.Key).

Якщо в виді дерева представлено арифметичний вираз (приклад 13.1), процедуру обчислення його значення треба програмувати обходом знизу-вгору: обчислити значення лівого операнду правого операнду результат бінарної операції. Неважко побачити, що якщо при побудові дерева Tree будь-яке ліве піддерево буде містити стільки же вузлів, скільки і відповідне праве, для його побудови треба O(n*log₂n) порівнянь. Однак у гіршому випадку (якщо, наприклад, вихідний список упорядкований), для вставки кожного наступного вузла алгоритм буде слідувати по одній і тій же гілці (наприклад, лівій). Тому алгоритм витрачає O(n²) порівнянь, тобто не є ефективним. Однак його можна модифікувати таким чином, щоб процедура TreeBild будувала т.н. збалансоване дерево. Тоді алгоритм сортування стане ефективним.

13.8. Задачі

1.Клас арифметичних виразів, який містить однобуквені змінні, операції +, -, *, / і круглі дужки, назвемо класом найпростіших виразів. Реалізувати:

процедуру побудови дерева найпростішого арифметичного виразу, який заданий у виді рядка.

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

процедуру перетворення дерева в рядок.

2. У параграфі 9, алгоритм пірамідального сортування, викладений метод представлення масиву в виді бінарного дерева. Реалізувати процедуру побудови цього дерева по масиву V[1..n].

3. Книга складається з 3-розділів. Кожний розділ містить 3 параграфа, а кожний параграф - 3 пункти. Всі вказані структурні частини книги мають назви. Реалізувати :

– процедуру побудови змісту книги в виді тернарного дерева;

– діалогову процедуру пошуку назви кожної частини книги за її номером;

– виведення змісту на екран за допомогою різних обходів;

– пошук розділу по його назві.

4. Реалізувати процедури порівняння двох однотипних бінарних дерев T₁ і T₂ на рівність (T₁ = T₂) і вкладення (T₁ £ T₂), використовуючи наступні рекурсивні визначення:

Через root(T) позначимо корінь дерева T. Тоді

T₁ = T₂, якщо root(T₁) = root(T₂) і L(root(T₁)) = L(root(T₂)), R(root(T₁)) = R(root(T₂))

T₁ £ T₂, якщо root(T₁)=root(T₂) або T₁=Nil і L(root(T₁))£ L(root(T₂)), R(root(T₁))£ R(root(T₂))

5. Реалізувати процедуру пошуку в дереві T₁ піддерева, який дорівнює T₂. Використати проце­дуру порівняння з попередньої задачі.

6. Реалізувати процедури, які ілюструють графічно:

побудову бінарного дерева;

пошук вузла з даним ключем різними обходами.

14. МЕТОДОЛОГІЯ СТРУКТУРНОГО ПРОГРАМУВАННЯ: ПІДСУМКИ

З виникненням мов високого рівня (кінець 50-х років) з’явилась можливість проектування великих програмних систем. Програмування з мистецтва комбінування машинних команд, таємницями якого володіли вибрані, перетворилося в індустрію виробництва програмного обладнання ЕОМ. До початку 70-их років витрати на виробництво програм перевищували витрати на виробництво апаратури. Тому проблема розробки ефективних і надійних програмних систем стала центральною задачею інформатики. Використання мов високого рівня зняло лише частину проблем (таких, наприклад, як проблема розподілу обчислювальних ресурсів), породивши одночасно нові проблеми (наприклад, у зв’язку з неефективністю машинного коду, що генерується транслятором у порівнянні з кодом “ручної роботи”, виникла задача оптимізації). Дослідження цих проблем привели, зокрема, до формування науково-обґрунтованого стилю програмування – структурного програмування.

Структурне програмування – це технологія проектування програм, яка базується на суворому визначенні засобів мови і методів їх використання. До засобів мови відносяться стандартні типи даних і оператори управління обчисленнями.

14.1. Основні структури управління

Розглянемо алгоритми розв’язку трьох задач, що відносяться до різних предметних областей:

а) Алгоритм Евкліда:

Program Evclid;

Var

a, b, u, v, w: Integer;

Begin

Read(a,b);

u := a;

v := b;

While u <> v do begin

w := u - v;

If w > 0

then u := w

else v := -w;

end;

Write(u)

end.

б) Наближений розв’язок рівняння методом ділення навпіл:

Program EquationSol;

Const

Eps = 1e-4;

Var

a, b, u, v, w: Real;

Begin

Read(a, b);

u := a;

v := b;

While u - v >= Eps do begin

w := (u + v)/2;

If f(u)*f(w) > 0

then u := w

else v := w;

end;

Write(u)

End.

в) Розподіл масиву на два масиви за бар’єрним елементом 0:

Program Partition ;

Const

n = 16;

Var

f, g, h : array [1..n] of Integer;

x, b: Integer;

i, j, k: Integer;

Begin

{ введення масиву f }

i := 1;

j := 1;

k := 1;

While f[i] <> 0 do begin

x := f[i];

If x > 0

then begin

g[j] := x;

j := j + 1;

i := i + 1

end

else begin

h[k] := x;

k := k + 1;

i := i + 1

end;

end;

Write(j, k)

End.

Програма Еvclid працює з цілими числами. Предметна область програми EquationSol – область дійсних чисел. Третя програма – Partition – оброблює масиви, причому тип компонент масиву не має суттєвого значення. Не зважаючи на різницю в предметних областях, між цими програмами існує схожість, що грає велику роль для розуміння суті програмування. Насправді, розділ операторів кожної з цих програм може бути описаний так:

Begin

< процедура введення >;

< послідовність простих операторів >;

while <умова> do begin

<оператор>;

if <умова>

then < оператор >

else < оператор > ;

end;

< процедура виведення >

End.

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

Рис 14.1. Блок-схема – структура управління програми.

Те загальне, що об’єднує розглянуті програми, називають структурою управління. Структура управління програми грає роль її несучої конструкції, скелета. Зрозуміло, що правильне проектування програми неможливе без правильної побудови її структури управління.

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

Основні структури управління ми розглядали в п. 1.13.

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

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

Основний результат можна тепер сформулювати наступним чином:

Управління будь-якого алгоритму може бути реалізовано у вигляді комбінації основних структур управління.

У реальних мовах структурного програмування застосовують і інші управляючі структури, кожна з яких може бути віднесена до одного з трьох основних типів. Наприклад, у мові Pascal розгалуження – умовний оператор, короткий умовний оператор, оператор варіанта; повторення – оператор циклу з параметром, оператор циклу з передумовою, оператор циклу з постумовою. Наявність додаткових структур управління породжує надлишковість у виразних можливостях мови, що дозволяє робити програми більш природними.

Відмітимо, що оператор переходу Goto не включений ні в список основних, ні додаткових операторів управління. Це – не випадковість. Безконтрольне застосування цього оператора приводить до того, що програма втрачає властивості, що вказані вище. Тому структурне програмування часто називають програмуванням без Goto.

14.2. Основні структури даних

Продовжимо аналіз прикладів, що приведені на початку параграфа. Звернемо увагу на сукупності даних, з якими працюють ці програми. Дані визначені в розділах типів, змінних і констант:

Program Evclid;

Var

a, b, u, v, w: Integer;

Program EquationSol;

Const

Eps = 1e-4;

Var

a, b, u, v, w: Real;

Program Partition ;

Const

n = 16;

Var

f, g, h : array [1..n] of Integer;

x, b: Integer;

i, j, k: Integer;

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

Методи побудови структур даних подібні методах утворення структур управління. Саме, існують основні (стандартні) структури, кожна з яких визначає один із засобів об’єднання даних у структуру. Дані простих типів при цьому грають роль цеглинок, з яких будується весь будинок.

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

Прості дані: цілі числа, дійсні числа, символи, логічні значення, дані - імена.

Засоби структурування даних: масиви, записи, файли, множини, посилання.

Наприклад, визначення типів

Word = Array [1..20] of Char;

Man = Record

Name: Word;

Age: Integer

end;

Notebook = array [1..n] of Man;

означає масив із записів, перше поле яких – масив із двадцяти символів, а друге – ціле число.

Необхідно розуміти, що зв’язок “дані-управління” полягає не тільки і не стільки у схожості правил їх побудови, скільки в орієнтації структур управління на обробку структур даних. Оператор присвоювання використовує дані простих типів. Логічні дані застосовують для визначення умов. Скалярні типи, що визначаються програмістом, використовують для описання даних-індексів у масивах і селектора варіанта в операторі вибору. Для обробки масивів зручно користуватись оператором циклу з параметром, а для обробки файлів – операторами While і Repeat. Записи з варіантами потрібно оброблювати операторами варіанта. Посилальні (динамічні) структури потрібно оброблювати рекурсивно. Цей список можна продовжити.

14.3. Методологія програмування “зверху-вниз”

Застосування у програмуванні концепції структур даних і управління потребує специфічної методології процесу розробки програм. Цей підхід називають, як ми вже відзначали, методом покрокового уточнення або програмуванням “зверху-вниз”. Суть метода – у наступному:

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

· уточнює структуру програми;

· уточнює структуру даних.

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

2. Уточнення структури даних складається у визначенні й описанні даних, що оброблюються вибраним оператором.

3. Визначення структури даних програми починається з описання входу-виходу, тобто з визначення структури початкових і вихідних даних.

4. При роботі користуються принципом мінімальної необхідності: уточнення здійснюють лише з тим ступенем точності, яка необхідна на даному кроці.

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

6. Основними структурними одиницями програми є процедури і функції. Кожну відносно самостійну підзадачу оформлюють як підпрограму (процедуру або функцію).

14.4. Приклад: Система лінійних рівнянь

Задача: Реалізувати процедуру розв’язання системи лінійних рівнянь, що отримана в процесі застосування метода невизначених коефіцієнтів до задачі обчислення невизначеного інтеграла від раціонального виразу.

Розв’язок: Стислість формулювання задачі обманлива: у ній скриті ті обмеження, які роблять цю постановку точною. Для уточнення задачі необхідно по-перше, указати поле коефіцієнтів системи рівнянь, по-друге – уточнити поняття розв’язку системи у термінах точне - наближене. Розглянемо два варіанта уточнення задачі:

Варіант 1. Поле коефіцієнтів – поле раціональних чисел. Елемент цього поля – або ціле число А, або дріб, що не скорочується, виду А/В, де знаменник В – натуральне число, а чисельник А – ціле число. Треба знайти точний розв’язок системи.

Варіант 2. Поле коефіцієнтів – поле дійсних чисел. Елемент цього поля – число типу Real. Треба знайти наближений розв’язок системи з указаною точністю.

У нашому випадку мають місце наступні обмеження:

· Коефіцієнти рівнянь системи – раціональні числа;

· Необхідно отримати точний розв’язок системи у виді набору раціональних чисел;

· Завжди існує єдиний розв’язок системи;

· Кількість рівнянь системи і кількість невідомих співпадають.

На першому кроці уточнюємо задачу в виді:

Program LinearSystem;

Type

Solution = ...;

LinSys = ...;

Var

S: LinSys;

X: Solution;

n: Integer;

Procedure SysInp(var A: LinSys);

Begin

{введення системи рівнянь A}

End;

Procedure SysSol(A: LinSys; var Y: Solution);

Begin

{розв’язок Y системи рівнянь A}

End;

Procedure SolOut(Y: Solution);

Begin

{виведення розв’язка Y}

End;

Begin {основна програма}

SysInp(S);

SysSol(S, X);

SolOut(X)

End. {кінець програми LinearSystem}

На наступному кроці уточнення виникає проблема вибору метода розв’язання і уточнення структури даних задачі. Відомим точним методом розв’язання систем лінійних рівнянь є метод Гауса послідовного вилучення невідомих. Основні кроки метода – вибір ведучого рівняння і ведучого невідомого і вилучення ведучого невідомого з інших рівнянь систем. Посібники з лінійної алгебри рекомендують представляти дані у виді n*(n+1) матриці коефіцієнтів системи

Оскільки параметр n залежить від задачі, для представлення матриці А у виді двомірного масиву треба резервувати пам’ять під масив деякого найбільш можливого розміру Nmax, що приводить до неоправданих витрат оперативної пам’яті. Радикальне рішення полягає у використанні динамічних структур даних. Систему можна представити в виді списку рівнянь, а кожне рівняння – списком доданків (членів рівняння):

LinSys = ^LS_Item; {список рівнянь}

LS_Item = Record

LS_Mem : LinEqu;

NextEqu: LinSys

End;

LinEqu = ^EquItem; {список членів рівняння}

EquItem = Record

EquMem : Monom;

NextMem: LinEqu

End;

Компромісне рішення – динамічне резервування пам’яті під масив A:

LinSys = ^Array[1..Nmax, 1..Nmax] of Rational; {Rational - раціональні числа}

Виберемо радикальний шлях рішення і уточнимо процедури SysInp, SysSol, SolOut. Наш вибір визначає Solution як список раціональних чисел.

Procedure SysInp(var A: LinSys);

Var

i: Integer;

P: LinSys;

Begin {введення системи рівнянь A}

Read(n); S := Nil;

For i := 1 to n do begin

Nеw(P); P^.NextEqu := S; S := P;

{введення i-того рівняння - списку P^.LS_Mem}

end

End;

Procedure SysSol(A: LinSys; var Y: Solution);

Begin {розв’язок Y системи рівнянь A}

For i ;= 1 to n do begin {прямий хід метода Гауса}

- вибір рівняння, що містить ненульовий коефіцієнт при X_i в якості ведучого;

- перестановка місцями i-того і ведучого;

For j := 1 to n do

If i <> j

then - вилучення X_i з j-того рівняння

end;

For i := n downto 1 do {обернений хід метода Гауса}

- обчислення X_i;

End;

Procedure SolOut(Y: Solution);

Var

i: Integer;

Begin {виведення розв’язку Y}

For i := 1 to n do {Виведення i-тої компоненти розв’язку}

Writeln(' Задача розв’язана ')

End;

Наступне уточнення структури даних складається у визначенні типу Monom. Якщо ми вирішимо продовжити тактику економії пам’яті, можна не зберігати члени рівняння виду A_ij*X_i при A_ij = 0. У цьому випадку члени рівняння представляються парою

<коефіцієнт, номер невідомого >:

Monom = Record

Coef: Rational;

Unknown: Integer

End;

Для спрощення структури даних змінимо визначення типу EquItem, вилучивши тип Monom:

EquItem = Record

Coef: Rational;

Unknown: Integer;

NextMem: LinEqu

End;

Тепер процедуру введення рівняння реалізуємо як локальну в процедурі SysInp. Введення рівняння – це введення лівої і правої частин рівняння, відмежованих одна від одної введенням знака "=". Введення лівої частини – повторення введень членів рівняння, відмежованих один від одного введенням знака "+".

Procedure SysInp(var A: LinSys);

Var

i: Integer;

P: LinSys;

Procedure EquInp(Var E: LinEqu);

Var

Q: LinEqu;

Sign: Char;

Procedure MemInp(var R: LinEqu);

{ тіло процедури MemInp }

Begin

Writeln('Введення першого члена лівої частини');

MemInp(Q); E := Q;

Write('Натисни = або +');

Sign := ReadKey;

While Sign = '+' do begin

Writeln('Введення наступного члена рівняння);

MemInp(Q^.NextMem);

Q := Q^.NextMem;

Write('Натисни = або +');

Sign := ReadKey

end;

Writeln('Введення вільного члена рівняння);

MemInp(Q^.NextMem);

Q := Q^.NextMem;

Q^.NextMem := Nil

End;{процедури введення рівняння}

Begin {введення системи рівняння A}

Read(n);

S := Nil;

For i := 1 to n do begin

Nеw(P);

P^.NextEqu := S;

S := P;

EquInp(P^.LS_Mem}

end

End;

Розділ операторів процедури SysInp набув закінченого вигляду. Введення члена рівняння оформимо в виді процедури MemInp, означивши тип Rational, значеннями якого є раціональні числа.

Увага! Введення чисельного типу Rational означає необхідність реалізації набору процедур, що забезпечують роботу з раціональними числами. Оскільки тип Rational необхідний для розв’язків багатьох інших задач, його треба оформити як модуль RAT і активізувати в програмі директивою Uses. Принципи проектування модуля ми розглянемо нижче. Зараз нам знадобляться тільки імена процедур введення і виведення раціональних чисел – RatInp і RatPrint.

Procedure MemInp(var R: LinEqu);

Begin

New(R);

With R^ do begin

RatInp(Coef);

If Sign <> '='

then Read(UnkNown)

else UnkNown := n + 1

end

End;

Наш алгоритм розв’язання системи (процедура SysSol) перетворить список рівнянь у список пар виду <номер невідомого, значення невідомого >. Тому для виведення розв’язку системи немає необхідності формувати список X. Достатньо установити посилання X типу LinSys на S і вивести значення X у потрібному виді. Це значить, що тип Solution можна вилучити, зробивши відповідні зміни у заголовках процедур.

Procedure SysSol(A: LinSys; var Y: LinSys);

Procedure SolOut(Y: LinSys);

Уточнимо процедуру виведення розв’язку:

Procedure SolOut(Y: LinSys);

Var

i: Integer;

P: LinSys;

Begin {виведення розв’язку Y}

P := Y;

For i := 1 to n do begin

{Виведення i-тої компоненти розв’язку}

With P^, LS_Mem^ do begin

Writeln('X[',i,'] = ');

RatPrint(Coef)

end;

P := P^.NextEqu

end;

Writeln(' Задача розв’язана ')

End;

Ми завершили проектування процедур введення-виведення з точністю до засобів модуля RAT. Продовжимо уточнення основної процедури програми – процедури SysSol.

Procedure SysSol(A: LinSys; var Y:LinSys);

Var

P, Q: LinSys;

TempRef: LinEqu;

i: Integer;

Begin {розв’язок Y системи рівнянь A}

P := A;

For i := 1 to n do begin {прямий хід метода Гауса}

{вибір ведучого рівняння}

Q := P;

While Q^.LS_Mem^.Unknown <> i do

Q := Q^.NextEqu;

{перестановка місцями i-того і ведучого}

TempRef := P^.LS_Mem;

P^.LS_Mem := Q^.LS_Mem;

Q^.LS_Mem := TempRef;

{вилучення X_i з рівнянь системи}

{1. нормалізація ведучого рівняння}

{2. вилучення X_i з верхньої частини системи}

{3. вилучення X_i з нижньої частини системи}

P := P^.NextEqu;

end;

Y := A;

End;

Для вибору ведучого рівняння використовується послідовний перегляд рівнянь системи за допомогою посилань Q. Єдиний розв’язок системи гарантує існування ведучого рівняння – рівняння з ненульовим коефіцієнтом при X_i.

Перестановка рівнянь здійснюється перенаціленням посилань P^.LS_Mem і Q^.LS_Mem.

Основна частина алгоритму – вилучення невідомого X_i. Вона складається з кроків 1, 2, 3, що виконуються послідовно.

Крок 1 – нормалізація ведучого рівняння, тобто ділення всіх членів рівняння на коефіцієнт при X_i.

Крок 2 - вилучення X_i з верхньої частини системи. j-те рівняння верхньої частини (j < i) має вид X_j + A_ji1*X_i1 + ... + A_jik*X_ik = B_j, причому i1 >= i оскільки воно нормалізовано і невідомі X_k, k < i, вилучені на попередніх кроках основного циклу. Тому вилучення здійснюється при i1 = i. Треба помножити ведуче рівняння на A_ji1 і обчислити його з j-того рівняння.

Крок 3 - вилучення Xi з нижньої частини системи. j-те рівняння нижньої частини (j > i) має вид A_ji1*X_i1 + ... + A_jik*X_ik = B_j, причому i1 >= i. Вилучення здійснюється точно також, як і на кроку 2.

Кроки 2 і 3 настільки схожі, що природно було би реалізувати їх одною і тою ж процедурою. Для цього необхідно всього лише реалізувати однакове представлення рівнянь з нижньої і верхньої частин системи, тобто не зберігати у списку рівняння верхньої частини системи відповідний ведучий член X_j !

Таким чином, на виході кроку 1 – процедури нормалізації ми повинні отримати "хвіст" A_ji1*X_i1 + ... + A_jik*X_ik = B_j нормалізованого рівняння. Основна частина алгоритму буде виглядати так:

{вилучення X_i з рівнянь системи}

{нормалізація i-того рівняння й отримання "хвоста"}

EquNorm(P);

Q := A;

For j := 1 to n do begin

If i <> j

then If Q^.LS_Mem^.Unknown = i

{вилучення X_i з j-того рівняння}

then EquTrans(Q, P);

Q := Q^.NextEqu

end;

У нашій версії метода Гауса та його частина, яку називають зворотним ходом, об¢єднана з прямим ходом методу. Ми приводимо матрицю системи одразу до діагонального вигляду. Зазначимо, що структура даних виходу процедури SysSol змінилась: тепер i-тий член списку Y має вид <n + 1, значення X_i>. Процедура SysSol набула завершеного виду. Залишилось уточнити процедури EquNorm(P) і EquTrans(Q, P), які оброблюють окремі рівняння.

{нормалізація рівнянь і виділення "хвоста"}

Procedure EquNorm(var P: LinSys);

Var

LCoef: Rational;

TempRef: LinEqu;

Begin

TempRef := P^.LS_Mem;

New(LCoef);

LCoef^ := TempRef^.Coef^; {ведучий коефіцієнт }

{установка посилання на “хвіст” рівняння}

P^.LS_Mem := P^.LS_Mem^.NextMem;

Dispose(TempRef); {збирання сміття}

TempRef := P^.LS_Mem; {ініціалізація циклу}

Repeat

TempRef^.Coef := DivRat(TempRef^.Coef, LCoef);

TempRef := TempRef^.NextMem {наступний член}

until TempRef = Nil;

Dispose(LCoef)

End {процедури нормалізації};

Найбільш цікава з точки зору техніки програмування процедура EquTrans елементарного перетворення лінійного рівняння E₁ за допомогою ведучого рівняння E₂.

E₁ := E₁ - C*E₂

Якби рівняння були представлені масивами коефіцієнтів, це перетворення реалізу­валось б за допомогою одного арифметичного циклу. У нашій же структурі даних необхідно реалізувати перетворення списків. Нехай рівняння мають вид

E₁ = A₁*X + T₁, E₂ = A₂*Y + T₂, де A₁*X, A₂*Y - перші члени списків (голови), а T₁ і T₂ - хвости списків. Можливі наступні випадки:

Випадок 1. Невідомі X і Y однакові. Тоді:

Якщо A₁ - C*A₂ <> 0

то (A₁*X + T₁) - С*(A₂*X + T₂) = (A₁-C*A₂)*X + (T₁ - C*T₂)

інакше (A1*X + T₁) - С*(A₂*X + T₂) = (T₁ - C*T₂)

Випадок 2. Номер X менше, ніж номер Y. Тоді:

(A₁*X + T₁) - С*(A₂*X + T₂) = A₁*X + (T₁ - C*E₂)

Випадок 3. Номер X більше, ніж номер Y. Тоді:

(A₁*X + T₁) - С*(A₂*X + T₂) = (-C*A₂)*Y + (E₁ - C*T₂)

У кожному з цих випадків права частина відповідного співвідношення - рівності є сума (голова + хвіст) результуючого рівняння, причому обчислення хвоста легко організувати за допомогою рекурсії і трохи складніше – ітерації. Ознака закінчення обчислень – вільні члени в головах списків і відсутність хвостів. Перед застосуванням описаного алгоритму (процедура EquDiff) обчислюється множник С і з рівняння, що перетворюється, вилучається перший член. Всі обчислення супроводжуються “збиранням сміття” – звільненням пам’яті, що займається членами, які вилучаються.

Procedure EquTrans(var Q: LinSys; P: LinSys);

Var

LCoef: Rational;

CurP, CurQ: LinEqu;

Procedure EquDiff(var RefQ, RefP: LinEqu; C: Rational);

Var

NextP, NextQ: LinEqu;

NextC: Rational;

II ,JJ: Integer;

Finish: Boolean;

{Вилучення члена рівняння з нульовим коефіцієнтом}

Procedure MemDel(var RefQ: LinEqu);

Var

TempRef: LinEqu;

Begin

TempRef := RefQ^.NextMem;

RefQ^.NextMem := RefQ^.NextMem^.NextMem;

RefQ^.Coef := TempRef^.Coef;

RefQ^.Unknown := TempRef^.UnkNown;

Dispose(TempRef) {збирання сміття}

End {процедури вилучення члена рівняння};

{вставка члена рівняння}

Procedure MemInc(var RefQ, RefP: LinEqu; C: Rational);

Var

C0: Rational;

TempRef: LinEqu;

Begin

New(TempRef);

TempRef^.Coef := RefQ^.Coef;

RefQ^.Coef := MinusRat(MultRat(RefP^.Coef, C));

TempRef^.Unknown := RefQ^.UnkNown;

RefQ^.Unknown := RefP^.Unknown;

TempRef^.NextMem := RefQ^.NextMem;

RefQ^.NextMem := TempRef;

RefQ := TempRef

End {процедури вставки члена рівняння};

Begin

NextQ := RefQ; {покажчики на голову списку}

NextP := RefP;

Finish := False; {ознака закінчення обчислень}

Repeat

II := NextQ^.Unknown; {номера невідомих}

JJ := NextP^.Unknown;

{випадок 1 і випадок закінчення обчислень}

If II = JJ

then begin {обчислення коефіцієнта рівняння}

NextC := SubRat(NextQ^.Coef, MultRat(NextP^.Coef, C));

If II = n + 1

then begin {випадок закінчення обчислень}

NextQ^.Coef := NextC;

Finish := True end

else {випадок 1}

if NextC^.Num <> 0

then begin

NextQ^.Coef := NextC;

NextQ := NextQ^.NextMem;

NextP := NextP^.NextMem end

else begin

MemDel(NextQ);

NextP := NextP^.NextMem end

end

else if II < JJ

then {випадок 2}

NextQ := NextQ^.NextMem

else begin {випадок 3}

MemInc(NextQ, NextP, C);

NextP := NextP^.NextMem end

until Finish

End {процедури EquDiff перетворення рівняння};

Begin

{підготовка до виклику процедури EquDiff}

CurQ := Q^.LS_Mem;

CurP := P^.LS_Mem;

New(LCoef);

Lcoef^_:=_CurQ^.Coef^;

Q^.LS_Mem :=_Q^.LS_Mem^.NextMem;

Dispose(CurQ);

CurQ := Q^.LS_Mem;

EquDiff(CurQ, CurP, LCoef)

End {вилучення невідомого};

Проектування процедур обробки рівнянь завершено з точністю до процедур арифметичних дій із раціональними числами. Наступний етап – проектування процедур модуля RAT.

14.5. Проектування модулів. Модуль RAT

Модуль RAT містить всі засоби, що забезпечують застосування у програмах раціональних чисел. Сюди входять:

· описання типу Rational, констант типу Rational;

· процедури введення-виведення раціональних чисел;

· функції перетворення числових типів і типу Rational;

· функції арифметичних операцій і порівнянь раціональних чисел;

· засоби, що використовуються для реалізації вищевказаних процедур (внутрішні засоби модуля).

Проектування почнемо з визначення поняття раціонального числа. Раціональні числа – це дроби виду Num/Den, де Num – чисельник, а Den – знаменник. Для забезпечення коректності і єдності представлення раціонального числа у виді пари <Num, Den> (дробу Num/Den) нехай виконуються наступні обмеження:

Den > 0, НОД(Num, Den) = 1, Якщо Num = 0, то Den = 1

Таке представлення ми будемо називати канонічною формою. Дії над дробами природно і зручно реалізовувати у виді функцій. Але функції мови Pascal повертають скалярні значення. Тому представлення дробу у виді запису у цьому випадку непридатне. Для того, щоб обійти цю чисто лінгвістичну перешкоду, уточнимо тип Rational як посилання на запис:

Type

Rational = ^RatValue;

RatValue = Record

Num, {чисельник }

Den: LongInt {знаменник}

End;

{Тип LongInt - один із цілочисельних типів в TP-6. Множина значень визначена константою MaxLongInt = 2³¹ - 1.}

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

A / B = A div НСД(А, В) / В div НСД(А, В)

{------------НСД двох натуральних чисел-------------------------}

Function GCD(u, v: LongInt): LongInt;

Begin

While (u <> 0) and (v <> 0) do

If u > v

then u := u mod v

else v := v mod u;

If u = 0

then GCD := v

else GCD := u

End;

{------------канонізація раціонального числа--------------------}

Function CanRat(X: Rational): Rational;

Var

u, v, w: LongInt;

Begin

u := X^.Num;

v := X^.Den;

If v = 0

then CanRat := Nil {дріб із нульовим знаменником}

else begin

If v < 0 {знаменник > 0}

then begin

u := -u;

v := -v end;

w := GCD(Abs(u), v);

If w <> 1

then begin {скорочення чисельника і знаменника}

u := u div w;

v := v div w end;

New(R);

Z^.Num := u;

Z^.Den := v ;

CanRat := Z;

end

End;

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

{ВВЕДЕННЯ-ВИВЕДЕННЯ}

Procedure RatInp(var X: Rational); {Введення}

Var

Ch: Char;

Begin

New(X);

Write('введення чисельника '); Read(X^.Num);

Ch := ReadKey;

If Ch = '/'

then begin

Write('введення знаменника '); Read(X^.Den);

X := CanRat(X)

end

else X^.Den := 1

End;

Procedure RatPrint(X: Rational); {Виведення}

Begin

If X = Nil

then Write('Ділення на нуль')

else begin

Write(X^.Num);

If X^.Den <> 1

then begin Write('/'); Write(X^.Den) end;

end;

Writeln

End;

{АРИФМЕТИЧНІ ОПЕРАЦІЇ}

Function AddRat(X, Y: Rational): Rational; {Додавання}

Begin

New(Z);

Z^.Num := X^.Num*Y^.Den + X^.Den*Y^.Num;

Z^.Den := X^.Den*Y^.Den;

AddRat := CanRat(Z)

End;

Function SubRat(X, Y: Rational): Rational; {Віднімання}

Begin

New(Z);

Z^.Num := X^.Num*Y^.Den - X^.Den*Y^.Num;

Z^.Den := X^.Den*Y^.Den;

SubRat := CanRat(Z)

End;

Function MultRat(X, Y: Rational): Rational; {Множення}

Begin

New(Z);

Z^.Num := X^.Num*Y^.Num;

Z^.Den := X^.Den*Y^.Den;

MultRat := CanRat(Z)

End;

Function DivRat(X, Y: Rational): Rational; {Ділення}

Begin

If Y^.Num = 0

then DivRat := Nil

else begin

New(Z);

Z^.Num := X^.Num*Y^.Den;

Z^.Den := X^.Den*Y^.Num;

DivRat := CanRat(Z)

end

End;

Function MinusRat(X: Rational): Rational; {число з знаком мінус}

Begin

New(Z);

Z^.Num := -X^.Num;

Z^.Den := X^.Den;

MinusRat := Z

End;

{ПОРІВНЯННЯ}

Function EquRat(X, Y: Rational): Boolean; {Рівність}

Begin

EquRat := (X^.Num = Y^.Num) and (X^.Den = Y^.Den)

End;

Function GrtRat(X, Y: Rational): Boolean; {Порівняння на "більш"}

Begin

GrtRat := SubRat(X, Y)^.Num > 0

End;

{ПЕРЕТВОРЕННЯ ТИПІВ}

Function RatReal(X:Rational): Real; {Раціональні в дійсні}

Begin

RatReal := X^.Num/X^.Den

End;

Function IntRat(X: LongInt): Rational; {Ціле в раціональне}

Begin

New(Z);

Z^.Num := X; Z^.Den := 1;

IntRat := Z

End;

Кожна з функцій, що описані вище, реалізує одну з дій у відповідності з його математичним визначенням. Так, наприклад, додавання спирається на формулу

A/B + C/D = CanRat((A*D + B*C)/(B*D))

Оскільки модуль планується використовувати при програмуванні багатьох прикладних задач, особливу увагу треба приділити його оптимізації. З цією метою необхідно, в першу чергу, виділити і оптимізувати ключеві засоби модуля. У нашому прикладі це функції GCD і CanRat.

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

A/B + C/D = CanRat((A*D + B*C)/(B*D)); (*)

A/B + C/B = CanRat((A + C)/B);

A/B + C = (A + B*C)/B;

A + C/D = (A*D + C)/D

Функція AddRat, що реалізована у відповідності з цим визначенням, у середньому ефективніше, ніж описана у модулі.

14.6. Реалізація модуля

Поряд зі стандартними модулями можна застосовувати і власні модулі. Модуль містить: заголовок модуля, інтерфейсну частину, реалізаційну частину і ініціалізаційну частину.

Заголовок модуля має вид:

Unit < Ім’я модуля >.

Ім’я модуля повинно співпадати з іменем файла, що містить цей модуль.

Інтерфейсна частина має вид:

Interface

<

· Описання констант, міток, типів і змінних, що доступні для використання зовнішніми програмами;

· Заголовки процедур і функцій, що доступні для використання зовнішніми програмами;

· Uses-директиви з іменами модулів, що доступні для використання зовнішніми програмами.

>

Всі доступні ззовні засоби модуля повинні бути описані в інтерфейсі цього модуля.

Реалізаційна частина має вид:

Implementation

<

· Описання всіх засобів модуля, які скриті від зовнішніх програм;

· Uses-директиви з іменами модулів, що використовуються в цьому модулі і скриті від зовнішніх програм;

· Повні описання всіх процедур і функцій модуля.

>

Ініціалізаційна частина – розділ операторів модуля. Він виконується перед виконанням зовнішньої програми, що використовує модуль. У зовнішню програму модуль включається директивою Uses.

В якості приклада приведемо оформлення модуля RAT.

{заголовок модуля}

Unit RAT; {<RAT.pas>}

Uses CRT;

{інтерфейсна частина}

Interface

Type

Rational = ^RatValue;

RatValue = Record

Num, {чисельник }

Den: LongInt {знаменник}

End;

Procedure RatInp(var X: Rational);

Procedure RatPrint(X: Rational);

Function AddRat(X, Y: Rational): Rational;

Function SubRat(X, Y: Rational): Rational;

Function MultRat(X, Y: Rational): Rational;

Function DivRat(X, Y: Rational): Rational;

Function MinusRat(X: Rational): Rational;

Function EquRat(X, Y: Rational): Boolean;

Function GrtRat(X, Y: Rational): Boolean;

Function RatReal(X:Rational): Real;

Function IntRat(X: LongInt): Rational;

{реалізаційна частина}

Implementation

Var Z: Rational;

{повні описання всіх процедур і функцій модуля}

{Ініціалізаційна частина}

Begin

ClrScr;

Writeln(' Модуль Rat v.0.0 ')

End.

14.7. Висновки (модульне програмування)

Підведемо деякі висновки проектування програми LinearSystem. У процесі проектування "зверху-вниз" ми отримали чітко відокремлені за змістом чотири рівня програми: рівень системи, рівень рівняння, рівень члена рівняння, рівень коефіцієнтів. З точки зору управління обчисленнями це означає побудову ієрархії процедур:

{Процедури SysOut, EquOut, MemOut використовувались для відладки і в тексті не описані.}

Побудова програми як чотирьохрівневої ієрархії обумовлено ієрархією математичних абстракцій, що використовується в математичній теорії систем лінійних рівнянь:

Система -> Рівняння -> Член рівняння-> Коефіцієнт

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

Проектування модуля RAT представляє собою окрему задачу – задачу з іншої предметної області. Замінивши модуль RAT, наприклад, модулем COMPLEX, у якому реалізовані дії з комплексними числами, ми отримаємо програму розв’язання системи лінійних рівнянь з комплексними коефіцієнтами. З іншого боку, наявність модуля RAT дозволяє легко програмувати і інші задачі, які потребують дій з раціональними числами.

14.8. Заключне зауваження: переходимо до об’єктів

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