Завдання 1. Представлення даних в пам’яті комп’ютера. 1.1. Теоретичні відомості. Концепція типів даних. Основною особливістю мови Pascal є концепція типів даних. Визначення, яке описує концепцію типізації даних таке: 1) довільний тип даних визначає множину значень, до яких може належати деяка константа, яку може приймати змінна або вираз і яку може формувати деяка операція або функція; 2) тип довільної константи, змінної або виразу може бути визначений по її опису. Для цього немає необхідності проводити які небуть обчислення; 3) кожна операція або функція вимагає аргументів певного типу і дає результат також фіксованого типу. Ієрархія типів даних. Типи даних можна поділити на 2 основні види: 1) Статичні – це такі дані, взаєморозподіл і взаємозв’язок яких залишається сталим; 2) Динамічні – це такі дані, внутрішня побудова яких формується згідно з деякими законами, але кількість елементів, їх взаємозв’язок і взаєморозподіл можуть динамічно змінюватись під час виконання програми. Представлення даних в пам’яті комп’ютера. 1. Цілі числа (2 байти в пам’яті комп’ютера). Назва типу Ідентифікатор Діапазон представлення числа Розмір пам’яті
Коротке ціле зі знаком shortint -128..+127 1 байт
Ціле зі знаком integer -32768..+32767 2 байти
Довге ціле зі знаком longint -2147483648.. +2147483647 4 байти
Коротке ціле без знаку byte 0..+256 1 байт
Ціле без знаку word 0..65535 2 байти
Додатні числа зберігаються у прямому коді (в першому біті числа знаходиться 0). Від’ємні чила зберігаються у доповняльному коді (в першому біті 1). Число 0 має одне представлення (+0). 2. Дійсні числа. Назва типу Ідентифіка- тор Діапазон представлен-ня числа Розмір пам’яті Внутрішній формат Значення числа
Дійсні одинарні числа
single 1.5*10-45.. 3.4*1038 4 байти S1 bitE8 bitM23 bit (-1)S*1.M* *2E-127
Дійсні real 2.9*10-39.. 1.7*1038 6 байт S1 bitE39 bitM8 bit (-1)S*1.M* *2E-129
Дійсні числа представляються у вигляді знака(+,-,0), мантиси та експоненти. Дійсні числа зберігаються у зворотному порядку розміщення байтів числа.
1.2. Опис алгоритму. Програмі, яка виконує завдання 1, ґрунтується на тому, що після введення змінної певного типу ми цю змінну переводимо у вигляд у якому вона зберігається в пам’яті комп’ютера (тобто у шістнадцяткову систему числення). Після цього ми виводимо змінну на екран монітора, а також її представлення у пам’яті комп’ютера. В залежності від того, якого типу змінна, під неї виділяється ділянка пам’яті певної довжини. Тому при виведенні змінних різних типів на екран виводиться рядок різної довжини (наприклад, для змінної типу integer – це 2 байти, а для змінної типу real – це 6 байт). 1.3. Текст програми. В даній програмі ми вводимо певні особисті дані (наприклад, дату народження, прізвище, адресу). Після цього ці дані присвоюються змінним різного типу. При підключенні модуля Unit1, за допомогою процедур, які в ньому описані відбувається перетворення чисел. Список процедур і їх призначення: Процедура BooleanTP переводить число типу boolean; Процедура WordBooleanTP переводить число типу wordbool; Процедура LongBooleanTP переводить число типу longbool; Процедура CharTP переводить число типу char; Процедура ByteTP byte; Процедура ShortIntegerTP переводить число типу shortint; Процедура WordTP переводить число типу word; Процедура IntegerTP переводить число типу integer; Процедура LongIntegerTP переводить число типу longint; Процедура RealTP переводить число типу real; Процедура SingleTP переводить число типу single; Процедура DoubleTP переводить число типу double; Процедура ExtendedTP переводить число типу extended; Процедура CompTP переводить число типу comp; Процедура StringTP переводить число типу string; Процедура CountingTP переводить число типу count; Процедура DiapasonTP переводить число типу diapason; Процедура MasyvTP переводить число типу array; Процедура RecordTP переводить число типу record. 1.4. Тестування. Формула знаходження значень змінних Значення змінних
true, якщо день народження парне число; b1 = false, якщо день народження непарне число; b2 := succ(b1); b3 := pred(pred(b1)); повертає попереднє значення b1. ch – перша літера Прізвища ; i1 – день народження; i2 := -i1; i3 := i1*125; i4 := -i3; i5 := -i3; r1– дробове число: ціла частина – місяць народження, дробова частина - рік народження; r2 := r1*125; r3 := -r2; r4 := r2; r5 := i5; str – Прізвище; p – Ім’я; d – число, яке відповідає дню народження + 15; m[1,1] – символ, який відповідає першій цифрі номера домашнього телефону; m[1,2] – символ, який відповідає другій цифрі; m[1,3] := ’0’; m[1,4] – символ, який відповідає третій цифрі; m[1,5] := ’0’; m[2,1] := ’0’; m[2,2] - символ, який відповідає четвертій цифрі; m[2,3] := ’0’; m[2,4] - символ, який відповідає п’ятій цифрі; m[2,5] - символ, який відповідає шостій цифрі; rec.a1 – назва міста в адресі прописки; rec.a2 – назва вулиці в адресі; rec.с1 – номер будинку в адресі прописки; rec.с2 – номер квартири в адресі прописки; rec.b1 := ’,’ ; rec.b2 := ’,’ ; rec.b3 := ’/’ ; S – множина всіх чисел кратних k з діапазону 02 .. 85, ( k = 3 );
Завдання 2. Сортування і пошук. 2.1. Сортування методом Шелла. 2.1.1. Теоретичні відомості. Для алгоритму сортування, який кожного разу переміщає запис тільки на одну позицію, середній час виконання буде в кращому разі пропорціонально N2, тому що в процесі сортування кожний запис повинен пройти в середньому через N*1/3 позицій. Тому, якщо бажано отримати метод, істотно перевершуючий по швидкості метод простих вставок, необхідний механізм, за допомогою якого записи могли б переміщатися великими скачками, а не короткими кроками. Такий метод запропонований в 1959 року Дональдом Л. Шеллом [Donald L. Shell, САСМ 2,7 (Juу, 1959), 30-32] і відомий у всьому світі під ім'ям свого автора. Спочатку ділимо 16 записів на 8 груп по два записи в кожній групі. В результаті сортування кожної групи записів по окремості приходимо до другого рядка. Цей процес називається першим проходом. Зверніть увагу на те, що елементи 154 і 512 помінялися місцями, а 908 і 897 перемістилися управо. Розділимо тепер записи на чотири групи по чотири в кожній. Потім знову розсортуємо кожну групу окремо; результат цього другого проходу показаний в третьому рядку таблиці. На третьому проході сортуються дві групи по вісім записів; процес завершується четвертим проходом, але час якого сортуються всі 10 записів. В кожній з проміжних стадій сортування беруть участь або порівняно короткі масиви, або вже порівняно добре впорядковані масиви, тому на кожному етапі можна користуватися методом простих вставок і сортування виконується досить швидко. Метод сортування Шелла також відомий під ім'ям Shellsort і методу сортування з "убуваючим зсувом" оскільки кожний прохід характеризується зсувом h, таким, що сортуються записи, кожний з яких відстоїть від попередньої на h позицій. Послідовність значень зсувів 8, 4, 2, 1 не потрібно вважати непорушної; можна користуватися будь-якою послідовністю але останній зсув повинен бути рівно 1. Як буде показано нижче, вибір значень зсувів на послідовних проходах має істотне значення для швидкості сортування. 2.1.2. Опис алгоритму. Крок 1. [Лічильнику COUNT присвоїти 1]. Установити в лічильниках COUNT[1] – COUNT[N] одиниці. Крок 2. [Цикл по і]. Виконувати Крок 3 при і=N, N-1, ..., 2; потім завершити виконання процедури. Крок 3. [Цикл по j]. Виконати Крок 4 при j= і-1, і-2, ..., 1. Крок 4. [Порівнювати Kj з Ki]. Якщо Ki < Kj , то збільшити COUNT[j] на1; в іншому випадку збільшити COUNT[i] на 1. Цей алгоритм сортує записи R1, ..., RN по ключах K1, ..., KN, використовуючи допоміжне поле елемента COUNT[1], …, COUNT[N] для підрахунку числа ключів, менших ніж даний. Після закінчення алгоритму величина COUNT[j]+1 визначає кінцеве положення елемента Rj. Варто зауважити, що в даному алгоритмі елементи не переміщаються, що значно підвищує швидкодію. Алгоритм дає правильний результат незалежно від числа рівних ключів. Цей спосіб сортування відрізняється швидкодією. Це зумовлено тим, що в даному алгоритмі елементи не переміщаються, а переміщення, як відомо, значно сповільнює виконання програми. Швидкодія алгоритму. Кількість порівнянь (С) залишається сталою і залежить від кількості елементів: Сmin=Cmax=Cср.=(N2-N)/2. Кількість операторів присвоювання також залежить від кількості елементів, а також від того, чи елементи вже є частково відсортовані. Якщо послідовність вже є відсортованою, то кількість операторів присвоювання Мmin=0. Якщо елементи послідовності розташовані в зворотному порядку, то кількість операторів присвоювання буде максимальною: Мmax=(N2-N)/2. В середньому: Mср.=(N2-N)/4. 2.1.3. Текст програми. В даній програмі ми вводимо послідовність з N елементів (N є константа; ми можемо її змінювати в процесі виконання програми). Для цього ми використовуємо цикл; на кожному кроці циклу відбувається присвоювання кожному елементу масиву в поле KEY введений елемент, а полю COUNT ми присвоюємо 1. Після цього використовуємо цикл в циклі. У внутрішньому циклі по j відбувається порівняння полів KEY A[i] i A[j] елементів масиву. Якщо поле KEY елемента A[i] є більшим за відповідне поле елемента A[j], то поле COUNT елемента A[i] збільшуємо на 1. В протилежному випадку збільшуємо на 1 поле COUNT елемента A[j]. Після закінчення виконання циклів ми виводимо елементи відповідно до зростання їх полів COUNT. 2.1.4. Тестування. Для тестування виберемо послідовність з N довільних елементів. Наприклад: 6, 22, 15, 13, 37, 1, 19, 45, 10, 31 (N=10). Після введення цих елементів отримаємо відсортовану послідовність: 1, 6, 10, 13, 15, 19, 22, 31, 37, 45. 2.2. Пошук методом відкритої адресації. 2.2.1. Теоретичні відомості. Розв’язок колізій методом відкритої адресації. Інший варіант розв'язання проблеми, пов'язаної з колізіями, полягає в тому, щоб повністю відмовитися від посилань, просто переглядаючи різні записи таблиці один за одним до тих пір, поки не буде знайдений ключ К або порожня позиція. Ідея полягає у формулюванні правила, згідно якого по даному ключу К визначається "пробна послідовність", т. д. послідовність позицій таблиці, які повинні бути переглянуті при вставці або пошуку К. Якщо при пошуку К згідно визначеної цим ключем послідовності зустрічається порожня позиція, можна зробити висновок про те, що К в таблиці відсутній (оскільки та ж послідовність перевірок повинна виконуватися при кожному пошуку К). Цей загальний клас методів названий відкритою адресацією [див. W. W. Реtеrsоn, 1ВМ J. Research & Develoment 1 (1957), 130-146]. Найпростіша схема відкритої адресації, відома як лінійне дослідження, використовує циклічну послідовність перевірок h(K), h(K) - 1 ..., 0, М - 1; М - 2 ..., h(К) + 1 (1) і описується таким чином. 2.2.2. Опис алгоритму. Алгоритм L (Лінійне дослідження і вставка). Цей алгоритм виконує пошук даного ключа К в таблиці з М вузлами. Якщо К відсутній в таблиці і таблиця не повна, ключ К буде вставлений в таблицю. Вузли таблиці позначаються як ТАВLЕ[i], 0 <= i < М, і можуть бути двох типів – порожніми і зайнятими. В зайнятих вузлах містяться ключі КЕY[i] і, можливе, інші поля. Допоміжна змінна N використовується для відстежування кількості зайнятих вузлів; вона розглядається як частина таблиці і збільшується на 1 при кожній вставці нового ключа. Алгоритм використовує хеш-функцію h(K) і лінійну послідовність проб (1) для адресації таблиці. Модифікації цієї послідовності обговорюються нижче. L1. [Хешування.] Встановити i «— h(К). (Тепер 0 <= i < М.) L2. [Порівняння.] Якщо вузол ТАВLЕ[i] порожній, перейти до кроку L4 . Інакше, якщо КЕY [i] = К, алгоритм успішно завершується. L3. [Перехід до наступного.] Встановити i <— і — 1; якщо тепер i < 0, встановити i < - i + М. Повернутися до кроку L2. L4. [Вставка.] (Пошук виявився невдалим.) Якщо N = М— 1, алгоритм завершується у зв'язку з переповнюванням (умова повного заповнення таблиці повністю в даному алгоритмі виглядає як N =М-1, а не як N = М). Інакше встановити N <— N + 1, помітити вузол ТАВLЕ[i] як зайнятий і встановити КЕY [i] <-- R. 2.2.3. Текст програми. При виконанні даної програми ми вводимо послідовність з N елементів (N довільне, можна змінювати під час виконання програми). Після цього розбиваємо список на m підсписків довжиною n. Для порівняння елементів використовуємо подвійний цикл. Спочатку шукаємо потрібний елемент у першому підсписку, потім у другому і так до m. Якщо елемент знайдений, то виводимо його на екран. Якщо при проходженні всіх підсписків не знайдено потрібного елемента, то виводимо повідомлення про те, що елемент відсутній. 2.2.4. Тестування. Для тестування виберемо послідовність з N довільних елементів. Наприклад: 6, 22, 15, 13, 37, 1, 19, 45, 10, 31 (N=10), та номер елемента (адресу). Якщо ми вибрали адресу 3, результатом виконання програми буде – 15.
Завдання 3. Стек. 3.1. Теоретичні відомості. Стеком називається впорядкований набір елментів, у якому додавання нових і вилучення існуючих елементів виконується тільки з одного кінця, який називається вершиною стеку. 3.2. Опис алгоритму. В даному алгоритмі ми використовуємо двонаправлений циклічний список в якому кожен елемент має вказівники на наступний і попередній елементи, а також інформаційне поле. При виконанні програми потрібно пройтись по всіх елементах списку, вилучаючи при цьому окремі елементи, на які вказує поле DIG. При цьому потрібно враховувати вилучені елементи. Даний алгоритм зручно використовувати, коли у нас циклічний двонаправлений список, оскільки при такій побудові процедура вилучення є простою. 3.3. Текст програми. Для реалізації цього алгоритму потрібно ініціалізувати список. Це виконує процедура Init(L). Після ініціалізації в поле DIG присвоюємо довільні числа. Для проходження списку використовуємо функцію FindAfter(L, K). Вона ґрунтується на тому, що рухаючись по вказівниках на наступний елемент функція FindAfter виводить вказівник на наступний елемент. Поле DIG служить ідентифікатором для вилучення наступного елемента. Знайшовши потрібний елемент, ми за допомогою процедури Delete(L, K) вилучаємо цей елемент і рухаємось далі. 3.4. Тестування. Для тестування введемо число n. Нехай n=15, тоді сума буде рівною : S=1401602636313 Висновки.
Під час виконання курсової роботи “Структури даних та алгоритми” я ознайомився з основними та базовими типами і структурами даних. Також я ознайомився з основними алгоритмами роботи з масивами та списками. Було розроблено та протестовано ряд програм та алгоритмів які були використані при виконанні поставлених задач. Мною були розроблені програми, які виконували сортування елементів, пошук елемента у списку, реалізовували циклічний двонаправлений список, представляли дані у вигляді, у якому вони зберігаються у пам’яті комп’ютера. Також я набув навичок розробки програмних продуктів, їх тестування, а також навиків виконання та оформлення технічної документації. Додаток. Завдання 1. Представлення даних в пам’яті комп’ютера.
Текст програми. Program DataType; {$APPTYPE CONSOLE} uses SysUtils, Unit1 in 'Unit1.pas'; begin writeln('Input first letter of Your surname'); readln(ch); writeln('Input Your day of birthday'); readln(i1); {День народження} i2:=-i1; {-i1} i3:=i1*125; {i1*125} i4:=-i3; {-i3} i5:=-i3; {-i3} writeln('Input month and year of Your birthday, for example 10.89'); readln(r1); {дробове число:ціла частина-місяць народження, дробова частина-рік народження} r2:=r1*125; {r1*125} r3:=-r2; {-r2} r4:=r2; {r2} r5:=i5; {i5} writeln('Input Your surname'); readln(str); {Прізвище} writeln('Input Your name'); readln(p); {Ім'я} d:=i1+15; {День народження + 15} m[1,1]:='3'; m[1,2]:='9'; m[1,3]:='0'; m[1,4]:='8'; m[1,5]:='0'; m[2,1]:='0'; m[2,2]:='1'; m[2,3]:='0'; m[2,4]:='9'; m[2,5]:='6'; writeln('Input city You live'); readln(rec.a1); {назва міста в адресі прописки} writeln('Input street You live'); readln(rec.a2); {назва вулиці в адресі прописки} writeln('Input Your house number'); readln(rec.c1); {номер будинку в адресі прописки} writeln('Input Your apartment number'); readln(rec.c2); {номер квартири в адресі прописки} rec.b1:= ','; rec.b2:= ','; rec.b3:= '/'; BooleanTP(b1); WordBooleanTP(b2); LongBooleanTP; CharTP; ByteTP; ShortIntegerTP; WordTP; IntegerTP; LongIntegerTP; RealTP; SingleTP; DoubleTP; ExtendedTP; CompTP; StringTP; CountingTP; DiapasonTP; MasyvTP; RecordTP; readln end. Модуль, який використовує програма. unit Unit1; interface const zz1=02; zz2=85; zz3=zz2-30; var b1 : boolean; b2 : Wordbool; b3 : Longbool; ch : Char; i1 : Byte; i2 : Shortint; i3 : Word; i4 : Integer; i5 : Longint; r1 : Real; r2 : Single; r3 : Double; r4 : Extended; r5 : Comp; str : String [15]; p : String; d : zz1..zz2; m : array [1..2, 1..5] of char; rec : record a1, a2 : string[15]; b1, b2, b3 : char; c1, c2 : integer end; s : set of zz1 .. zz3 ; f : text; procedure BooleanTP(b1:boolean); procedure WordBooleanTP(b2:WordBool); procedure LongBooleanTP; procedure CharTP; procedure ByteTP; procedure ShortIntegerTP; procedure WordTP; procedure IntegerTP; procedure LongIntegerTP; procedure RealTP; procedure SingleTP; procedure DoubleTP; procedure ExtendedTP; procedure CompTP; procedure StringTP; procedure CountingTP; procedure DiapasonTP; procedure MasyvTP; procedure RecordTP; implementation procedure BooleanTP(b1:boolean); const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..1] of byte absolute b1; begin b1:=(i1 mod 2)=0; write('B1 = ',b1,' '); write('Predstavlennya typu Boolean: '); for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16]); writeln end; procedure WordBooleanTP(b2:WordBool); const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..2] of byte absolute b2; begin b2:=succ(b1); write('B2 = ',b2,' '); write('Predstavlennya typu WordBool: '); for i:=1 to 2 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure LongBooleanTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..4] of byte absolute b3; begin b2:=pred(pred(b1)); write('B3 = ',b3,' '); write('Predstavlennya typu LongBool: '); for i:=1 to 4 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure CharTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..1] of byte absolute ch; begin write('Ch = ', ch, ' '); write('Predstavlennya typu Char: '); for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure ByteTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..1] of byte absolute i1; begin write('I1 = ',i1,' '); write('Predstavlennya typu Byte: '); for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure ShortIntegerTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..1] of byte absolute i2; begin write('I2 = ',i2,' '); write('Predstavlennya typu ShortInt: '); for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16]); writeln end; procedure WordTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..2] of byte absolute i3; begin write('I3 = ',i3,' '); write('Predstavlennya typu Word: '); for i:=1 to 2 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure IntegerTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..2] of byte absolute i4; begin write('I4 = ',i4,' '); write('Predstavlennya typu Integer: '); for i:=1 to 2 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure LongIntegerTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..4] of byte absolute i5; begin write('I5 = ',i5,' '); write('Predstavlennya typu LongInt: '); for i:=1 to 4 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure RealTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..6] of byte absolute r1; begin write('R1 = ',r1:4:2,' '); write('Predstavlennya typu Real: '); for i:=1 to 6 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure SingleTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..4] of byte absolute r2; begin write('R2 = ',r2:6:2,' '); write('Predstavlennya typu Single: '); for i:=1 to 4 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure DoubleTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..8] of byte absolute r3; begin write('R3 = ',r3:6:2,' '); write('Predstavlennya typu Double: '); for i:=1 to 8 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure ExtendedTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..10] of byte absolute r4; begin write('R4 = ',r4:6:2,' '); write('Predstavlennya typu Extended: '); for i:=1 to 10 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure CompTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..8] of byte absolute r5; begin write('R5 = ',r5:4:0,' '); write('Predstavlennya typu Comp: '); for i:=1 to 8 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure StringTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..13] of byte absolute str; begin write('Str = ',str,' '); write('Predstavlennya typu String: '); for i:=1 to 12 do begin write(b[a[i] div 16], b[a[i] mod 16],' '); end; writeln end; procedure CountingTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..1] of byte absolute p; begin write('P = ',p,' '); write('Predstavlennya typu Count: '); for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure DiapasonTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..1] of byte absolute d; begin write('D = ',d,' '); write('Predstavlennya typu Diapason: '); for i:=1 to 1 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure MasyvTP; const b:array[0..15] of char='0123456789ABCDEF'; var i,j:integer; a:array[1..10] of byte absolute m; begin write('M = '); for i:=1 to 2 do begin for j:=1 to 5 do write(m[i,j],' '); end; writeln; write(' Predstavlennya typu Array: '); for i:=1 to 10 do write(b[a[i] div 16], b[a[i] mod 16],' '); writeln end; procedure RecordTP; const b:array[0..15] of char='0123456789ABCDEF'; var i:integer; a:array[1..39] of byte absolute rec; begin write('Rec = ',rec.a1,rec.b1,' ',rec.a2,rec.b2,' ',rec.c1, rec.b3,rec.c2,' ' ); writeln; write(' Predstavlennya typu Record: '); for i:=1 to 39 do begin write(b[a[i] div 16], b[a[i] mod 16],' '); if (i=10) or (i=20) or (i=30) then begin writeln; write(' '); end; end; writeln; end; end. Завдання 2. Сортування і пошук. Сортування. program SortList; uses SysUtils; {$APPTYPE CONSOLE} const n=10; type rec=record key:integer; count:integer; end; var i,j,k,l:integer; elem:rec; A: array [1..n] of rec; B: array [1..n] of integer; begin writeln ('Vvedit ',n, ' elementiv'); for i:=1 to n do begin readln (elem.key); A[i]:=elem; A[i].count:=1; end; l:=0; for i:=n downto 1 do begin for j:=i-1 downto 1 do begin if A[i].key>A[j].key then A[i].count:=A[i].count+1 else A[j].count:=A[j].count+1; l:=l+1; end; k:=A[i].count; B[k]:=A[i].key; end; for k:=1 to n do write (B[k], ' '); writeln; writeln('Kilkist porivnyan = ',l); readln end. Пошук. program poshyk; {$APPTYPE CONSOLE} uses SysUtils; var i:integer; a:array [1..10] of integer; begin Writeln('Vvedit chusla'); for i:=1 to 10 do begin readln (a[i]); end; Writeln('vvedit adresy'); readln(i); Writeln('potribnuj element = ',a[i]); readln; { TODO -oUser -cConsole Main : Insert code here } end. Завдання 3. Стек.
Текст програми. program Stack; {$APPTYPE CONSOLE} uses SysUtils; Const N=30000; Type InfoType=Integer; StackType=record Info:array [1..N] of InfoType; Top:Word; End; Var M,K,i:integer; x,Suma,E:real; A:array [1..N] of integer; S:StackType; Procedure Init(var S:StackType); Begin S.Top:=0; end; Function Full (S:StackType):Boolean; Begin Full:=S.Top=N; End; Function Empty (S:StackType):Boolean; Begin Empty:=S.Top=0; End; Procedure Push (var S:StackType; x:InfoType); Begin If Full(S) Then Writeln('Error: Stack is Full') else Begin inc(S.Top); S.Info[S.Top]:=x; end; End; Function Pop (var S:StackType):InfoType; Begin If Empty(S) Then Writeln('Error: Stack is Empty') Else Begin Pop:=S.Info[S.Top]; dec(S.Top); End; End; begin Writeln('Vvedit M'); Readln(M); Init(s); For k:=m downto 1 do begin Push(S,k); end; E:=1; Suma:=0; For i:=1 to M do Begin x:=Pop(S); E:=E*x; Suma:=Suma+E; End; Writeln('Suma=',Suma:4:0); Readln; { TODO -oUser -cConsole Main : Insert code here } end.
