Міністерство освіти та науки України
Національний університет “Львівська політехніка”
ІКТАМ
Кафедра ЕОМ
Курсова робота
з курсу „Програмування”
”Структури даних та алгоритми”


Завдання на курсову роботу
Завдання 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 , де № - порядковий номер студента в журналі викладача );
Завдання 2
Реалізувати метод Сортування Шелла та Індексно-послідовного пошуку в послідовності, представленій у вигляді масиву чисел, елементи якого містять по декілька інформаційних полів (в загальному випадку – великі об’єми інформації), одне з яких є ключовим.
Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком.
Дослідити метод сортування Шелла на стійкіть.
Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для основних простих методів сортування (вставки, вибору, обміну), зробити висновки про ефективність метода, що досліджується.
Дослідити метод на економність використання пам’яті.
Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з одинаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
Завдання 3
Задача на пошук медіани списку:
Проходження по списку даним алгоритмом;
Сортування списку;
Знаходження медіани;
Завдання 4
Задача на перевірку балансу дужок:
1) Поелементне заповнення стеку;
2) Перевірка кожного елементу;
3) Перевірка умов балансу дужок;
Анотація
В курсовій роботі досліджуються:
представлення в пам’яті комп’ютера даних статичної структури. Розглядаються основні прості (цілі, дійсні, символьні, логічні) і складові і фундаментальні (масиви, записи, рядки символів) структури даних;
метод Ссортування Шелла та Індексно-послідовного пошуку в послідовності, представленій у вигляді масиву чисел, елементи якого містять по декілька інформаційних полів, одне з яких є ключовим, і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв’язків, метод сортування досіджується на стійкіть, економність використання пам’яті, на можливу специфіку вхідної послідовності, досіджується ефективність метода. Для цього визначається середні значення кількості порівнянь, кількості перестановок і часу виконання.
3) Задача на пошук медіани списку:
a) Проходження по списку даним алгоритмом;
b) Сортування списку;
c) Знаходження медіани;
4) Задача на перевірку балансу дужок:
a) Поелементне заповнення стеку;
b) Перевірка кожного елементу;
c) Перевірка умов балансу дужок;