Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структури даних та алгоритми.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2004
Тип роботи:
Курсова робота
Предмет:
Програмування
Група:
КІ-2
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська Політехніка”
Кафедра електронних
обчислювальних машин
Курсова робота
„Структури даних та алгоритми”
Виконав:
студент групи КІ-2
Перевірила:
Львів – 2004
Завдання 1. Представлення даних в пам’яті комп’ютера.
Дослідити представлення в пам’яті комп’ютера даних статичної структури. Розглянути основні прості (цілі, дійсні, символьні, логічні) і складові або фундаментальні (масиви, записи, рядки символів) структури даних.
const zz1 = місяць народження (дві цифри);
zz2 = дві останні цифри року народження; *
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 : (Прізвище, Ім’я, По-батькові); **
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;
* - Замість місяця і року народження підставляти свої конкретні дати (по дві цифри кожна).
** - Замість Прізвище, Ім’я, По-батькові підставляти свої конкретні значення, записані латинськими літерами ( перша літера - велика, решта – малі) .
Тестування провести для наступних значень змінних:
true, якщо день народження парне число;
b1 =
false, якщо день народження непарне число;
b2 := succ(b1);
b3 := pred(pred(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] - символ, який відповідає шостій цифрі;
{Якщо домашнього телефону немає, обрахунки проводити для кафедрального телефону, його номер 398196: m[1,1]:=’3’; m[1,2]:=’9’; m[1,4]:=’8’; m[2,2]:=’1’; m[2,4]:=’9’; m[2,5]:=’6’;}
rec.a1 – назва міста в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.a2 – назва вулиці в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.с1 – номер будинку в адресі прописки;
rec.с2 – номер квартири в адресі прописки;
rec.b1 := ’,’ ;
rec.b2 := ’,’ ;
rec.b3 := ’/’ ;
S – множина всіх чисел кратних k з діапазону zz1 .. zz3,
( k = № mod 5 + 2 , де № - порядковий номер студента в журналі викладача ).
Завдання 2. Сортування і пошук.
Реалізувати вказаний нижче метод сортування і пошуку в послідовності, представленій у вигляді масиву чисел або у вигляді лінійного однозв’язаного списку, елементи якого містять по декілька інформаційних полів (в загальному випадку – великих об’єми інформації), одне з яких є ключовим, і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв’язків. Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком. Дослідити метод на стійкість. Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для основних простих методів сортування (вставки, вибору, обміну), зробити висновки про ефективність метода, що досліджується. Дослідити метод на економність використання пам’яті. Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
Метод cортування : Порозрядне сортування.
Метод пошуку : Пошук Фібоначчі.
Завдання 3.
Скласти програму, яка обчислює арифметичний вираз, записаний у префіксній формі.
АНОТАЦІЯ
Комп’ютер – це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними.
Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застосовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані.
Велике значення в курсовій роботі приділяється методиці розробки програмних продуктів і стилю програмування.
Метою курсової роботи є:
- систематизувати, закріпити і розширити теоретичні і практичні знання з програмування, навчитися застосовувати різноманітні структури даних та алгоритми при розв'язанні конкретних прикладних задач;
отримати навики розробки більш складних програмних продуктів і оформлення програмної документації.
ЗМІСТ
Вступ ................................................................................................................................ 7 Завдання 1. Представлення даних в па’яті комп’ютера .................................... 8 1.1.Теоретичні відомості ................................................................................................ 8 1.2.Опис алгоритму ........................................................................................................ 9 1.3.Текст програми ......................................................................................................... 9 1.4.Тестування ............................................................................................................... 10 Завдання 2. Сортування і пошук ............................................................................. 11 2.1. Порозрядне сортування .................................................................................... 11 2.1.1.Теоретичні відомості .......................................................................................... 11 2.1.2.Опис алгоритму .................................................................................................. 11 2.1.3.Текст програми ................................................................................................... 11 2.1.4.Тестування ........................................................................................................... 11 2.2. Пошук Фібоначчі ............................................................................................... 12 2.2.1.Теоретичні відомості ......................................................................................... 12 2.2.2.Опис алгоритму .................................................................................................. 12 2.2.3.Текст програми ................................................................................................... 12 2.2.4.Тестування ........................................................................................................... 12 Завдання 3. Обчислення арифметичного виразу у префіксній формі .............. 13 3.1.Теоретичні відомості ..............................................................................................13 3.2.Опис алгоритму ...................................................................................................... 13 3.3.Текст програми ....................................................................................................... 13 3.4.Тестування .............................................................................................................. 13 Висновки ......................................................................................................................... 14 Список використаної літератури ............................................................................... 15 Додаток 1 ......................................................................................................................... 16 Додаток 2 ......................................................................................................................... 23 Додаток 3 ......................................................................................................................... 26
ВСТУП
В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для їх реалізації необхідно застосовувати більш складні прийоми. Послідовний файл займає проміжне значення, оскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Оскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами.
В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
В другому завданні будується один з методів сортування та пошуку. Досліджуються основні характеристики цього метода і проводиться порівняння ефективностей даного метода і класичних методів. Алгоритмам сортування і пошуку приділяється стільки уваги у зв’язку з тим, що за їх допомогою можна проілюструвати багато принципів програмування і ситуацій, що виникають в інших задачах.
В третьому завданні курсової роботи реалізується структура даних список і основні процедури роботи з ним. В цьому завданні на основі двохнаправленого циклічного списку реалізується задача пошуку і вилучення елемента зі списку без зміни інших елементів, що являється важливою задачею програмування.
Завдання 1. Представлення даних в пам’яті комп’ютера.
1.1. Теоретичні відомості.
Концепція типів даних. Основною особливістю мови Pascal є концепція типів даних. Визначення, яке описує концепцію типізації даних таке: 1) довільний тип даних визначає множину значень, до яких може належати деяка константа, яку може приймати змінна або вираз і яку може формувати деяка операція або функція; 2) тип довільної константи, змінної або виразу може бути визначений по її опису. Для цього немає необхідності проводити які небуть обчислення; 3) кожна операція або функція вимагає аргументів певного типу і дає результат також фіксованого типу.
Ієрархія типів даних. Типи даних можна поділити на 2 основні види:
1) Статичні – це такі дані, взаєморозподіл і взаємозв’язок яких залишається сталим;
2) Динамічні – це такі дані, внутрішня побудова яких формується згідно з деякими законами, але кількість елементів, їх взаємозв’язок і взаєморозподіл можуть динамічно змінюватись під час виконання програми.
Представлення даних в пам’яті комп’ютера.
1. Цілі числа (2 байти в пам’яті комп’ютера).
Додатні числа зберігаються у прямому коді (в першому біті числа знаходиться 0). Від’ємні чила зберігаються у доповняльному коді (в першому біті 1). Число 0 має одне представлення (+0).
2. Дійсні числа.
Дійсні числа представляються у вигляді знака(+,-,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. Тестування.
Завдання 2. Сортування і пошук.
2.1. Порозрядне сортування.
2.1.1. Теоретичні відомості.
Метод порозрядного сортування суттєво відрізняється від більшості методів сортування, оскільки в ньому використовується двійкове представлення ключів і тому він призначений виключно для двійкових машин. Замість того, щоб порівнювати між собою два ключа, в цьому методі перевіряється чи рівні 0 або 1 окремі біти ключа.
2.1.2. Опис алгоритму.
Послідовність сортуємо по знаку – спочатку від’ємні числа, а потім додатні з нулем. Далі виконуємо порозрядне сортування по спаданню від’ємних чисел, а потім по зростанню – додатніх. Саме порозрядне сортування полягає в тому, що, починаючи сортування з наймолодшого розряду, ми не повинні на наступних кроках сортування порушити вже частково сформований порядок ключів. Продовжувати порозрядне сортування треба поки послідовність не буде відсортована по всіх розрядах.
2.1.3. Текст програми.
В даній програмі ми вводимо послідовність з N елементів, або задаємо щоб програма ввела випадкові числа. Перший розряд числа відображає його знак ( 0 – якщо число від’ємне, 1 – якщо додатнє ). Сортуємо послідовність по знаку – спочатку від’ємні числа, а потім додатні з нулем. Далі виконуємо порозрядне сортування по спаданню від’ємних чисел, а потім по зростанню – додатніх. Сортування починаємо з наймолодшого розряду і продовжуємо аж до найстаршого, поки послідовність не буде повністю відсортована.
2.1.4. Тестування.
Для тестування виберемо послідовність з N довільних елементів. Наприклад: 150, 562, 15, -13, 7, 91, 0, 45, -910, 431 (N=10). Після введення цих елементів отримаємо відсортовану послідовність: -910, -13 , 0 , 7 , 15 , 45 , 91 , 150 , 431 , 562.
-910 00000000000000000000001110001110
-13 00000000000000000000000000001101
0 10000000000000000000000000000000
7 10000000000000000000000000000111
15 10000000000000000000000000001111
45 10000000000000000000000000101101
91 10000000000000000000000001011011
150 10000000000000000000000010010110
431 10000000000000000000000110101111
562 10000000000000000000001000110010
2.2. Пошук Фібоначчі.
2.2.1. Теоретичні відомості.
Числа Фібоначчі можуть відігравати роль, аналогічну степеням 2, тому за допомогою чисел Фібоначчі створюються методи пошуку, в деяких випадках ефективніші за бінарний пошук. Цей метод для деяких ЕОМ кращий ніж бінарний, оскільки він містить лише додавання та віднімання; немає необхідності ділення на 2.
2.2.2. Опис алгоритму.
Алгоритм F (Пошук Фібоначчі). Цей алгоритм призначений для пошуку аргумента К в таблиці записів R1, R2, … , RN, розміщених в порядку зростання ключів K1 < K2 < … < KN.
Для зручності опису вважаємо, що N+1 – число Фібоначчі FK+1.
F2. [Початкова установка.] Встановити i FK , q FK-1, p FK-2 ( В цьому алгоритмі p і q – послідовні числа Фібоначчі).
F2. [Порівняння.] Якщо K < Kі , перейти до кроку F3 ; якщо K > Kі , перейти до кроку F4 ; якщо K < Kі , алгоритм завершується успішно.
F3. [Зменшення і.] Якщо q=0, алгоритм завершується неуспішно. Якщо q < > 0, то встановити i i-q , замінити(p , q) на(q , p-q) і повернутися на F2.
F4. [Збільшення і.] Якщо p=1, алгоритм завершується неуспішно. Якщо p < > 1, то встановити i i+q , p p-q , q q+p і повернутися на F2.
2.2.3. Текст програми.
При виконанні даної програми ми вводимо послідовність з N=12 елементів, або задаємо програмі створити послідовність з випадкових чисел. Після програма сортує послідовність по зростанню. Порівнюємо елемент, який шукаємо з i (числом Фібоначчі порядку К). Якщо шукане число менше за Ki , то зменшуємо і, якщо більше за Ki , то збільшуємо і та повторюємо порівняння, а якщо рівне Ki , то виводимо порядковий номер числа в послідовності і завершуємо виконання програми.
2.2.4. Тестування.
Для тестування виберемо послідовність з N=12 довільних елементів. Наприклад введемо N чисел: 6, 12, 15, 23, 37, 41, 69, 95, 110, 141, 234, 241, та значення шуканого елемента. Якщо ми ввели значення 37, то результатом виконання програми буде – 5.
Завдання 3. Обчислення арифметичного виразу, записаного у префіксній формі.
3.1. Теоретичні відомості.
Списком називається структура даних, до якої елементи можуть додаватись (або вилучатись з нього) в довільному місці. Списки поділяються на однозв’язні та двозв’язні. Елемент однозв’язного списку складається з одного інформаційного поля ( або кількох ) та вказівника на наступний елемент. Елемент двозв’язного списку крім того містить ще й вказівник на попередній елемент.
3.2. Опис алгоритму.
В даному алгоритмі ми використовуємо однонаправлений лінійний список в якому кожен елемент має вказівник на наступний елемент, а також три інформаційних поля. Алгоритм обчислення базується на тому що ми за один цикл, переглядаючи список від початку, знайшовши знак операції та два операнди, виконуємо одну операцію і вносимо відповідні зміни в список.
3.3. Текст програми.
Для реалізації цього алгоритму потрібно ініціалізувати список. Це виконує процедура Init ( L ) . Після ініціалізації виконуємо ввід виразу в список. Для запису введених операцій та операндів у список використовується перевірка чи введений елемент є одним з чотирьох знаків арифметичних дій, чи числом чи символом закінчення вводу вираза. На основі цього, якщо введений знак, то в поле typ записується true, в поле znak – відповідний знак, а якщо введене число, то в поле typ записується false, а в num – значення числа. Ми переглядаємо список від початку, і коли зустрічається знак і два числа, слідуючих за ним, ми виконуємо відповідну операцію над операндами, зберігаємо результат в елементі списку, де був знак і видаляємо елементи списку де знаходились операнди за допомогою процедури Delete ( L , I ). Знову повторюємо перегляд, аж поки в списку не залишиться один елемент, значення інформаційного поля якого і буде результатом обчислення введеного арифметичного виразу.
3.4. Тестування.
Для тестування введемо наступний вираз, натискаючи Enter після вводу кожної операції та операнда : / + - * 15 2 37 19 + 7 1. Після вводу виразу у префіксній формі вводимо q, що означає кінець вводу. Отримаємо результат : 1.5 .
Висновки.
Під час виконання курсової роботи “Структури даних та алгоритми” я ознайомився з основними та базовими типами і структурами даних. Також я ознайомився з основними алгоритмами роботи з масивами та списками. Я розробив та протестував ряд програм та алгоритмів, які були використані при виконанні поставлених задач. Мною були розроблені програми, які представляли дані у вигляді, у якому вони зберігаються у пам’яті комп’ютера, виконували сортування елементів, пошук елемента у списку, реалізовували однонаправлений список, обчислювали арифметичний виразу, записаний у префіксній формі. Також я набув навичок розробки програмних продуктів, їх тестування, а також навиків виконання та оформлення технічної документації.
Список використаної літератури:
1. Методичні вказівки і завдання до курсової роботи „Структури даних та алгоритми” з курсу „Основи інформатики, алгоритмізації та мов програмування” для студентів спеціальності 7.091502 "Технологія проблемного та системного програмування" / Укл. Лисак Т.А. – Львів: ІППТ, 2002. – 50 с.
2. Кнут Д. Искусство програмирования, том 3. Сортировка и поиск. –М.: Изд.дом „Вильямс”, 2001. – 832 с.
Додаток 1. Представлення даних в пам’яті комп’ютера.
Текст програми.
program Kursova;
{$APPTYPE CONSOLE}
uses
SysUtils;
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);
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('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('Predstavlennya typu Word Boolean: ');
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('Predstavlennya typu Long Boolean: ');
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 Short integer: ');
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 Long Integer: ');
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 write(b[a[i] div 16], b[a[i] mod 16],' ');
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 Counting: ');
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
for j:=1 to 5 do write(m[i,j],' ');
writeln;
write(' Predstavlennya typu Masyv: ');
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;
begin
writeln('Vvedit pershu literu prizvushca (velyku)');
readln(ch);
writeln('Vvedit den narodzhennja');
readln(i1); {День народження}
i2:=-i1; {-i1}
i3:=i1*125; {i1*125}
i4:=-i3; {-i3}
i5:=-i3; {-i3}
writeln('Vvedit drobove chyslo:cila chastyna-misjatc narodzh, drobova-rik');
readln(r1); {дробове число:ціла частина-місяць народження,
дробова частина-рік народження}
r2:=r1*125; {r1*125}
r3:=-r2; {-r2}
r4:=r2; {r2}
r5:=i5; {i5}
writeln('Vvedit prizvyshce z velykoi litery');
readln(str); {Прізвище}
writeln('Vvedit imja z velykoi litery');
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('Vvedit misto');
readln(rec.a1); {назва міста в адресі прописки}
writeln('Vvedit vulytcju');
readln(rec.a2); {назва вулиці в адресі прописки}
writeln('Vvedit nomer budynku');
readln(rec.c1); {номер будинку в адресі прописки}
writeln('Vvedit nomer kvartyry');
readln(rec.c2); {номер квартири в адресі прописки}
rec.b1:= ',';
rec.b2:= ',';
rec.b3:= '/';
if (i1 mod 2)=0
then b1:=true
else b1:=false;
write('B1 = ',b1,' ');
BooleanTP(b1);
b2:=succ(b1);
write('B2 = ',b2,' ');
WordBooleanTP(b2);
b3:=pred(pred(b1));
write('B3 = ',b3,' ');
LongBooleanTP;
CharTP;
ByteTP;
ShortIntegerTP;
WordTP;
IntegerTP;
LongIntegerTP;
RealTP;
SingleTP;
DoubleTP;
ExtendedTP;
CompTP;
StringTP;
CountingTP;
DiapasonTP;
MasyvTP;
RecordTP;
readln
end.
Додаток 2. Сортування і пошук.
Порозрядне сортування.
program PorozrSort;
{$APPTYPE CONSOLE}
uses SysUtils;
const n=10; h=32;
type TElem=record
dec:integer;
bin:array [1..h] of char;
end;
TSpysok=array[1..n] of TElem;
var i,j,k,p,a_or_b:integer; {a_or_b: 0 - a, 1 - b}
a,b:TSpysok;
c:TElem;
procedure Dec2Bin(var z:TElem; x:integer);
var k,l:byte;
b:string[2];
y:integer;
begin
b:='01'; k:=h; y:=abs(x);
while y>=2 do begin
z.bin[k]:=b[(y mod 2)+1];
y:=y div 2;
k:=k-1
end;
z.bin[k]:=b[y+1];
for l:=k-1 downto 1 do z.bin[l]:='0';
if x>=0
then z.bin[1]:='1' {1 - chyslo dodatnie}
else z.bin[1]:='0' {0 - chyslo vidjemne}
end;
procedure Vvid(var z:TSpysok);
var sign,i,choice:integer;
begin
Randomize;
writeln('1 - Vypadkovi chysla');
writeln('2 - Vvesty chysla');
readln(choice);
while (choice<>1) and (choice<>2) do begin
writeln('!!! Nevirnyj vybir. Vvedit'' 1 abo 2');
readln(choice);
end;
if choice=1 then begin
sign:=1;
for i:=1 to n do begin
a[i].dec:=Random(1000)*sign;
sign:=-sign;
Dec2Bin(a[i], a[i].dec)
end;
end
else if choice=2 then begin
writeln('Vvedit'' 10 chysel');
for i:=1 to n do begin
readln(a[i].dec);
Dec2Bin(a[i], a[i].dec)
end;
end;
writeln('---===||| Vhidna poslidovnist''');
for i:=1 to n do writeln(a[i].dec,' ',a[i].bin)
end;
procedure SortVidjem(w:TSpysok; var z:TSpysok; k:integer);
var i,j:integer;
begin
j:=1;
if p>=2 then begin
for i:=1 to p do begin
if w[i].bin[k]='1' then begin
z[j]:=w[i];
j:=j+1
end;
end;
for i:=1 to p do begin
if w[i].bin[k]='0' then begin
z[j]:=w[i];
j:=j+1
end;
end;
end;
end;
procedure SortDodat(w:TSpysok; var z:TSpysok; k:integer);
var i,j:integer;
begin
j:=n;
if n-p>=2 then begin
for i:=n downto p+1 do begin
if w[i].bin[k]='1' then begin
z[j]:=w[i];
j:=j-1
end;
end;
for i:=n downto p+1 do begin
if w[i].bin[k]='0' then begin
z[j]:=w[i];
j:=j-1
end;
end;
end;
end;
procedure Vyvid(z,w:TSpysok);
var i: byte;
begin
writeln('---===||| Vidsortovana poslidovnist''');
if a_or_b=0
then for i:=1 to n do writeln(z[i].dec,' ',z[i].bin)
else for i:=1 to n do writeln(w[i].dec,' ',w[i].bin);
end;
begin
Vvid(a);
for i:=n downto 2 do
for j:=1 to i-1 do
if a[j].bin[1]>a[j+1].bin[1] then begin
c:=a[j+1];
a[j+1]:=a[j];
a[j]:=c
end;
p:=0;
while a[p+1].bin[1]='0' do p:=p+1; {p - kil''kist'' vidjemnyh chysel}
if p=1 then b[1]:=a[1];
if p=n-1 then b[n]:=a[n];
k:=h;
while k>=2 do begin
SortVidjem(b,a,k); SortDodat(b,a,k);
a_or_b:=0; k:=k-1;
if k>=2 then begin
SortVidjem(a,b,k); SortDodat(a,b,k);
a_or_b:=1; k:=k-1
end;
end;
Vyvid(a,b);
readln
end.
Пошук Фібоначчі
program FiboSearch;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
n=12;
type
TSpysok=array[1..n] of integer;
Var
K,i:integer;
a:TSpysok;
error:boolean;
porivn:integer;
procedure Vvid(var z:TSpysok);
var sign,i,choice:integer;
begin
Randomize;
writeln('1 - Vypadkovi chysla');
writeln('2 - Vvesty chysla');
readln(choice);
while (choice<>1) and (choice<>2) do begin
writeln('!!! Nevirnyj vybir. Vvedit'' 1 abo 2');
readln(choice);
end;
if choice=1 then begin
sign:=1;
for i:=1 to n do begin
a[i]:=Random(1000)*sign;
sign:=-sign;
end;
end
else if choice=2 then begin
writeln('Vvedit'' 12 chysel');
for i:=1 to n do readln(a[i])
end
end;
procedure Sort(var z:TSpysok);
var i,j,x:integer;
begin
for i:=n downto 2 do
for j:=1 to i-1 do
if a[j]>a[j+1] then begin
x:=a[j+1];
a[j+1]:=a[j];
a[j]:=x
end
end;
function Find(z:TSpysok; x:integer):integer;
var i,p,q,p1:integer;
found:boolean;
begin
Find:=0;
error:=false;
found:=false;
i:=8; p:=5; q:=3;
repeat
porivn:=porivn+1;
if x<a[i]
then
if q<>0 then begin
i:=i-q;
p1:=p;
p:=q; q:=p1-q
end
else begin
writeln('!Nema takogo elementa v masyvi!');
readln; halt
end
else begin
porivn:=porivn+1;
if x>a[i] then
if p<>1 then begin
i:=i+q;
p:=p-q; q:=q-p
end
else begin
writeln('!Nema takogo elementa v masyvi.!');
readln; halt
end
else begin
Find:=i;
found:=true
end
end
until found;
end;
begin
porivn:=0;
writeln('*** Poshuk Fibonacci ***');
Vvid(a); Sort(a);
writeln(' Vhidna poslidovnist''');
for i:=1 to n do writeln(i,') ',a[i]);
write('Vvedit'' element, jakyy treba znaity: ');
readln(K);
writeln('Poriadkovyi nomer chysla ',K,': ',Find(a,K),'.');
writeln('Kil''kist'' porivnian'' : ',porivn,'.');
readln
end.
Додаток 3.
Обчислення арифметичного виразу, записаного у префіксній формі.
program spysok_masyv;
{$APPTYPE CONSOLE}
uses SysUtils, A_list;
begin
Init(L);
writeln('** Obchyslennia vyrazy, zapysanogo v prefiksnij formi **');
Vvid(L,Free,Space);
writeln('** Rezultat obchyslennia : ',PrefixCalculate(L):10:4,'**');
readln
end.
unit A_List;
interface
const N=100;
type
IndexType=0..N;
InfoType=real;
ElemType=record
typ:boolean;
num:InfoType;
znak:char;
next:IndexType;
end;
ListType=IndexType;
SpaceType=array [0..N] of ElemType;
var L:ListType;
Free:IndexType;
Space:SpaceType;
procedure Init (var L:ListType);
function Empty (L:ListType):boolean;
function Full (L:ListType):boolean;
function FindLast (L:ListType):IndexType;
function FindBefore (L:ListType; K:IndexType):IndexType;
procedure Delete (var L:ListType;K:IndexType);
procedure AddElem (var L:ListType; t:boolean; x:InfoType; c:char);
procedure Vvid(var L:ListType;var Free:IndexType;var Space:SpaceType);
function PrefixCalculate (L:ListType):real;
implementation
procedure Init (var L:ListType);
var i:IndexType;
begin
for i:=1 to N-1 do space[i].Next:=i+1;
Space[0].next:=0;
Space[N].next:=0;
L:=0;
Free:=1
end;
function Empty (L:ListType):boolean;
begin
Empty:=L=0
end;
function Full (L:ListType):boolean;
begin
Full:=Free=0
end;
function FindLast (L:ListType):IndexType;
var i:IndexType;
begin
i:=L;
while Space[i].Next<>0 do i:=space[i].Next;
FindLast:=i
end;
function FindBefore (L:ListType; K:IndexType):IndexType;
var i:IndexType;
begin
i:=L; FindBefore:=0;
while Space[i].Next<>K do i:=Space[i].Next;
FindBefore:=i
end;
procedure Delete (var L:ListType;K:IndexType);
var i,j:IndexType;
begin
i:=K;
if Space[i].Next=0
then begin
j:=FindBefore(L,i); Space[j].Next:=0;
end
else begin
j:=Space[i].Next; Space[i]:=Space[j]; i:=j;
end;
Space[FindLast(Free)].Next:=i; Space[i].Next:=0
end;
procedure AddElem (var L:ListType; t:boolean; x:InfoType; c:char);
var i,j:IndexType;
begin
if not Full(L) then begin
i:=Free;
Free:=Space[Free].next;
space[i].typ:=t; space[i].num:=x; space[i].znak:=c;
space[i].next:=0;
j:=FindLast(L);
space[j].Next:=i;
end
else writeln('Error: List is Full')
end;
procedure Vvid(var L:ListType;var Free:IndexType;var Space:SpaceType);
var i:integer; s:string; x:InfoType;
begin
writeln('- Vvedit vyraz v prefiksnij formi, natyskajuchy "Enter"');
writeln(' pislia kozhnogo operatora ta operanda');
writeln(' (dlia zakinchennia vvodu vyraza vvedit'' q)');
repeat
readln(s);
if (s[1]='+')or(s[1]='-')or(s[1]='*')or(s[1]='/')or(s[1]='.')
or(s[1]='1')or(s[1]='2')or(s[1]='3')or(s[1]='4')or(s[1]='5')
or(s[1]='6')or(s[1]='7')or(s[1]='8')or(s[1]='9')or(s[1]='0')
then if (s[1]='+')or(s[1]='-')or(s[1]='*')or(s[1]='/')
then AddElem(L,true,0,s[1])
else begin
Val(s,x,i); AddElem(L,false,x,' ');
end
else if s[1]='q'
then writeln('- vvid zakincheno')
until s[1]='q';
end;
function PrefixCalculate (L:ListType):real;
var i,j:IndexType; z:char; calc:0..2; a:array[1..2] of InfoType;
begin
PrefixCalculate:=0; calc:=0; z:=' ';
while FindLast(L)>1 do begin
i:=L;
repeat
i:=Space[i].next;
if Space[i].typ=true
then begin
calc:=0; z:=Space[i].znak
end
else begin
calc:=calc+1; a[calc]:=Space[i].num
end;
until calc=2;
j:=FindBefore(L,i); Delete(L,i);
i:=FindBefore(L,j); Delete(L,j);
Space[i].typ:=false;
Space[i].znak:=' ';
case z of
'+': Space[i].num:=a[1]+a[2];
'-': Space[i].num:=a[1]-a[2];
'*': Space[i].num:=a[1]*a[2];
'/': Space[i].num:=a[1]/a[2];
end;
end;
i:=Space[L].next;
if Space[i].next=0
then PrefixCalculate:=Space[i].num
else writeln('Error - je > 1 elem')
end;
end.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора