Рис 13.16. Структура бінарного дерева
Як і для списків, основними процедурами обробки дерев є пошук, вставка і вилучення вузла дерева. Ці процедури ми розглянемо на прикладі, в якому сортування послідовності реалізована за допомогою побудови і наступної обробки бінарного дерева.
Приклад 13.5: Нехай A = a1, a2,..., ,an - послідовність цілих чисел. Для того, щоб відсортувати послідовність А, що складається з елементів ai
а) побудуємо бінарне дерево, що задовольняє наступній властивості: для будь-якого вузла дерева 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*log2n) порівнянь. Однак у гіршому випадку (якщо, наприклад, вихідний список упорядкований), для вставки кожного наступного вузла алгоритм буде слідувати по одній і тій же гілці (наприклад, лівій). Тому алгоритм витрачає O(n2) порівнянь, тобто не є ефективним. Однак його можна модифікувати таким чином, щоб процедура TreeBild будувала т.н. збалансоване дерево. Тоді алгоритм сортування стане ефективним.
13.8. Задачі
1.Клас арифметичних виразів, який містить однобуквені змінні, операції +, -, *, / і круглі дужки, назвемо класом найпростіших виразів. Реалізувати:
процедуру побудови дерева найпростішого арифметичного виразу, який заданий у виді рядка.
процедуру обчислення значення найпростішого арифметичного виразу, який заданий деревом при значеннях змінних, що вводяться з клавіатури.
процедуру перетворення дерева в рядок.
2. У параграфі 9, алгоритм пірамідального сортування, викладений метод представлення масиву в виді бінарного дерева. Реалізувати процедуру побудови цього дерева по масиву V[1..n].
3. Книга складається з 3-розділів. Кожний розділ містить 3 параграфа, а кожний параграф - 3 пункти. Всі вказані структурні частини книги мають назви. Реалізувати :
– процедуру побудови змісту книги в виді тернарного дерева;
– діалогову процедуру пошуку назви кожної частини книги за її номером;
– виведення змісту на екран за допомогою різних обходів;
– пошук розділу по його назві.
4. Реалізувати процедури порівняння двох однотипних бінарних дерев T1 і T2 на рівність (T1 = T2) і вкладення (T1 £ T2), використовуючи наступні рекурсивні визначення:
Через root(T) позначимо корінь дерева T. Тоді
T1 = T2, якщо root(T1) = root(T2) і L(root(T1)) = L(root(T2)), R(root(T1)) = R(root(T2))
T1 £ T2, якщо root(T1)=root(T2) або T1=Nil і L(root(T1))£ L(root(T2)), R(root(T1))£ R(root(T2))
5. Реалізувати процедуру пошуку в дереві T1 піддерева, який дорівнює T2. Використати процедуру порівняння з попередньої задачі.
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) матриці коефіцієнтів системи
x1
| x2
| . . .
| xn
| Вільний член
|
a11
| a12
| . . .
| a1n
| b1
|
a21
| a22
| . . .
| a2n
| b2
|
. . .
. . .
| . . .
. . .
| . . .
. . .
| . . .
. . .
| . . .
. . .
|
an1
| an2
| . . .
| ann
| bn
|
Оскільки параметр 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 {прямий хід метода Гауса}
- вибір рівняння, що містить ненульовий коефіцієнт при Xi в якості ведучого;
- перестановка місцями i-того і ведучого;
For j := 1 to n do
If i <> j
then - вилучення Xi з j-того рівняння
end;
For i := n downto 1 do {обернений хід метода Гауса}
- обчислення Xi;
End;
Procedure SolOut(Y: Solution);
Var
i: Integer;
Begin {виведення розв’язку Y}
For i := 1 to n do {Виведення i-тої компоненти розв’язку}
Writeln(' Задача розв’язана ')
End;
Наступне уточнення структури даних складається у визначенні типу Monom. Якщо ми вирішимо продовжити тактику економії пам’яті, можна не зберігати члени рівняння виду Aij*Xi при Aij = 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;
{вилучення Xi з рівнянь системи}
{1. нормалізація ведучого рівняння}
{2. вилучення Xi з верхньої частини системи}
{3. вилучення Xi з нижньої частини системи}
P := P^.NextEqu;
end;
Y := A;
End;
Для вибору ведучого рівняння використовується послідовний перегляд рівнянь системи за допомогою посилань Q. Єдиний розв’язок системи гарантує існування ведучого рівняння – рівняння з ненульовим коефіцієнтом при Xi.
Перестановка рівнянь здійснюється перенаціленням посилань P^.LS_Mem і Q^.LS_Mem.
Основна частина алгоритму – вилучення невідомого Xi. Вона складається з кроків 1, 2, 3, що виконуються послідовно.
Крок 1 – нормалізація ведучого рівняння, тобто ділення всіх членів рівняння на коефіцієнт при Xi.
Крок 2 - вилучення Xi з верхньої частини системи. j-те рівняння верхньої частини (j < i) має вид Xj + Aji1*Xi1 + ... + Ajik*Xik = Bj, причому i1 >= i оскільки воно нормалізовано і невідомі Xk, k < i, вилучені на попередніх кроках основного циклу. Тому вилучення здійснюється при i1 = i. Треба помножити ведуче рівняння на Aji1 і обчислити його з j-того рівняння.
Крок 3 - вилучення Xi з нижньої частини системи. j-те рівняння нижньої частини (j > i) має вид Aji1*Xi1 + ... + Ajik*Xik = Bj, причому i1 >= i. Вилучення здійснюється точно також, як і на кроку 2.
Кроки 2 і 3 настільки схожі, що природно було би реалізувати їх одною і тою ж процедурою. Для цього необхідно всього лише реалізувати однакове представлення рівнянь з нижньої і верхньої частин системи, тобто не зберігати у списку рівняння верхньої частини системи відповідний ведучий член Xj !
Таким чином, на виході кроку 1 – процедури нормалізації ми повинні отримати "хвіст" Aji1*Xi1 + ... + Ajik*Xik = Bj нормалізованого рівняння. Основна частина алгоритму буде виглядати так:
{вилучення Xi з рівнянь системи}
{нормалізація i-того рівняння й отримання "хвоста"}
EquNorm(P);
Q := A;
For j := 1 to n do begin
If i <> j
then If Q^.LS_Mem^.Unknown = i
{вилучення Xi з j-того рівняння}
then EquTrans(Q, P);
Q := Q^.NextEqu
end;
У нашій версії метода Гауса та його частина, яку називають зворотним ходом, об¢єднана з прямим ходом методу. Ми приводимо матрицю системи одразу до діагонального вигляду. Зазначимо, що структура даних виходу процедури SysSol змінилась: тепер i-тий член списку Y має вид <n + 1, значення Xi>. Процедура 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 елементарного перетворення лінійного рівняння E1 за допомогою ведучого рівняння E2.
E1 := E1 - C*E2
Якби рівняння були представлені масивами коефіцієнтів, це перетворення реалізувалось б за допомогою одного арифметичного циклу. У нашій же структурі даних необхідно реалізувати перетворення списків. Нехай рівняння мають вид
E1 = A1*X + T1, E2 = A2*Y + T2, де A1*X, A2*Y - перші члени списків (голови), а T1 і T2 - хвости списків. Можливі наступні випадки:
Випадок 1. Невідомі X і Y однакові. Тоді:
Якщо A1 - C*A2 <> 0
то (A1*X + T1) - С*(A2*X + T2) = (A1-C*A2)*X + (T1 - C*T2)
інакше (A1*X + T1) - С*(A2*X + T2) = (T1 - C*T2)
Випадок 2. Номер X менше, ніж номер Y. Тоді:
(A1*X + T1) - С*(A2*X + T2) = A1*X + (T1 - C*E2)
Випадок 3. Номер X більше, ніж номер Y. Тоді:
(A1*X + T1) - С*(A2*X + T2) = (-C*A2)*Y + (E1 - C*T2)
У кожному з цих випадків права частина відповідного співвідношення - рівності є сума (голова + хвіст) результуючого рівняння, причому обчислення хвоста легко організувати за допомогою рекурсії і трохи складніше – ітерації. Ознака закінчення обчислень – вільні члени в головах списків і відсутність хвостів. Перед застосуванням описаного алгоритму (процедура 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 = 231 - 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. Заключне зауваження: переходимо до об’єктів
В другій частині книги ми будемо вивчати сучасні методи програмування великих за розміром програмних систем. Ми побачимо, як уточнюються наші уявлення про ті ієрархії структур даних, які потрібно застосовувати в програмах.