ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.11.2019
Просмотров: 461
Скачиваний: 1
antibotan.com
ВСЕУКРАЇНСЬКИЙ СТУДЕНТСЬКИЙ АРХІВ
Головна
Інформація
Особистий кабінет
Форум
ТОП-10
Додати роботу
Реєстрація
Шукати
Пошук
ВУЗи
Типи робіт
Предмети
Тип роботи:
Курсова робота
ВУЗ:
Національний університет Львівська політехніка
Кафедра:
Електронні обчислювальні машини
Предмет:
Структури даних та алгоритми
Група:
КІ-2
Рік:
2004
Вартість:
7 балів
Частина тексту файла:
Міністерство освіти і науки України
Національний університет „Львівська Політехніка”
Кафедра електронних
обчислювальних машин
Курсова робота
„Структури даних та алгоритми”
Виконав:
студент групи КІ-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і , перейти до кроку 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. Теоретичні відомості.