Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структури даних та алгоритми.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра електронних обчислювальних машин
Інформація про роботу
Рік:
2003
Тип роботи:
Курсова робота
Предмет:
Програмування
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
ІКТАМ
Кафедра ЕОМ
Курсова робота
з курсу „Програмування”
”Структури даних та алгоритми”
Виконав: ст. гр. КІ-
Прийняла:
Львів 2003
Завдання на курсову роботу
Завдання 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) Перевірка умов балансу дужок;
1. Вступ
Програма, написана на будь-якій мові програмування, є деякою описаною послідовністю операцій, котрі необхідно виконати з деякою сукупністю даних. В свою чергу будова конкретної обчислювальної машини і особливості трансляторів визначають внутрішнє представлення даних їх розміщення в пам’яті ЕОМ. Ці факти свідчать про те, що організація даних для обробки є важливим етапом розробки програмних продуктів, а проблема структур даних та алгоритмів роботи з ними є актуальною проблемою.
Для реалізації багатьох програм вибір структури даних є найважливішим рішенням, і коли вибір зроблено правильно, то розробка алгоритму програми значно спрощується. Для одних і тих самих даних різні структури будуть займати неоднаковий дисковий простір; ті самі операції з різними структурами даних створюють алгоритми різної ефективності. Тобто вибір алгоритмів та структур даних тісно взаємопов’язані і найчастіше поняття структури даних включає алгоритми роботи з даною структурою.
Важливим є кожен рівень представлення даних. Наприклад, обрана математична модель може не в цілому або не точно відображати властивості реальних об’єктів і існуючі між ними зв’язки. В свою чергу, синтаксис окремої алгоритмічної мови може значно обмежувати можливості опису логічної структури даних, або ж робить ці описи складними і громіздкими. Неможливим або неефективним виконання синтаксично (і семантично) правильної програми можуть зробити характеристики комп’ютера (малий об’єм пам’яті, низька швидкодія). Тому структури даних та їх внутрішнє представлення, а також зв’язки між ними є одним з важливих питань в програмуванні.
Ефективність роботи алгоритмів залежить не лише від структури даних, яка використовується, але й від того, як дана структура розміщена. Звичайно, оперуючи великими кількостями інформації, бажано щоб вона була певним чином відсортована. Для цього використовують різноманітні методи впорядкування, тобто сортування інформації.
Курсова робота присвячена дослідженню внутрішнього представлення даних в пам’яті ЕОМ, а також сортуванню методом вставки зі спадаючим приростом. Як доводилося вище, ці задачі не перестають бути актуальними у наш час.
2. Теоретична частина до задач
2.1. Задача на дослідження внутрішнього представлення даних в пам’яті комп’ютера.
2.1.1. Логічні типи
У середовищі програмування TurboPascal логічні типи представлені такими типами як Boolean, ByteBool, WordBool, LongBool. Значення, які можуть набувати змінні логічного типу, позначаються вбудованими ідентифікаторами констант False і True. Логічні змінні не можуть набувати інших значень, крім False і True. Для змінних і констант логічного типу визначено наступні співвідношення:
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора