1. Вступ
Програма, написана на будь-якій мові програмування, є деякою описаною послідовністю операцій, котрі необхідно виконати з деякою сукупністю даних. В свою чергу будова конкретної обчислювальної машини і особливості трансляторів визначають внутрішнє представлення даних ( їх розміщення в пам’яті ЕОМ. Ці факти свідчать про те, що організація даних для обробки є важливим етапом розробки програмних продуктів, а проблема структур даних та алгоритмів роботи з ними є актуальною проблемою.
Для реалізації багатьох програм вибір структури даних є найважливішим рішенням, і коли вибір зроблено правильно, то розробка алгоритму програми значно спрощується. Для одних і тих самих даних різні структури будуть займати неоднаковий дисковий простір; ті самі операції з різними структурами даних створюють алгоритми різної ефективності. Тобто вибір алгоритмів та структур даних тісно взаємопов’язані і найчастіше поняття структури даних включає алгоритми роботи з даною структурою.
Важливим є кожен рівень представлення даних. Наприклад, обрана математична модель може не в цілому або не точно відображати властивості реальних об’єктів і існуючі між ними зв’язки. В свою чергу, синтаксис окремої алгоритмічної мови може значно обмежувати можливості опису логічної структури даних, або ж робить ці описи складними і громіздкими. Неможливим або неефективним виконання синтаксично (і семантично) правильної програми можуть зробити характеристики комп’ютера (малий об’єм пам’яті, низька швидкодія). Тому структури даних та їх внутрішнє представлення, а також зв’язки між ними є одним з важливих питань в програмуванні.
Ефективність роботи алгоритмів залежить не лише від структури даних, яка використовується, але й від того, як дана структура розміщена. Звичайно, оперуючи великими кількостями інформації, бажано щоб вона була певним чином відсортована. Для цього використовують різноманітні методи впорядкування, тобто сортування інформації.
Курсова робота присвячена дослідженню внутрішнього представлення даних в пам’яті ЕОМ, а також сортуванню методом вставки зі спадаючим приростом. Як доводилося вище, ці задачі не перестають бути актуальними у наш час.
2. Теоретична частина до задач
2.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера.
2.1.1. Логічні типи
У середовищі програмування TurboPascal логічні типи представлені такими типами як Boolean, ByteBool, WordBool, LongBool. Значення, які можуть набувати змінні логічного типу, позначаються вбудованими ідентифікаторами констант False і True. Логічні змінні не можуть набувати інших значень, крім False і True. Для змінних і констант логічного типу визначено наступні співвідношення:
False < True
Ord(False) = 0
Ord(True) = 1
Succ(False) = True
Pred(True) = False
У внутрішньому представленні змінні логічного типу мають певну надлишковість. У таблиці 1 наведено характеристики внутрішнього представлення логічних типів.
Таблиця 1. Вбудовані логічні типи даних

Ідентифікатор
Значенню FALSE відповідає
Значенню TRUE відповідає
Розмір пам’яті


Boolean
0

Довільне число відмінне від 0
1


ByteBool
0

1


WordBool
0 в 2-х байтах

2


LongBool
0 в 4-х байтах

4


Як видно з таблиці 1, якщо значення логічної змінної дорівнює TRUE, то в пам’яті зберігається довільне число відмінне від нуля, якщо ж логічна змінна набула значення FALSE, то у кожному байті, відведеному під зберігання змінної, записується значення 0.
2.1.2 Цілі типи
Середовище Turbo Pascal містить п’ять вбудованих цілочисельних типів:
Shortint
Integer
Longint
Byte
Word
Кожен із вище наведених типів має свою множину значень, які може набувати змінна даного типу. Ця множина залежить від внутрішнього представлення конкретного типу, тобто від кількості байт, що відводиться для зберігання змінної того чи іншого типу. У таблиці 2 подано розмір та діапазон представлення чисел цілих типів.
Всі без винятку числа цілих типів в пам’яті комп’ютера зберігаються побайтно у зворотному порядку. Додатні числа зберігаються у прямому, а від’ємні ( у доповняльному коді.
Інформацію про знак числа містить перший біт. Перший біт додатнього числа дорівнює 0, а від’ємного ( 1. Нуль завжди має знак "+", тобто перший біт нульового числа дорівнює 0.
Таблиця 2. Вбудовані цілочисельні типи

Назва
Ідентифікатор
Діапазон
Розмір

1
Коротке ціле зі знаком
ShortInt
-128 … 127
1 байт

2
Ціле зі знаком
Integer
-32768 … 32767
2 байти

3
Довге ціле зі знаком
LongInt
-2147483648 … 2147483647
4 байти

4
Коротке ціле без знаку
Byte
0 … 255
1 байт

5
Ціле без знаку
Word
0 … 65535
2 байти


2.1.3 Дійсні типи
До дійсного типу відноситься підмножина дійсних чисел, котрі можуть бути представлені в форматі з плаваючою комою з фіксованою кількістю цифр.
У середовищі програмування TurboPascal є п’ять вбудованих дійсних типів: Real, Single, Double, Extended і Comp. Дійсні типи відрізняються діапазоном представлення чисел, розміром пам’яті, а також точністю значень змінних цих типів. У таблиці 3 подано розмір та діапазон представлення чисел дійсних типів.
Таблиця 3. Вбудовані дійсні типи даних

Назва
Ідентифікатор
Діапазон
Розмір

1
Дійсне одинарної точності
Single

4 байти

2
Дійсний
Real

6 байт

3
Дійсний подвійної точності
Double

8 байт

4
Дійсне підвищеної точності
Extended

10 байт

5
Ціле в формі дійсного
Comp

8 байт


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


1 біт
8 біт
23 біта

Значення числа приймається за умовний нуль.
Примітка: У даній і наведених нижче схемах внутрішнього представлення дійсних чисел введено такі позначення: - знак числа (+ або -); - мантиса; - експонента.
Тип Real


e

1 біт
39 біт
8 біт

Значення числа приймається за умовний нуль.
Тип Double

e


1 біт
11 біт
52 біта

Значення числа приймається за умовний нуль.
Тип Extended

e
i


1 біт
15 біт
1 біт
63 біта

Значення числа приймається за умовний нуль. Бітове поле i дорівнює 0, якщо число є близьке до нуля, в протилежному випадку - 1.
Тип Comp



1 біт
63 біта

Число, представлене у даному форматі , де - двійкове доповнення 63 бітного значення (тобто число зберігається у доповняльному коді).
2.1.4. Символьний тип даних
Ідентифікатором даного типу у середовищі програмування TurboPascal є ідентифікатор char. Значеннями даного типу є множина символів таблиці ASCII. Кожному символу відповідає ціле число у діапазоні 0..255.
У пам’яті комп’ютера займають 1 беззнаковий байт. В цей байт записується ASCII-код символа.
2.1.5. Рядковий тип.
Значенням рядкового типу є послідовність символів з динамічним атрибутом довжини, який залежить від дійсної кількості символів у рядку при виконанні програми, і константним атрибутом розміру в діапазоні від 1 до 255.
Довжина рядкового типу дорівнює: максимальна довжина рядка +1 байт. Перший байт завжди містить біжучу довжину рядка, а наступні байти - символи рядка. Максимальна кількість символів у рядку - 255. Схематично рядковий тип можна зобразити так:

1
2
3
...
n

де - d - біжуча довжина рядка; - ASCII-коди символів, що входять у рядок.
2.1.6. Перелічуваний тип
Перелічуваний тип - це впорядкований набір ідентифікаторів, заданий шляхом їх перелічення. Опис перелічуваного типу складається зі списку його елементів, розділених комами. Цей список обмежується круглими дужками.
Якщо описана змінна перелічуваного типу, то в пам’яті комп’ютера під неї виділяється стільки байт пам’яті, скільки відводиться на відповідне ціле число, яке дорівнює кількості елементів у списку перелічуваного типу. Так, якщо елементів у списку до 256 - то відводиться 1 байт пам’яті; якщо більше 256, але менше 65356 - відводиться 2 байти і т.д.
Значенню змінної в пам’яті відповідає порядковий номер його (починаючи з нуля) у списку ідентифікаторів, що заданий при об’явленні типу.
2.1.7. Діапазонний (інтервальний) тип
Діапазонний тип уявляє собою інтервал значень деякого порядкового типу, який називається базовим. При описі діапазонного типу вказується найменше і найбільше значення, розділені "..".
В пам’яті виділяється стільки байт, скільки відводиться під типи даних, що відповідають найменшому і найбільшому значенню діапазону і в них записується значення змінної.
2.1.8. Тип масив
Масив - це однорідна складена структура даних статичної структури. Кожен компонент масиву характеризується своїм індексом. Допустимими типами індексів є всі порядкові типи, за винятком Longint та піддіапазонів цього ж типу. Для доступу до елементів масиву необхідно вказати ідентифікатор масиву з одним чи кількома індексами в дужках.
Розглянемо зберігання масивів у пам’яті комп’ютера. Він зберігається як неперервна послідовність змінних того типу, якого оголошені елементи масиву.
Розмір пам’яті, що відводиться для зберігання масиву, обчислюється за формулою:

Взагалі, масив в пам’яті - це набір послідовних байт, причому адреса -го елементу масиву визначається за формулою: ,
де - адреса першого елементу масиву; - кількість байт, яку займає один елемент масиву.
Елементи масиву з найменшим індексом зберігаються по найменшій адресі пам’яті. Багатовимірні масиви зберігаються так, що найбільш правий індекс збільшується першим.
2.1.9. Тип запис
Запис - це статична неоднорідна структура даних, яка складається з фіксованого числа компонентів, що називаються полями запису. На відміну від масиву, поля запису можуть бути різного типу. Завдяки цьому записи використовуються для створення таких структур даних, які не підтримуються мовою програмування.
Розглянемо збереження записів у пам’яті комп’ютера. Компоненти запису у пам’яті комп’ютера зберігаються як неперервна послідовність змінних тих типів, яких об’явлені компоненти запису. Всі компоненти запису зберігаються у послідовності їх описання. Перше поле зберігається по найменшій адресі. Якщо запис містить варіантні частини, то кожна варіантна частина починається з однієї і тієї ж адреси.
Схематично це буде виглядати так:
Тексти програм містяться в дерикторії programs.
2.2.Задача на сортування (сортуваня Шелла або сортування вставкою із спадаючим приростом).
Теоретичний вступ.
1959 рік н.е. Дональд Л. Шелл, який займався розробкою алгоритмів, придумав покращення до вже існуючого методу сортування – методу сортування простими вставками.
Сортування методом Шелла намагається покращити швидкість роботи за рахунок швидшого переміщення елементів, які знаходяться далеко від потрібних позицій. Тут застосовується переміщення таких елементів великими „скачками” через кілька елементів одночасно, зменшуючи розмір „скачків” і, в кінці-кінців, кінцева установка елементів в необхідній позиції виконується за допомогою класичного сортування методом вставок.
Сортування методом Шелла працює шляхом вставки відсортованих підмножин основного списку. Кожна підмножина формується за рахунок вибирання кожного h-ого елемента, починаючи з любої позиції в списку. В результаті дістанемо h підмножин, відсортованих методом вставок. Послідовність елементів в списку, яку ми дістали, називається відсортована по h. Потім значення h зменшується і знову виконується сортування. Н зменшуємо доти, поки воно не стане рівним 1. Після чого останній прохід буде звичайним сортуванням методом вставок.
Зміст цього методу полягає в тому, що сортування по h швидко переносить елементи в область, де вони мають знаходитися у відсортованому списку, а зменшення значення h дозволяє зменшувати розмір „скачків” і, в кінці-кінців, помістити елемент в потрібну позицію. Перед повільним переміщенням елементів ідуть великі „скачки”, які зводяться до простого сортування методом вставок, який практично не пересуває елементи.
В своїй першій праці Шелл запропонував значення 1, 2, 4, 8, 16, 32... (звичайно в зворотньому порядку), але з цими значеннями пов’язана одна проблема: до останнього проходу елементи з парними індексами ніколи не зрівнюються з елементами з непарними індексами. В результаті чого під час останнього проходу все ще виникнуть переміщення елементів на великі відстані.
Пройшло 10 років (1969 р.). Дональд Кнут запропонував свою послідовність 1, 4, 13, 40, 121 ... (в зворотньому порядку звичайно), яка була математично обгрунтована (hk-1= 3hk+1, ht=1 і t = log3n - 1),
Для списків середніх розмірів ця послідовність показує досить високі характеристики швидкодії (на основі емпіричних досліджень Кнут оцінив швидкодію для середнього випадку як О(n5/4), а для найгіршого випадку було доведено, що швидкість роботи рівна О(n3/2)) при неважкому методі обчислень значень самої послідовності. Ряди інших послідовностей дозволяють дістати кращі значення швидкості в роботі (хоча і не набагато), але вимагають попереднього вираховування значень послідовностей, оскільки використовувані формули досить важкі. Як приклад можна привести іншу найшвидшу послідовність на сьогоднішній день, розроблену Робертом Седжвіком: 1, 5, 19, 41, 109 ... (формується шляхом об’єднання двох послідовностей 9*4і-9*2і+1 для і > 0 і 4і-3*2і+1 для i>1). Відомо, що для цієї послідовності час роботи в найгіршому випадку визначається, як О(n4/3) при О(n7/6) для середнього випадку.
Аналіз цього алгоритму поставив багато важких математичних питань, які і по сьогоднішній день не вирішені. Зокрема, невідомо які послідовності дають найкращі результати. Але відомо одне, елементи не мають бути множниками один одного.
Що стосується стійкості, то при перестановці елементів, які сильно відрізняються один від одного, можливе порушення порядку розташування елементів з одинаковими значеннями. Відповідно, цей метод відноситься до нестійких. Даний метод відноситься до методів з економічним використанням пам’яті, бо пам’ять при сортуванні використовується в основному для представлення вхідної послідовності і залежить від типу знінних, якими представлені самі елементи вхідної послідовності, а сама программа якщо і використовує пам’ять, то тільки при перестановці двох елементів, що в загальному випадку при великі об’єми інформації і декількох інформаційних полях, одне з яких є ключовим призводить до майже непомітного збільшення файлу підкачки.
Специфіка вхідної послідовності полягає в типі змінних, що використовуються при представлені ключового поля. Це призводить до залежності кількості використаної пам’ять від типу змінних, що при великих об’ємах інформації суттєво помітно.

Конкретний приклад роботи методу сортування
Спочатку вибираємо послідовність чисел, які відповідають кроку для порівняння елементів в підмножині на кожному кроці сортування. Як вищезазначалось найкращими є 1, 4, 13, 40, 121 ... і 1, 5, 19, 41, 109 ... (в зворотньому порядку звичайно). Для конкретних ситуацій можна вибирати й інші послідовності.
При послідовності кроків для елементів 5, 2, 1, що випливають з формули (m+2) div 3 для 14 елементів сортування матиме 3 етапи. На першому етапі подається вхідна послідовність в якій будуть сортуватись елементи, що віддалені один від одного на 5 позицій. На другому етапі сортуватимуться елементи, відсортовані на попередньому етапі, що віддалені один від одного на 2 позиції. На останньому третьому етапі ще невідсортовані елементи сортуватимуться методом простої вставки:
І етап.

ІІ етап

ІІІ етап

Відсортована послідовність матиме вигляд:

Текст програми представлений у Додатку 3.2
2.3.Задача на пошук медіани списку
Медіаною послідовності з n елементів називається елемент, значення якого менше (або рівне) половині n елементів і більше (або рівне) другій половині.
Задачу пошуку медіани прийнято пов’язувати із сортуванням, так як медіану завжди можна знайти наступним чином: просортувати n елементів, а потім вибрати середній елемент.
Алгоритм винайдений К.Хоором працює наступним чином. Перш за все використовується операція розділення, вона використовується при швидкому сортуванні, з l=1, r=n, та з a[k], вибраним у якості розділюючого значення x. Отримані значення індексів i та j є такими, що
1) a[h]<=x для всіх
2) a[h]>=x для всіх
3) i>j;
Можливі такі три варіанти:
1. Розділююче значкння x було малим; в результаті границя між двома частинами менше за шукане значеня k. Процес потрібно повторити для елементів a[i],….,a[r].
l j i k r
2. Вибрана границя x була дуже великою. Операцію розбитть потрібно повторити на підмасиві a[l],…,a[j].
l k j i r
3. Значення k лежить в інтервалі j<k<i; елемент a[k] розділює масив у заданій пропорції і, відповідно, являється шуканим.


l j k i r

Процес розбиття продовжується до виявлення випадку 3.
Якщо припустити, що в середньому кожне розбиття зменшує вдвоє розмір підмасиву, в якому знаходиться шуканий елемент, то число необхідних порівнянь становить:

Текст програми представлений у Додатку 3.3

Блок-схема даного методу пошуку:
2.4.Задача на перевірку балансу дужок.
Дана задача реалізується за допомогою структури даних типу стек.
Стеком називається впорядкований набір елементів у якому додавання нових елементів і вилучення існуючих елементів виконується тільки з одного кінця, який наз вершиною стеку. Стек функціонуе за принципом LIFO, тобто: last in first out, що означає – перший зайшов, останній вийшов.
Алгоритм програми:
Перший крок: заносимо до нашого стеку довільні елементи, що містять три види дужок:”(“, “)”, “[”, “]”, “{”, “}”.
Другий крок: в циклі пробігоємося по стеку і якщо зустрічаються якісь дужки, то вмикаємо лічильник:
”(“- то d1:=d1+1; “)”-то d1:=d1-1; “[”- то d2:=d2+1; “]”- то d2:=d2-1; “{”- то d3:=d3+1; “}”- то d3:=d3-1; де d1,d2,d3-лічильники.
Третій крок: після першої (i=1) ітерації робимо перевірку: якщо (d1<0)або (d2<0)або (d3<0), то тоді баланс дужок невірний, а якщо умова не справджується, то продовжуємо далі.
Четвертий крок: після закінчення циклу робимо перевірку лічильників: якщо (d1>0)або (d2>0)або (d3>0), то тоді баланс дужок невірний, а якщо умова не справджується, то це означає, що всі лічильники дорівнюють 0, тобто боланс дужок є правильний.
Текст програми представлений у Додатку 3.4
Блок-схема даного алгоритму:
3. Тексти програм
3.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера.
На дискеті програми до даної задачі містяться за шляхом:
A:\Kursov_R\Zavd1\
В директорії programs містяться наступні файли:
type_Boolean
type_Wordbool
type_Longbool
type_Char
type_Byte
type_Shortint
type_Word
type_Integer
type_Longint
type_Real
type_Single
type_Double
type_Extended
type_Comp
type_String
type_Masiv
type_Record
3.2
Задача на сортування (сортування Шелла) .
На дискеті вони розміщені в директорії
A:\Kursov_r\zavd_2
В цій директорії знаходяться наступні файли:
shella.dpr
Текст програми:
program Part_2;
{$APPTYPE CONSOLE}
uses
SysUtils,DateUtils;
const rr=1000000;
TYPE
listerary = record
index,elem:integer ;
end;
ListType = array [1..rr] of listerary;
VAR
list : ListType;
ncomp, nswap, n, i, temp, temp1, i1, i2, k : INTEGER;
time1,time2:TDateTime;
time3:int64;
Y_N:char;
PROCEDURE swap (m,n:integer; VAR k, l : Listerary);
VAR
tmp1,tmp2 : INTEGER;
BEGIN
tmp1:= list[m].elem;
tmp2:= list[m].index;
list[m].elem:=list[n].elem;
list[m].index:=list[n].index;
list[n].elem:=tmp1;
list[n].index:=tmp2;
k:=list[m];
l:=list[n];
END;
PROCEDURE shell (VAR list : ListType; n : INTEGER);
VAR
m, i, j, r : INTEGER;
done : BOOLEAN;
BEGIN
ncomp := 0;
nswap := 0;
m := n;
REPEAT
m := (m + 2) div 3;
FOR i := m+1 TO n DO
BEGIN
j := i;
done := false;
WHILE ((j >= m+1) AND (NOT done)) DO
BEGIN
ncomp := ncomp + 1;
IF ( list[j-m].elem < list[j].elem ) THEN
done := true
ELSE
BEGIN
r:=j-m;
swap (j, r, list[j], list[j-m]);
nswap := nswap + 1
END;
j := j - m
END
END;
UNTIL m <= 1
END;
BEGIN
Randomize;
writeln ('Enter quantity of items in array');
readln (n);
writeln('Enter HighEnd for Random function');
readln (k);
FOR i := 1 TO n DO
Begin
list[i].elem:=random (k);
list[i].index:=i;
end;
readln;
writeln (^l);
writeln ('Before Sorting');
writeln;
FOR i := 1 TO n DO
write (' ',list[i].elem);
writeln;
writeln;
{ Sort with subroutines }
time1:=time;
shell (list, n);
time2:=time;
writeln;
writeln ('After Sorting');
writeln;
FOR i := 1 TO n DO
write (' ',list[i].elem);
writeln;
writeln;
writeln ('Number of comparisons=', ncomp);
writeln ('Number of exchanges=', nswap);
writeln;
time3:=MilliSecondsBetween(time2,time1);
Writeln ('Sort Time: ',time3,' miliseconds');
writeln('');
writeln ('Do you want to investigate search algorithm on resistance?');
readln(y_n);
case y_n of
'y': begin
temp1:=0;
for i:=1 to n do
begin
temp:=list[i].elem;
i2:=0;
if temp>temp1 then
Begin
temp1:=temp;
k:=i;
for i1:=k+1 to n do
begin
if temp=list[i1].elem then
begin
while i2<>1 do
begin
writeln('');
write('Same elements have index: ');
write (list[i].index);
i2:=1;
end;
write (' ',list[i1].index);
end;
end;
end;
end;
end;
'n': writeln('');
end;
readln;
END.
3.3 Задача на пошук медіани списку.
На дискеті вони розміщені в директорії
A:\Kursov_r\zavd_3
В цій директорії знаходяться наступні файли:
median.dpr
Текст програми:
program Pr3;
{$APPTYPE CONSOLE}
uses
SysUtils;
const n=10;
var
x,k,i1:integer; a:array [1..n] of integer;
procedure find;
var l,r,i,j,w:integer;
begin
l:=1; r:=n;
while l<r do
begin
x:=a[k]; i:=l; j:=r;
repeat while a[i]<x do i:=i+1;
while x<a[j] do j:=j-1;
if i<=j then begin
w:=a[i]; a[i]:=a[j]; a[j]:=w;
i:=i+1; j:=j-1; end
until i>j;
if j<k then l:=i;
if k<i then r:=j
end;
end;
begin
k:=(n+1) div 2;
writeln('vvedit a[i]:');
for i1:=1 to n do begin
write('a[',i1,']=');
readln(a[i1]);
end;
find;
writeln(' mediana poslidovnosti =',x);
readln;
{ TODO -oUser -cConsole Main : Insert code here }
end.
3.4. Задача на перевірку балансу дужок.
На дискеті вони розміщені в директорії
A:\Kursov_r\zavd_4
В цій директорії знаходяться наступні файли:
bal_duj.dpr
Текст програми:
program stack3;
{$APPTYPE CONSOLE}
uses
SysUtils;
label dali;
type
InfoType=char;
StackType=record
info:array[0..100]of InfoType;
top:word;
end;
var x:infotype;
s:Stacktype;
j,i,d1,d2,d3,er:integer;
procedure InitS(var s:StackType);
begin
s.top:=0;
end;
procedure PushS(var s:StackType; x:InfoType);
begin
inc(s.top);
s.Info[s.top]:=x;
end;
procedure PrintStack(var s:StackType);
begin
writeln('');
write('Stack:');
for i:=1 to s.top do
write(' ',s.info[i]);
writeln('');
end;
begin
InitS(s);
writeln('Enter the stack:');
for i:=1 to 100 do
begin
write('Element ',i,':');
readln(x);
if x=#13 then goto dali;
PushS(S,x);
end;
dali: inc(s.top);
j:=i-1;
PrintStack(s);
er:=1; d1:=0;d2:=0;d3:=0;
for i:=1 to j do
begin
if(s.info[i]='(') then d1:=d1+1;
if(s.info[i]=')') then d1:=d1-1;
if(s.info[i]='{') then d2:=d2+1;
if(s.info[i]='}') then d2:=d2-1;
if(s.info[i]='[') then d3:=d3+1;
if(s.info[i]=']') then d3:=d3-1;
if (d1<0)or(d2<0)or(d3<0) then er:=0;
end;
if (d1>0)or(d2>0)or(d3>0) then er:=0;
if er=0 then Writeln('Error')
else writeln('Normal');
readln;
end.

4. Тестування
4.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера.
4.1.1. Логічні типи
b1: Boolean
Змінна b1:=TRUE. Як відомо, якщо значення змінної рівне TRUE, то у кожний байт пам’яті, відведеної під змінну, буде записано -1. Під змінну типу Boolean відводиться 1 байт.
1 байт

Очікуваний результат
01

Результат виконання програми
01

Представлення в пам’яті комп’ютера
00000001


b2: WordBool
Змінна b2:=succ(b1). Змінні даного типу займають у пам’яті 2 байти. Знайдемо вмістиме пам’яті. Функція succ(b1) додає до значення, яке міститься у комірках пам’яті, відведених під b1, число 1.Оскільки вмістиме одного байту дорівнює нуль, змінна b2 набуде значення FALSE.
1 байт
2 байт

Очікуваний результат
00
00

Результат виконання програми
00
00

Представлення в пам’яті комп’ютера
00000000
00000000


b3: LongBool
Змінна b3:=pred(pred(b1)). Змінні даного типу займають у пам’яті 4 байти. Знайдемо вмістиме пам’яті враховуючи, що функція pred(b1) зменшує значення b1 на 1.Змінна b3 набуде значення FALSE.
1 байт
2 байт
3 байт
4 байт

Очікуваний результат
00
00
00
00

Результат виконання програми
00
00
00
00

Представлення в пам’яті комп’ютера
00000000
00000000
00000000
00000000


4.1.2. Цілочисельні типи
i4: Integer
Дані даного типу займають в пам’яті комп’ютера 2 байти. i4:=-750 ( число від’ємне, отже змінна зберігатиметься у доповняльному коді.
Переведемо прямий код у доповняльний. Для цього проінвертуємо iпрям, починаючи від розряду наступного після першої крайньої справа одиниці:
iпрям
0
0
0
0
0
0
1
0
1
1
1
0
1
1
1
0

iдоп
1
1
1
1
1
1
0
1
0
0
0
1
0
0
1
0


1 байт
2 байт

Очікуваний результат
FD
12

Результат виконання програми
12
FD

Представлення в пам’яті комп’ютера
0001 0010
1111 1101


i2: ShortInt
Дані даного типу займають в пам’яті комп’ютера 1 байт. i2:=-6, отже змінна зберігатиметься у доповняльному коді: -610=01102пр=10102доп.
Доповнюємо до 1-го байту:
1111 0000





1 байт

Очікуваний результат
FA

Результат виконання програми
FA

Представлення в пам’яті комп’ютера
1111 1010


i5: LongInt
Дані даного типу займають в пам’яті комп’ютера 4 байти. i5:=-750, отже змінна зберігатиметься у доповняльному коді:
-75010=1.10111 011102пр =1.01000 100102доп.
Доповнюємо до 4-х байт:
1111 1111
1111 1111
1111 1111
1000 0011


1 байт
2 байт
3 байт
4 байт

Очікуваний результат
FF
FF
12
FD

Результат виконання програми
12
FD
FF
FF

Представлення в пам’яті комп’ютера
0001 0010
1111 1101
1111 1111
1111 1111


i1: Byte
Дані даного типу займають в пам’яті комп’ютера 1 байт. i1:=6, отже змінна зберігатиметься у прямому коді: 110=0.01102пр.
Доповнюємо до 1-го байту, дописуючи спереду 0:
0000 0001


1 байт

Очікуваний результат
06

Результат виконання програми
06

Представлення в пам’яті комп’ютера
0000 0110


i3: Word
Дані даного типу займають в пам’яті комп’ютера 2 байти. i3:=750, отже змінна зберігатиметься у прямому коді: 75010=0.10111 011102пр .
Доповнюємо до 2-х байт, дописуючи спереду 0:
0000 0000
0111 1101


1 байт
2 байт

Очікуваний результат
02
EE

Результат виконання програми
EE
02

Представлення в пам’яті комп’ютера
1110 1110
0000 0010


4.1.3. Дійсні типи
r1: Real
З вхідних даних r1:=6.8500. Переведемо окремо цілу і дробову частини. Ціла частина: 610=6HEX.
Переводимо дробову частину числа. Для цього дріб, який відповідає числу X(10), множимо на 16 (основу системи числення, в яку ми переводимо) за правилами десяткової арифметики. В отриманому добутку від’єднується ціла частина, яка може дорівнювати 0, а дробова частина знову множиться на 16 з наступним від’єднанням цілої частини. Ця операція повторюється або до отримання нульової дробової частини добутку, або до отримання необхідної кількості розрядів числа X(16). Старша цифра результату переведення (тобто, перша після коми) збігається з першою від’єднаною цілою частиною.
X
0.8500
16


X
0.6000
16

>
X
13.6000
0.6000
16

>
X
9.6000
0.6000
16

>
X
9.6000
0.6000
16

>
X
9.6000
0.6000
16

>
X
9.6000
0.6000
16

>
9.60

>
X
9.6000
0.6000
16


>
X
9.6000
0.6000
16


>
X
9.6000
0.6000
16


>
9.60



Отже, число матиме вигляд: r1:= 6.D999999999 HEX.
Записавши дане число у двійковому представленні, отримуємо:
110, 1101 1001 1001 1001 1001 1001 1001 1001 1001 1001
Нормуємо число. Для цього виконуємо зсув вліво на один розряд, щоб отримати лише одну одиницю перед комою.
Визначаємо порядок. Оскільки ми зсунули число на 1 розряд вліво, то порядок буде:
(129+2)10 = 13110 = 8316 =1000 00112
Число додатнє, тому першу 1 замінюємо на 0. Знаходимо мантису числа разом зі знаковим бітом, які разом займають 5 байт:
0
1011 0110 0110 0110 0110 0110 0110 0110 0110 0110
1000 0011


знаковий біт+мантиса порядок
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт

Очікуваний результат
66
66
66
66
66
66

Рез-тат вик. програми
66
66
66
66
66
66

Предст. в пам’яті комп.
0110 0110
0110 0110
0110 0110
0110 0110
0110 0110
0110 0110


r2: Single
З вхідних даних r2:=856.25 Перевід цілої і дробової частини здійснюється аналогічно, як і для змінної типу real. Результатом переводу у 16-ву систему числення буде: r2:= 358.4(0)HEX.
Записавши дане число у двійковому представленні, отримуємо:
0011, 0101 1000 0100 0000 0000 0000 …
Нормуємо число. Для цього виконуємо зсув вліво на вісім розрядів. Визначаємо порядок. Оскільки ми зсунули число на 8 розрядів вліво, то порядок буде:
(127+9)10 = 13610 = 8816 =100010002.
Число додатнє, тому знаковий біт =0. Знаходимо мантису числа, яка займає 23 біта:
0
10001000
1010 1100 0010 0000 0000 0000


знаковий біт+порядок мантиса
Заокруглення виконувати не потрібно.
Записуємо мантису, знаковий біт та порядок у формат числа та переводимо у 16-ову систему числення:
0
100
0100
0
101
0110
0001
0000
0000
0000

s
е
m

( (
( (
( (
( (

8
8
A
C
2
0
0
0


1 байт
2 байт
3 байт
4 байт

Очікуваний результат
56
44
00
10

Результат виконання програми
00
10
56
44

Представлення в пам’яті комп’ютера
1001 1010
1110 1001
1100 0111
0100 0011


r3: Double
З вхідних даних r3:=-856.25. Перевід цілої і дробової частини здійснюється аналогічно, як і для змінної типу real. Результатом переводу у 16-ву систему числення буде: r3:=-358.4(0)HEX.
Записавши дане число у двійковому представленні, отримуємо:
001,1010 1100 0010 0000 0000 0000 0000 …
Нормуємо число. Для цього виконуємо зсув вліво на вісім розрядів. Визначаємо порядок. Оскільки ми зсунули число на 8 розрядів вліво, то порядок буде:
(1023+9)10 = 103210 = 40816 =100000010002.
Число від’ємне, тому знаковий біт залишаємо одиницею. Знаходимо мантису числа, яка займає 52 біта:
1
10000001000
1010 1100 0010 0000 0000 0000 0000 0000 0000

знаковий біт+порядок
мантиса
Заокруглення не робимо, бо наступний розряд розрядної сітки рівний нулю.
Записуємо мантису, знаковий біт та порядок у формат числа та переводимо у 16-ову систему числення:
1
100 0000
1000
1010
1100 1110
0000 0000
0000 0000
0000 0000
0000 0000
0000 0000

S
e
M

( (
( (
( (
( (
( (
( (
( (
( (

8 1
1 5
9 C
0 0
0 0
0 0
0 0
0 0


1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт

ОР
C0
8A
C2
00
00
00
00
00

РВП
00
00
00
00
00
C2
8A
C0

ППК
0011 0011
0011 0011
0011 0011
0011 0011
0011 0011
1111 1101
0111 1000
1100 0000

Примітка. Тут і надалі застосовуються позначення: ОР - очікуваний результат, РВП - результат виконання програми; ППК - представлення у пам’яті комп’ютера.
r4: Extended
З вхідних даних r4:=856.25. Перевід цілої і дробової частини здійснюється аналогічно, як і для змінної типу real. Результатом переводу у 16-ву систему числення буде: r4:=358.4(0)HEX.
Записавши дане число у двійковому представленні, отримуємо:
001,1010 1100 0010 0000 0000 0000 0000 …
Нормуємо число. Для цього виконуємо зсув вліво на вісім розрядів. Визначаємо порядок. Оскільки ми зсунули число на 8 розрядів вліво, то порядок буде:
(16383+9)10 = 1639210 = 400816 =1000000000010002.
Число додатне, тому знаковий біт дорівнює 0. Число i=1, бо число не близьке до нуля.
Знаходимо мантису числа, яка займає 63 біта:
0
100000000001000
1
1010 1100 0010 0000 0000 0000 0000 0000 0000 000


знаковий біт+порядок мантиса
Робимо заокруглення, бо наступний розряд розрядної сітки рівний 1. Тоді
остання тетрада останього байту: 0100. В результаті отримуємо:
0
1000000
0000 1000
1
1010110
0001 0000
0000 0000
0000 0000
0000 0000
0000 0000
0000 0000
0000 0000

s
e
i
m

(
(
(
(
(
(
(
(
(
(

80
08
AC
20
00
00
00
00
00
00


1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт
10 байт

ОР
40
08
D6
10
00
00
00
00
00
00

РВП
00
00
00
00
00
00
10
D6
08
40

ППК
01000000
00001000
11010110
0001000
0000000
0000000
0000000
0000000
0000000
0000000


r5: Comp
З вхідних даних r5:=-75010=-2EE16. Значення змінних даного типу компілятор заокруглює до цілого. Оскільки число від’ємне, то воно зберігатиметься у доповняльному коді.
Проінвертуємо r5прям, починаючи від розряду наступного після першої крайньої справа одиниці:
Знаковий біт s=1, бо число від’ємне. Саме число доповнюємо до 63 біт (у доповняльному коді для цього у числа спереду дописуються одиниці).
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт

ОР
FF
FF
FF
FF
FF
FF
FD
12

РВП
12
FD
FF
FF
FF
FF
FF
FF

ППК
0001 0010
1111 1101
1111 1111
1111 1111
1111 1111
1111 1111
1111 1111
1111 1111


4.1.4. Символьний тип
ch: Char
Представлення даного типу у пам’яті визначається його кодом у таблиці ASCII. Оскільки Ch:=П, то ord('П')=20710. Переведемо у 16-ву систему числення:
Отже, 20710=CFHex
1 байт

Очікуваний результат
CF

Результат виконання програми
CF

Представлення в пам’яті комп’ютера
1100 1111


4.1.5. Рядковий тип
Str: String[15];
Проведемо розрахунок для Str:=’Прилипко’.
Для змінної даного типу в пам’яті комп’ютера виділиться 16 байт. У першому байті буде записано біжучу довжину рядка, а в наступних - символи рядка (тобто їх ASCII-коди).
Ord(’П’)=20710=CFHEX;
Ord(’п’)=23910=EFHEX;

Ord(’р’)=24010=A0HEX;
Ord(’к’)=23410=EAHEX;

Ord(’и’)=23210=E8HEX;
Ord(’о’)=23810=EEHEX;

Ord(’л’)=23510=EBHEX;


Ord(’и’)=23210=E8HEX;


Даний рядок містить 6 символів, отже у першому байті буде записано 06.
№ байту
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ОР
08
Cf
A0
E8
EB
A8
EF
EA
EE
X
X
X
X
X
X
X

РВП
08
Cf
A0
E8
EB
A8
EF
EA
EE
X
X
X
X
X
X
X

Примітка: X - довільні 16-ві дворозрядні числа.
У пам’яті комп’ютера змінна зберігатиметься у наступному вигляді:
1 байт
2 байт
3 байт
4байт
5 байт
6байт
7 байт
8 байт

0000 1000
1100 1111
1010 0000
1110 1000
1110 1011
1010 1000
1110 1111
1110 1010


9 байт
10 байт
11 байт
12 байт
13 байт
14 байт
15 байт
16 байт

1110 1110
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx

Примітка: X - двійкові 0 або 1.
4.1.6. Перелічуваний тип
P: (Prilipko,Oleksandr,Petrovych);
За умовою p:=Oleksandr. Під змінну даного типу буде відведено один байт. Для даного типу у пам’яті буде зберігатися порядковий номер елементу у типі. Номер рахується з нуля, отже, у пам’ять буде поміщено число 1.
1 байт

Очікуваний результат
01

Результат виконання програми
01

Представлення в пам’яті комп’ютера
00000001


4.1.7. Діапазонний тип
d: 06..85;
Задане значення d:=37. Число буде зберігатися у такому форматі, як зберігаються числа цілого типу. Перевівши у 16-ву систему числення: d=3710=25HEX. Для зберігання даного типу у пам’яті відведеться 1 байт.
1 байт

Очікуваний результат
25

Результат виконання програми
25

Представлення в пам’яті комп’ютера
0010 0101


4.1.8. Тип масив.
m: array [1..2,1..5] of char;
Розмір пам’яті, який відведеться для зберігання масиву дорівнюватиме 10 помножити на розмір пам’яті, який відводиться на зберігання одного елементу масиву. Змінні типу char займають у пам’яті 1 байт, отже, масив займатиме 10 байт.
В комірках пам’яті зберігатимуться коди символів:
змінна
значення
Ord(m[x,y])

m[1,1]
'2'
5010=32HEX

m[1,2]
'7'
5510=37HEX

m[1,3]
'0'
4810=30HEX

m[1,4]
'2'
5010=32HEX

m[1,5]
'0'
4810=30HEX

m[2,1]
'0'
4810=30HEX

m[2,2]
'1'
4910=31HEX

m[2,3]
'0'
4810=30HEX

m[2,4]
'5'
5310=35HEX

m[2,5]
'0'
4810=30HEX


1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт
10 байт

ОР
32
37
30
32
30
30
31
30
35
30

РВП
32
37
30
32
30
30
31
30
35
30

ППК
00110010
00110111
0011000
00110010
0011000
0011000
00110001
0011000
00110101
0011000


4.1.9. Тип запис
Поля запису, згідно умови, набувають значень:
String[15]
Integer
Char

rec.a1:=’Хуст’
rec.c1:=25
rec.b1:=’,’

rec.a2:=’Шкільна’
rec.c2:=2
rec.b2:=’,’



rec.b3:=’/’


Проведемо розрахунок з умови, що перше поле запису зберігається по найменшій адресі. Поля зберігатимуться в порядку опису. У даному випадку порядок полів буде таким: a1, a2, b1, b2, b3, c1, c2.
Розрахуємо представлення кожного з полів.
rec.a1
Біжуча довжина рядка: 0410=04HEX.
Ord(’Х’)=21310=D5HEX;

Ord(’у’)=24310=F3HEX;

Ord(’с’)=24110=F1HEX;

Ord(’т’)=24210=F2HEX;

Займає в пам’яті 16 байт.
rec.a2
Біжуча довжина рядка: 0710=07HEX.
Ord(’Ш’)=21610=D2HEX;
Ord(’ь’)=25210=FCHEX;

Ord(’к’)=23210=E8HEX;
Ord(’н’)=23710=EDHEX;

Ord(’і’)=17910=B3HEX;
Ord(’а’)=22410=E0HEX;

Ord(’л’)=23510=EBHEX;


Займає в пам’яті 16 байт.
rec.c1
Займає в пам’яті 2 байти. 2510=19HEX. Спереду дане число доповнюється до 2-х байт нулями.
rec.c2
Займає в пам’яті 2 байти. 210=02HEX. Спереду дане число доповнюється до двох байт нулями.
rec.b1
У одному байті пам’яті зберігатиметься код змінної. Ord(’,’)=4410=2CHEX.
rec.b2
У одному байті пам’яті зберігатиметься код змінної. Ord(’,’)=4410=2CHEX.
rec.b3
У одному байті пам’яті зберігатиметься код змінної. Ord(’/’)=4710=2FHEX.
Отже, весь запис матиме наступний вигляд:
Очікуваний результат:
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт
10 байт

04
D5
F3
F1
F2
XX
XX
XX
XX
XX












11 байт
12 байт
13 байт
14 байт
15 байт
16 байт
17 байт
18 байт
19 байт
20 байт

XX
XX
XX
XX
XX
XX
07
D2
E8
D3












21 байт
22 байт
23 байт
24 байт
25 байт
26 байт
27 байт
28 байт
29 байт
30 байт

EB
FC
ED
E0
XX
XX
XX
XX
XX
XX


31 байт
32 байт
33 байт
34 байт
35 байт
36 байт
37 байт
38 байт
39 байт


XX
XX
XX
19
02
00
2C
2C
2F


Примітка: X - довільні 16-ві цифри.
Результат виконання програми:
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт
10 байт

04
D5
F3
F1
F2
XX
XX
XX
XX
XX












11 байт
12 байт
13 байт
14 байт
15 байт
16 байт
17 байт
18 байт
19 байт
20 байт

XX
XX
XX
XX
XX
XX
07
D2
E8
D3












21 байт
22 байт
23 байт
24 байт
25 байт
26 байт
27 байт
28 байт
29 байт
30 байт

EB
FC
ED
E0
XX
XX
XX
XX
XX
XX












31 байт
32 байт
33 байт
34 байт
35 байт
36 байт
37 байт
38 байт
39 байт


XX
XX
XX
19
02
00
2C
2C
2F


Примітка: X - довільні 16-ві цифри.
Представлення в пам’яті комп’ютера:
1 байт
2 байт
3 байт
4 байт
5 байт
6 байт
7 байт
8 байт
9 байт

0000 0100
1101 0101
1111 0011
1111 0001
1111 0010
xxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx











10 байт
11 байт
12 байт
13 байт
14 байт
15 байт
16 байт
17 байт
18 байт

xxxxxxxx
xxxxxxxx
xxxxxxxx
хxxxxxxx
xxxxxxxx
xxxxxxxx
xxxxxxxx
0000 0111
1101 0010











19 байт
20 байт
21 байт
22 байт
23 байт
24 байт
25 байт
26 байт
27 байт

1110 1000
1101 0011
1110 0001
1111 1100
1110 1101
1110 0000
xxxxxxxx
xxxxxxxx
xxxxxxxx











28 байт
29 байт
30 байт
31 байт
32 байт
33 байт
34 байт
35 байт
36 байт

хxxxxxxx
xxxxxxxx
xxxxxxxx
хxxxxxxx
xxxxxxxx
xxxxxxxx
0001 1001
0000 0010
0000 0000











37 байт
38 байт
39 байт







0010 1100
0010 1100
0010 1111







Примітка: X - довільні 2-ві цифри.

4.1 Задача на сортування (сортування Шелла).
Опис алгоритму сортування програмою та дослідження методу на ефективність
Саме сортування програма здійснює за допомогою двох процедур: основної Shell (list, n) та допоміжної Swap (m, n, k, l). В процедуру Shell (list, n) передається не відсортований масив (послідовність) елементів і їх кількість. Процедура в залежності від кількості елементів сама встановлює оптимальний крок сортування, після чого починає порівнювати відповідні елементи, і якщо слід поміняти місцями елементи в послідовності, то викликається ще одна процедура Swap (m, n, k, l) в яку передаються порядкові значення елементів m, n в масивах k, l, після чого ця процедура здійснює перестановку елементів в послідовності. Процедура Shell (list, n) завершує своє виконання після здійснення сортування простою вставкою (сортування з кроком 1).
Ефективність Методу при 10000 елементах з множини 0...7000 і 6 кратному вимірюванні:
Час виконання: Tmin= 10 мс; Taver = 13 мс; Tmax = 20мс.
Кількість порівнянь: Сmin= 232669; Сaver = 236052; Сmax = 239375.
Кількість престановок: Mmin= 152125; Maver = 155464; Mmax = 158838.
Аналогічні параметри для інших методів сортування:
Сортування вставкою: Сортування обміном:
Caver = 25007499 Caver = 49995000
Maver = 25017498 Maver = 74992500
Taver = 7 c Taver = 20 c
Сортування вибором: Швидке сортування:
Caver = 49995000 Caver = 125445
Maver = 97904 Maver = 8404
Taver = 9 c Taver = 0,03 с для масиву і 0,08 с для списку
Блок-схема даного алгоритму:
5. Висновки
Курсова робота на тему “Структури даних та алгоритми” систематизувала, розширила і закріпила теоретичні і практичні знання з програмування.
Розв’язання конкретних прикладних задач (зокрема задачі на сортування, обчислення виразів) навчило застосовувати різноманітні структури даних та алгоритми по роботі з ними.
Задача на дослідження внутрішнього представлення даних узагальнила знання про зберігання даних, а також наочно показало ефективність використання тих чи інших структур даних.
Третя задача, в якій описано принцип сортування методом Шелла, дала можливість прослідкувати як відбувається процес сортування покроково.
Список використаної літератури
Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі. ( К.:Либідь, 1993, 224с.
Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/ Структуры даных/ Сортировка/ Поиск: Пер. с англ. ( К.: “ДиаСофт”, 2001, 688с.
Кнут Д. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы. Пер. с англ. ( М.: “Мир”, 1976, 735с.
Кнут Д. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск. Пер. с англ. ( М.: “Мир”, 1976, 714с.
Вирт Н. Алгоритмы+Структуры данных=Программы. ( М., 1985, 406с.
Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. ( М.: “Нолидж”, 2001, 576с.
Турбо Паскаль 7.0. -К.: Издательская группа BHV, 1996, 448с.