Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структури даних та алгоритми.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2004
Тип роботи:
Курсова робота
Предмет:
Основи інформатики, алгоритмізації та мов програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет ’Львівська політехніка’
Кафедра ЕОМ
Курсова робота
Із дисципліни”Структури даних та алгоритми”
з курсу ”Основи інформатики, алгоритмізації та мов програмування ”
Львів 2004
ЗМІСТ
ВСТУП 2
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ 3
1.1. Вимоги до розробки програмних продуктів 4
1.2. Вимоги до оформлення пояснювальної записки 4
2. ВАРІАНТИ ЗАВДАНЬ 6
2.1. Завдання 1 6
2.2. Завдання 2 8
2.2.1. Завдання 2.1 9
2.2.2. Завдання 2.2 9
2.3. Завдання 3 10
3. ДОДАТОК 9
3.1. Додаток 1 11
3.2. Додаток 2.1 18
3.3. Додаток 2.2 20
3.4. Додаток 3 22
4. СПИСОК ЛІТЕРАТУРИ 30
ВСТУП
Комп’ютер – це машина, що обробляє інформацію. Вивчення засобів програмування передбачає вивчення того, яким чином ця інформація організована всередині ЕОМ, як вона обробляється і як може бути використана. Тому, для вивчення дисципліни студенту особливо важливо зрозуміти концепцію організації даних і роботи з ними.
Програма представляє собою в кінцевому рахунку конкретні формулювання абстрактних алгоритмів, що базуються на конкретних представленнях і структурах даних. Зрозуміло, що рішення про структури даних які необхідно застосувати неможливо прийняти без знання алгоритмів, що застусовуються до цих даних, і навпаки, вибір алгоритмів суттєво залежить від вибраних структур даних. Отже, структури програм і структури даних нерозривно пов’язані.
В курсовій роботі спочатку розглядаються фундаментальні структури які складаються з простих даних. Вони представляють собою компоненти, з яких складаються більш складні структури. Змінні фундаментальної структури можуть змінювати тільки своє значення, зберігаючи незмінною свою форму. Таким чином, розмір пам’яті яку вони займають залишається постійним. Навпаки, ускладнені структури характеризуються зміною не тільки значення, але й форми під час виконання програми. Тому для йх реалізації необхідно застусовувати більш складні прийоми. Послідовний файл займає проміжне значення, поскільки хоча його довжина й змінюється, але ця зміна форми є тривіальною. Поскільки послідовний файл грає важливу роль практично у всіх обчислювальних системах, він буде розглядатись разом з фундаментальними структурами.
В першому завданні курсової роботи досліджується представлення в пам’яті комп’ютера даних статичної структури. Розглядаються прості (цілі, дійсні, символьні, логічні, перелічувані, обмежені) і складові або фундаментальні (масиви, множини, записи, рядки символів, файли) структури даних.
В другому завданні будується одна з більш складних динамічних структур даних (стеки, черги, списки, дерева, графи), розробляються алгоритми і програмні реалізації роботи з нею і за їх допомогою розв’язується прикладна задача.
В другому завданні будується один з методів сортування або пошуку. Досліджуються основні характеристики цього метода і проводиться порівняння ефективностей даного метода і класичних методів. Алгоритмам сортування і пошуку приділяється стільки уваги у зв’язку з тим, щоза їх допомогою можна проилюструвати багато принципів програмування і ситуацій, що виникають і в інших задачах.
Велике значення в курсовій роботі приділяється методиці розробки програмних продуктів і стилю програмування.
Метою курсової роботи є:
- систематизувати, закріпити і розширити теоретичні і практичні знання з програмування, навчитися застосовувати різноманітні структури даних та алгоритми при розв'язанні конкретних прикладних задач;
отримати навики розробки більш складних програмних продуктів і оформлення програмної документації.
1. ВИМОГИ ДО ПОРЯДКУ ВИКОНАННЯ ТА ОФОРМЛЕННЯ
КУРСОВОЇ РОБОТИ
Завдання на курсову роботу видаються студенту керівником курсової роботи індивідуально. Можливе їх корегування керівником під час виконання роботи.
Виконуючи курсову роботу студент повинен розробити, відла годити та протестувати програму на мові Turbo Pascal (або іншій - узгодивши із керівником курсової роботи) і оформити пояснювальну записку.
1.1. Вимоги до розробки програмних продуктів.
Програма має складатися із двох частин:
- модулів, що містить підпрограми, які реалізують суть кожного завдання;
- тестуючої програми, яка демонструє працездатність основних підпрограм.
Результати тестування мають видаватися у зручному для сприйтяття вигляді (текстовому, табличному, графічному). Текстові значення мають виводитися як на екран відеомонітора, так і в файл (при потребі). Вивід таблиць і графіків теж можна оформити як окремі підпрограми. Таблиці і графіки повинні мати заголовки та зручний для читання вигляд. Як підпрограму доцільно оформити і дії пов'язані із вводом даних необхідних для тестування.
Тестуюча програма повинна мати зручний користувацький інтерфейс, наприклад, вона повинна мати меню. Меню може бути декількаступеневим - після вибору пункту меню вишого рівня, з'являється меню наступного (підпорядкованого) рівня. Для кожного завдання треба передбачити як ввід довільних вхідних даних, так і можливість використання деяких тестуючих значень по замовчуванню. Всі результати, що вводяться або виводяться мають обов’язково супроводжуватись повідомленнями.
Розроблена в курсовій роботі програма повинна легко читатися, відповідати вимогам структурного програмування, всі імена повинні нести змістовне навантаження, коментарів у програмі повинно бути стільки, щоб програма була самодокументованою.
1.2. Вимоги до оформлення пояснювальної записки
Пояснювальна записка повинна бути переплетена у тверду обкладинку.
Пояснювальна записка українською мовою може бути надрукована або написана від руки. В обох випадках текст розміщується на одному боці аркуша паперу формату А4. Рекомендується розміщувати до 30 рядків на сторінці.
Обсяг пояснювальної записки повинен становити 20 - 25 сторінок друкованого тексту або 25 – 30 сторінок рукописного тексту.
На аркушах необхідно залишити поля з усіх чотирьох боків. Розмір лівого поля - 25 мм, правого - не менше 10 мм, верхнього і нижнього - не менше 20 мм.
На аркушах, де починаються розділи, зміст, анотація, вступ, висновки, список літератури рекомендується збільшувати розмір верхнього поля до 40 мм.
Чорнило, яким виконується робота, має бути чорним, фіолетовим чи синім .
Пояснювальна записка має бути стислою, чіткою, лаконічною і містити лише інформацію, яка має пряме відношення до теми курсової роботи.
Рекомендується наступний склад розділів пояснювальної за писки:
Титульна сторінка
Завдання на курсову роботу
Анотація
Зміст
Вступ
1. Теоретична частина
2. Опис алгоритму
3. Текст програми
4. Тестування
Висновки
Список літератури
Додатки
В анотації викладаються короткі відомості про курсову ро боту. У вступі має приводитися коротка характеристика задач, їх місце і значення в тих галузях, до яких вони мають відношення. В тео ретичній частині мають приводитися всі теоретичні дані, які не обхідні для розробки алгоритму. Опис алгоритму містить текстові пояснення і блок-схеми алгоритму, які мають виконува тися згідно із стандартами [1]. В тексті програми описується зміст всіх програм і підпрограм, а самі тексти програм поміщаються в додатках.
Текст розділів може розділятися на підрозділи, пункти і підпункти. Розділи повинні нумеруватися арабськими цифрами в межах всієї записки. Вступ, висновки, список літератури і додатки не нумеруються.
Підрозділи необхідно нумерувати арабськими цифрами в межах кожного розділу. Номер підрозділу складається з номера розділу і номера підрозділу, розділених крапкою. Наприклад: "3.1." (перший параграф третього розділу). Пункти (якщо вони використовуються) нуме-руються аналогічно. Наприклад: "3.1.2." (другий пункт першого параграфу третього розділу).
Нумерація сторінок має бути наскрізною: першою сторінкою є титульна сторінка, другою - завдання, третьою - анотація і т.д. Номер сторінки проставляється у верхньому правому куті. На сторінках 1 (титульна сторінка), 2 (завдання), 3 (анотація) і 4 (перша сторінка змісту) номер сторінки не пишеться.
2. ВАРІАНТИ ЗАВДАНЬ
2.1. Завдання 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;
{ Наприклад, якщо дата народження 21.10.1982, то:
i1 := 21; i2 := -21; i3 := 2625; i4 := 2625; i5 := -2625;
r1 := 10.1982; r2 := 1274.775; r3 := -1274.775; r4:= 1274.775; r5 := -2625; }
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 , де № - порядковий номер студента в журналі викладача );
Алгоритм і вихідний текст програми, що реалізує розв’язок завдання 1 описано у додатку 1.
2.2. Завдання 2
Реалізувати один із вказаних нижче методів сортування або пошуку в послідовності, представленій у вигляді масиву чисел або у вигляді лінійного однозв’язаного списку, елементи якого містять по декілька інформаційних полів (в загальному випадку – велики об’єми інформації), одне з яких є ключовим, і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв’язків..
Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком.
Дослідити метод на стійкіть.
Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для основних простих методів сортування (вставки, вибору, обміну), зробити висновки про ефективність метода, що досліджується.
Дослідити метод на економність використання пам’яті.
Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з одинаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
2.2.1. Завдання 2.2.1.
Метод сортування.
Сортування Шелла, що використовує кроки 3, 2 і 1 [8, 466-469 c.].
Сортування Шелла дістало свою назву від творця Д.Л.Шелла.
Загальний метод, який використовує сортування вставкою, застосовує принцип зменшення відстані між своїми елементами. На малюнку показана схема виконання сортування Шелла для масиву ’оасве’. Спочатку сортуються всі елементи, які розміщені один від одного на відстані ’3’.Далі сортуються елементи, що розміщені на відстані ’2’. І нарешті сортуються всі сусідні елементи
прохід1 f d a c b e прохід2 c b a f d e прохід3 a b c e d f отриманий результат a b c d e f
Відстані між елементами можуть змінюватися по-різному. Обов’язковим є лиш те, що останній крок повинен дорівнювати 1. Наприклад, хороший результат дає послідовність кроків 3, 2, 1, яка використовується при розв’язанні цієї задачі.
Алгоритм і вихідний текст програми, що реалізує розв’язок завдання 2.2.1 описано у додатку 2.1.
2.2.2. Завдання 2.2.2.
Метод пошуку.
Однорідний бінарний пошук [6, 447-449 c.].
Якщо дані відсортовані, то можна використовувати метод пошуку названий однорідним бінарним пошуком. При такому пошуку використовується принцип ’розділяй і володій’. Спочатку проводиться перевірка середнього елемента. Якщо його ключ більше ключа потрібного елемента, то проводиться перевірка для середнього елемента із першої половини. В протилежному випадку проводиться перевірка для середнього елемента із другої половини. Цей процес продовжується доти, доки не буде знайдено потрібний елемент або поки не залишиться більше елементів для перевірки.
Наприклад, для пошуку числа 4 у масиві [ 1 2 3 4 5 6 7 8 9 ] однорідним бінарним пошуком спочатку проводиться перевірка середнього елемента, яким є число 5. Оскільки цей елемент є більшим за 4, то пошук буде продовжено в першій половині масиву, тобто серед чисел [ 1 2 3 4 5 ].Тут середнім елементом є 3. Це значення є менше 4 і тому перша половина не буде більше розглядатися і пошук продовжиться серед чисел [ 4 5 ]. Під час наступного кроку потрібний елемент буде знайдено.
При двійковому пошуку число порівнянь в найгіршому випадку дорівнює
Log n. Для середнього випадку це значення буде дещо кращим, а в найкращому випадку воно дорівнюватиме одиниці.
Алгоритм і вихідний текст програми, що реалізує розв’язок завдання 2.2.2. описано у додатку 2.2.
2. 3. Завдання 3
Побудувати базову структуру даних і алгоритми роботи з нею. Застусувати їх для розв’язку однієї з наступних задач згідно варіанту.
Написати алгоритм програми,яка реалізує арифметичні операції (додавання) із числами у форматі із плаваючою крапкою. Під час роботи програма повинна звертатись до стеку.
Потрібно зазначити, що при при виконанні будь-яких арифметичних дій над операндами,представленими у форматі з плаваючою крапкою,операції, що виконуються над мантисами і порядками (чи характеристиками) цих чисел, різні. Тому перед початком будь-якої арифметичної процедури кожен із операндів ’розділяється’: порядок (характеристика) відділяється від мантиси операнда, для виконання окремих операцій. Після виконання конкретної арифметичної дії і обов’язкової процедери нормалізації результату, його порядок або характеристика і мантиса ’упаковуються’ в звичайний формат з плаваючою крапкою.У випадку алгебраїчного додавання порядки операндів обов’язково повинні бути однаковими. Тому проводимо вирівнювання порядків.
Для цього мантиса операнду із меншою характеристикою зсувається по розрядній сітці вправо із додаванням одиниці при кожному зсуві на один розряд.
Результат буде мати отриману таким чином характеристику. Далі реалізується додавання по правилах аналогічних до тих, що застосовуються при додаванні чисел із фіксованою крапкою, зокрема мантиса одного із операндів перетворюється в доповняльний код (при відніманні). Далі, при необхідності проводиться ’нормалізація’ і заокруглення відповіді.
Алгоритм і вихідний текст програми, що реалізує розв’язок завдання 3 описано у додатку 3.
3. Додаток
3.1. Додаток 1.
unit Unit1;
interface
const zz1=09;
zz2=85;
zz3=55;
type dtype=zz1..zz2;
ptype=(soltys,vasyl,igorovich);
masyvtype=array[1..2,1..5]of char;
zapystype=record
a1,a2:string[15];
b1,b2,b3:char;
c1,c2:integer
end;
settype=set of zz1..zz3;
var b:array[0..15]of char='0123456789ABCDEF';
function bool1(x:boolean):integer;
function bool2(x:wordbool):integer;
function bool3(x:longbool):integer;
function symvolne(x:char):integer;
procedure tsile1(x:byte);
procedure tsile2(x:shortint);
procedure tsile3(x:word);
procedure tsile4(x:integer);
procedure tsile5(x:longint);
procedure dijsne1(x:single);
procedure dijsne2(x:real);
procedure dijsne3(x:double);
procedure dijsne4(x:extended);
procedure dijsne5(x:comp);
procedure stroka1(x:string);
procedure perelik(x:ptype);
procedure diapazon(x:Dtype);
procedure masyv(x:masyvtype);
procedure zapys(x:zapystype);
procedure mnozhyny(x:settype);
implementation
function bool1(x:boolean):integer;
begin
if x=false then bool1:=0 else bool1:=1
end;
function bool2(x:wordbool):integer;
begin
if x=false then bool2:=0 else bool2:=1
end;
function bool3(x:longbool):integer;
begin
if x=false then bool3:=0 else bool3:=1
end;
function symvolne(x:char):integer;
begin
symvolne:=ord(x)
end;
procedure tsile1(x:byte);
var a:byte absolute x;
begin
writeln(b[a div 16],b[a mod 16],' ')
end;
procedure tsile2(x:shortint);
var a:byte absolute x;
begin
writeln(b[a div 16],b[a mod 16],' ')
end;
procedure tsile3(x:word);
var i:byte;
a:array[1..2]of byte absolute x;
begin
for i:=1 to 2 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure tsile4(x:integer);
var i:integer;
a:array[1..2]of byte absolute x;
begin
for i:=1 to 2 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure tsile5(x:longint);
var i:integer;
a:array[1..4]of byte absolute x;
begin
for i:=1 to 4 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure dijsne1(x:single);
var i:integer;
a:array[1..4]of byte absolute x;
begin
for i:=1 to 4 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure dijsne2(x:real);
var i:integer;
a:array[1..6]of byte absolute x;
begin
for i:=1 to 6 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure dijsne3(x:double);
var i:integer;
a:array[1..8]of byte absolute x;
begin
for i:=1 to 8 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure dijsne4(x:extended);
var i:integer;
a:array[1..10]of byte absolute x;
begin
for i:=1 to 10 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure dijsne5(x:comp);
var i:integer;
a:array[1..8]of byte absolute x;
begin
for i:=1 to 8 do write(b[a[i] div 16],b[a[i] mod 16],' ')
end;
procedure stroka1(x:string);
var i:integer;
begin
write(length(x),' ');
for i:=1 to length(x) do write(ord(x[i]),' ')
end;
procedure perelik(x:ptype);
begin
case x of
soltys:writeln(b[0 div 16],b[0 mod 16],' ');
vasyl:writeln(b[1 div 16],b[1 mod 16],' ');
igorovich:writeln(b[2 div 16],b[2 mod 16],' ');
end;
end;
procedure diapazon(x:dtype);
var a:byte absolute x;
begin
writeln(b[a div 16],b[a mod 16],' ')
end;
procedure masyv(x:masyvtype);
var i,j:integer;
begin
for i:=1 to 2 do
for j:=1 to 5 do
write(ord(x[i,j]),' ');
end;
procedure zapys(x:zapystype);
begin
stroka1(x.a1);
stroka1(x.a2);
write(ord(x.b1),' ',ord(x.b2),' ',ord(x.b3),' ');
tsile4(x.c1);
tsile4(x.c2);
end;
procedure mnozhyny(x:settype);
var i:integer;
begin
for i:=zz1 to zz3 do
if i in x then write('1')
else write('0')
end;
end.
Тестуюча програма:
program Kursova1;
{$APPTYPE CONSOLE}
uses
SysUtils, Unit1;
type Birthtype=1..31;
var secondname:string[15];
birthday:birthtype;
homenumber:string[6];
i:integer;
n:1..30;
k:1..8;
b1:boolean;
b2:wordbool;
b3:longbool;
ch:char;
i1:byte;
i2:shortint;
i3:word;
i4:integer;
i5:longint;
r1:single;
r2:real;
r3:double;
r4:extended;
r5:comp;
str:string[15];
p:ptype;
d:dtype;
m:masyvtype;
rec:zapystype;
s:settype;
begin
writeln('input your birthday date(two digits):');
readln(birthday);
if (birthday mod 2)=0 then b1:=true
else b1:=false;
writeln('b1 in comp memory');
writeln(b[bool1(b1)div 16],b[bool1(b1)mod 16],' ');
b2:=succ(b1);
writeln('b2 in comp memory');
writeln(b[0div 16],b[0mod 16],' ');
writeln(b[bool2(b2)div 16],b[bool2(b2)mod 16],' ');
b3:=pred(pred(b1));
writeln('b3 in comp memory');
for i:=1 to 3 do write(b[0div 16],b[0mod 16],' ');
writeln(b[bool3(b3)div 16],b[bool3(b3)mod 16],' ');
writeln('input your second name:');
readln(secondname);
ch:=secondname[1];
writeln('first letter of your second name in the comp memory:');
writeln(symvolne(ch));
readln;
i1:=birthday;
writeln('i1 in the comp memory:');
tsile1(i1);
i2:=-i1;
writeln('i2 in the comp memory:');
tsile2(i2);
i3:=i1*125;
writeln('i3 in the comp memory:');
tsile3(i3);
writeln;
i4:=-i3;
writeln('i4 in the comp memory:');
tsile4(i4);
writeln;
i5:=i4;
writeln('i5 in the comp memory:');
tsile5(i5);
writeln;
readln;
r1:=9.1985;
writeln('r1 in the comp memory:');
dijsne1(r1);
writeln;
r2:=r1*125;
writeln('r2 in the comp memory:');
dijsne2(r2);
writeln;
r3:=-r2;
writeln('r3 in the comp memory:');
dijsne3(r3);
writeln;
r4:=r2;
writeln('r4 in the comp memory:');
dijsne4(r4);
writeln;
r5:=i5;
writeln('r5 in the comp memory:');
dijsne5(r5);
writeln;
readln;
str:=secondname;
writeln('your second name in the comp memory:');
stroka1(str);
writeln;
readln;
p:=vasyl;
writeln('your name in the comp memory:');
perelik(p);
readln;
d:=birthday+15;
writeln('d in the comp memory:');
diapazon(d);
writeln('input your home number(6 digits):');
readln(homenumber);
m[1,3]:='0';
m[1,5]:='0';
m[2,1]:='0';
m[2,3]:='0';
m[1,1]:=homenumber[1];
m[1,2]:=homenumber[2];
m[1,4]:=homenumber[3];
m[2,2]:=homenumber[4];
m[2,4]:=homenumber[5];
m[2,5]:=homenumber[6];
writeln('array m in the comp memory');
masyv(m);
writeln;
readln;
rec.a1:='калуш';
rec.a2:='драгоманова';
rec.c1:=8;
rec.c2:=34;
rec.b1:=',';
rec.b2:=',';
rec.b3:='/';
writeln('rec in the comp memory');
zapys(rec);
writeln;
writeln('input your number in the group:');
read(n);
k:=n mod 5+2;
s:=[];
for i:=zz1 to zz3 do if (i mod k)=0 then s:=s+[i];
writeln('set in the comp memory');
mnozhyny(s);
writeln;
readln
{ TODO -oUser -cConsole Main : Insert code here }
end.
3.2.Додаток 2.1:
unit shell1;
interface
procedure Shell(var a:array of integer; count:integer);
implementation
procedure Shell(var a:array of integer; count:integer);
const
t = 5;
var i, j, k, s, m: integer;
h: array[1..t] of integer;
x: integer;
begin
h[1]:=3;
h[2]:=2;
h[3]:=1;
for m := 1 to t do
begin
k:=h[m];
s:=-k;
for i := k+1 to count do
begin
x := a[i];
j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
a[s] := x;
end;
while (x<a[j]) and (j<count) do
begin
a[j+k] := a[j];
j := j-k;
end;
a[j+k] := x;
end;
end;
for i:=1 to count do write(a[i],' ');
writeln;
readln
end;
end.
Тестуюча програма:
program kursova2a;
{$APPTYPE CONSOLE}
uses
SysUtils,
shell1 in 'shell1.pas';
const n=21;
var i,sign:integer;
a:array[0..n]of integer;
begin
Randomize;
sign:=1;
for i:=1 to n do
begin
a[i]:=Random(10000);
write(a[i],' ')
end;
writeln;
Shell(a,n)
{ TODO -oUser -cConsole Main : Insert code here }
end.
3.3. Додаток 2.2:
unit bsearch1;
interface
function BSearch (a: array of integer; count:integer; k:integer):integer;
implementation
function BSearch (a: array of integer; count:integer; k:integer):integer;
var low, high, mid: integer;
found:boolean;
begin
low:=1;
high:=count;
found:=false; {не знайдено }
while (low<=high) and (not found) do
begin
mid:=(low+high) div 2;
if k<a[mid] then high:=mid-1
else if k>a[mid] then low:=mid+1
else found:=true; {знайдено}
end;
if found then BSearch:=mid
else BSearch:=0; {не знайдено }
end; { завершення пошуку }
end.
Тестуюча програма:
program kursova2b;
{$APPTYPE CONSOLE}
uses
SysUtils,
bsearch1 in 'bsearch1.pas';
const n=5;
var i,j,x,k:integer;
a:array[0..n]of integer;
sign:integer;
begin
Randomize;
sign:=1;
for i:=1 to n do
begin
a[i]:=Random(100)*sign;
write(a[i],' ');
sign:=-sign
end;
writeln;
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;
for i:=1 to n do write(a[i],' ');
writeln;
write('search==> ');
readln(k);
writeln('result==> ',BSearch (a,n,k));
writeln;
readln
{ TODO -oUser -cConsole Main : Insert code here }
end.
4. Додаток 3:
unit stack1;
interface
const n=8;
m=100;
type mas=array[1..m]of integer;
stacktype=record
data:array[1..m]of mas;
top:word
end;
var masR:mas;
stack:stacktype;
procedure binary(a:integer;var a2:mas);
function decimal(a:integer;k:integer):integer;
procedure sum(mas1:mas;mas2:mas);
procedure init(var s:stacktype);
function empty(s:stacktype):boolean;
function full(s:stacktype):boolean;
procedure push(var s:stacktype;x:mas);
function pop(var s:stacktype):mas;
implementation
procedure binary(a:integer;var a2:mas);
var i:integer;
begin
i:=1;
while(a>=2)and(i<=n)do begin
a2[i]:=a mod 2;
a:=a div 2;
i:=i+1
end;
a2[i]:=a;
for i:=n downto 1 do
write(a2[i])
end;
function decimal(a:integer;k:integer):integer;
var d,i:integer;
begin
if a=0 then decimal:=0;
if a=1 then begin
d:=1;
for i:=1 to k do d:=d*2;
decimal:=d
end
end;
procedure sum(mas1:mas;mas2:mas);
var k,j,i:integer;
begin
writeln('sum mantises in modified code:');
write(' ',mas1[n],mas1[n-1],mas1[n-2],'.');
for i:=n-3 downto 1 do write(mas1[i]);
writeln;
write(' ','+',' ',mas2[n],mas2[n-1],'.');
for i:=n-2 downto 1 do write(mas2[i]);
writeln;
write(' ');
for i:=1 to n+2 do write('=');
writeln;
masR[1]:=mas2[1];
k:=2;
while k<=n do begin
if mas2[k]<>mas1[k-1] then masR[k]:=1
else if mas2[k]=0 then masR[k]:=mas2[k]
else begin
masR[k]:=0;
if mas1[k]=0 then mas1[k]:=1
else if mas2[k+1]=0 then mas2[k+1]:=1
else begin
masR[k+1]:=1;
if (mas1[k+1]=0)or(mas2[k+2]=0)then
begin
if(mas1[k]=0)and(mas2[k+1]=0)thenmas1[k]:=1;
if mas1[k]=0 then mas1[k]:=1;
if mas2[k+1]=0 then mas2[k+1]:=1;
end;
k:=k+1;
end;
end;
k:=k+1;
end;
write(' ',masR[n],masR[n-1],'.');
j:=n-2;
while j>=1 do begin
write(masR[j]);
j:=j-1;
end;
push(stack,masR);
writeln;
end;
procedure init(var s:stacktype);
begin
s.top:=0
end;
function empty(s:stacktype):boolean;
begin
empty:=s.top=0
end;
function full(s:stacktype):boolean;
begin
full:=s.top=n
end;
procedure push(var s:stacktype;x:mas);
begin
if not full(s) then
begin
inc(s.top);
s.data[s.top]:=x
end
else writeln('error:stack is full');
end;
function pop(var s:stacktype):mas;
begin
if empty(s) then writeln('error:srack is empty')
else begin
pop:=s.data[s.top];
dec(s.top)
end;
end;
end.
Тестуюча програма:
program kursova3a;
{$APPTYPE CONSOLE}
uses
SysUtils,
stack1 in 'stack1.pas';
var a,b,i,j,propA,propB,propREZ:integer;
porA,porB,porREZ,k,result:integer;
abin,bbin,masM,mas2,mas1,p:mas;
signA,signB:char;
stack:stacktype;
begin
init(stack);
writeln('input operandes:');
write('a=');
readln(a);
write('b=');
readln(b);
writeln('in binary scalar system:');
write('a=');
binary(a,abin);
writeln;
write('b=');
binary(b,bbin);
writeln;
push(stack,abin);
push(stack,bbin);
readln;
writeln('with fields:');
write('a=');
write(abin[n],'.',abin[n-1],abin[n-2],abin[n-3],'.');
for i:=n-4 downto 1 do write(abin[i]);
writeln;
write('b=',bbin[n],'.',bbin[n-1],bbin[n-2],bbin[n-3],'.');
for i:=n-4 downto 1 do write(bbin[i]);
writeln;
readln;
writeln('signs of a&b');
if abin[n]=0 then signA:='+' else signA:='-';
if bbin[n]=0 then signB:='+' else signB:='-';
writeln(signA,'&',signB);
readln;
propB:=0;
writeln('properties:');
writeln('A');
for i:=n-1 downto n-3 do write(abin[i]);
write('=');
j:=0;
for i:=n-3 to n-1 do begin
propA:=propA+decimal(abin[i],j);
j:=j+1
end;
writeln(propA);
writeln('B');
for i:=n-1 downto n-3 do write(bbin[i]);
write('=');
j:=0;
for i:=n-3 to n-1 do begin
propB:=propB+decimal(bbin[i],j);
j:=j+1
end;
writeln(propB);
readln;
writeln('pokaznuku poriadkiv:');
write('A');
porA:=propA-4;
writeln(porA);
write('B');
porB:=propB-4;
writeln(porB);
readln;
write('mantusa A');
for i:=n-4 downto 1 do write(abin[i]);
writeln;
write('mantusa B');
for i:=n-4 downto 1 do write(bbin[i]);
writeln;
if porA<>porB then begin
write('vurivnianuj poriadok');
if porA>porB then porREZ:=porA
else porREZ:=porB;
writeln(porREZ);
write('mantusa vurivn. poriadky:');
if porA>porB then begin
k:=porA-porB;
i:=n-4;
j:=n-k-3;
repeat
masM[j]:=bbin[i];
i:=i-1;
j:=j-1;
until (j=1)or(i=1);
for i:=n downto (n-k-1) do masM[i]:=0;
masM[n-k-2]:=1;
mas2[n]:=0;
mas2[n-1]:=0;
mas2[n-2]:=0;
mas2[n-3]:=1;
i:=n-4;
while i>=1 do begin
mas2[i]:=abin[i];
i:=i-1;
end;
end;
if porB>porA then begin
k:=porB-porA;
i:=n-4;
j:=n-k-3;
repeat
masM[j]:=abin[i];
i:=i-1;
j:=j-1;
until (j=1)or(i=1);
for i:=n downto n-k-1 do masM[i]:=0;
masM[n-k-2]:=1;
mas2[n]:=0;
mas2[n-1]:=0;
mas2[n-2]:=0;
mas2[n-3]:=1;
i:=n-4;
while i>=1 do begin
mas2[i]:=bbin[i];
i:=i-1;
end;
end;
write(masM[n],masM[n-1],'.');
writeln;
push(stack,masM);
readln;
sum(mas2,masM);
end
else begin
writeln('poriadok rezyltaty:');
mas1[n-1]:=0;
mas1[n-2]:=0;
mas1[n-3]:=1;
for i:=n-4 downto 1 do mas1[i]:=abin[i];
mas2[n-1]:=0;
mas2[n-2]:=1;
mas2[n]:=0;
for i:=n-4 downto 1 do mas2[i+1]:=bbin[i];
readln;
sum(mas1,mas2);
end;
writeln;
writeln('near...');
write(masR[n-1],'.');
for i:=n-2 downto n-6 do write(masR[i]);
write('(');
for i:=n-7 downto 1 do write(masR[i]);
write(')');
writeln;
if masR[n-7]=1 then begin
i:=n-6;
while i<=n do begin
if masR[i]=0 then masR[i]:=1;
if masR[i]=1 then begin
masR[i]:=0;
i:=i+1
end;
end;
end;
writeln('mantusa rezyltaty:');
write(masR[n-1],'.');
for i:=n-2 downto n-6 do write(masR[i]);
writeln;
readln;
writeln('result properties:');
propREZ:=porREZ+4;
write(propREZ,'=');
binary(propREZ,mas1);
writeln;
readln;
writeln('result with fields:');
write('0.');
for i:=3 downto 1 do write(mas1[i]);
write('.');
for i:=n-3 downto n-6 do write(masR[i]);
writeln;
mas2[n]:=0;
for i:=n-4 downto 1 do mas2[i]:=masR[i+1];
j:=3;
for i:=n-1 downto n-3 do begin
mas2[i]:=mas1[j];
j:=j-1;
end;
writeln('result in binary code:');
for i:=n downto 1 do write(mas2[i]);
writeln;
push(stack,mas2);
readln;
result:=0;
for i:=1 to n do result:=a+b;
writeln('result: ',result);
writeln('stack:');
i:=stack.top;
while i<>0 do
begin
mas1:=pop(stack);
for k:=n downto 1 do write(mas1[k]);
writeln;
i:=i-1
end;
readln
{ TODO -oUser -cConsole Main : Insert code here }
end.
4. Список літератури
Методичні вказівки із дисципліни ’Програмування’, Львів, НУ “ЛП”, 2003р.
Д.Кнут “Искусство програмирования”, том 3, “Сортировка и поиск”, “Питер”,2001г.
Гудзь Р.В., Ярошко С.А. “Використання динамічних даних у програмах на Borland Pascal. Тексти лекцій”, 54с., Львів, ЛНУ ім. І.Франка, 2000р.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора