Нікітін Д.М., Антонова А.Р. Алгоритми і методи обчислень. Посібник до виконання лабораторних робіт - файл n1.doc

Нікітін Д.М., Антонова А.Р. Алгоритми і методи обчислень. Посібник до виконання лабораторних робіт
скачать (775 kb.)
Доступные файлы (1):
n1.doc775kb.13.09.2012 13:39скачать

n1.doc

  1   2   3   4   5   6


Міністерство освіти і науки України
ОДЕСЬКА ДЕРЖАВНА АКАДЕМІЯ ХОЛОДУ

КАФЕДРА ПРОГРАМУВАННЯ



Нікітін Д.М., Антонова А.Р.


АЛГОРИТМИ І МЕТОДИ ОБЧИСЛЕНЬ

Посібник до виконання лабораторних робіт

Одеса 2009



Методичні вказівки розроблені та підготовлені до друку:

доцентом Нікітіним Д.М., ст. викладачем Антоновой А.Р.

Методичні вказівки розглянуті

на засіданні кафедри програмування

протокол № 5 від 28 січня 2009 року


Зав. кафедрою Косой Б.В.

і затверджені методичною комісією

Факультету інформаційних технологій

протокол № від 2009 року
Голова метод. комісії Корнієнко Ю.К.

Вступ



Дисципліна “Алгоритми і методи обчислень” входить до переліку обов’язкових дисциплін циклу професійно орієнтованих дисциплін освітньо-професійної програми вищої освіти за професійним спрямування 0915 “Комп’ютерна інженерія”. Необхідними передумовами для вивчення дисципліни “Алгоритми і методи обчислень" є засвоєння студентами матеріалу дисциплін "Вища математика", “Основи програмування та алгоритмічні мові”, “Об’єктно-орієнтовано програмування”, “Основи дискретної математики”, “Теорія ймовірностей, імовірнісні процеси і математична статистика” та “ Чисельні методи в інформатиці”.

Вивчення дисципліни сприяє формуванню наукового рівня інженерного мислення майбутнього фахівця, містить в собі теоретичну базу, яка необхідна при вирішенні прикладних питань оптимізації в конкретних задачах дослідження інформаційних комп'ютерних систем в техніці та економіці. Основу дисципліни складає засвоювання методів дослідження операцій та реалізація відповідних алгоритмів з використанням комп'ютерної техніки. Особлива увага надається методам вирішення задач лінійного та дискретного програмування в їх практичній інтерпретації.
Мета курсу:



Тема 1. “Елементи сучасної технології розробки алгоритмів”


Структурний підхід до розробки алгоритмів засновується на наступних принципах:


  1. використання для запису алгоритмів тільки базових структур: проходження, розвилка, повторення;

  2. кожен алгоритм (або його функція) повинен розроблятися, як простий:


Реалізація принципів структурного програмування дозволяє впорядкувати алгоритми і позитивно впливає на етапи тестування і супроводження програм. Тестування – це процес виконування програми з метою виявлення помилок, тобто перевірка наявності помилок у його роботі. Далеко не завжди вдається після виконаного тестування вказати точне місце помилки в алгоритмі. Як правило, для цього необхідно провести додатковий аналіз алгоритму. Цей процес називається налагодженням алгоритму. Таким чином, структурний підхід до розробки алгоритму означує виконання трьох основних етапів: успадкована розробка алгоритму, тестування і налагодження розробленого алгоритму.

Розробка алгоритму програми починається з виділення її основних функцій, а потім другорядних, призначених для забезпечення основних. Кожна із цих функцій може бути представлена в програмі окремим структурним елементом, який зветься модулем. Модуль - це послідовність логічно пов'язаних фрагментів, оформлених у виді окремої частини програми. Опрацювання програми у вигляді сукупності модулів зветься принципом модульного програмування, який характеризується наступними перевагами:


Таким чином, модульне програмування створює умови для керування процесом розробки великих програм, маневрування людськими ресурсами, підвищення якості завершених програм, накопичення в бібліотеках досвіду розробки програм у вигляді стандартних функцій обробки даних.

В програмуванні часто виникає задача перерозташування елементів різних множин (сортування), як приклад, - у порядку збільшення або зменшення. Розглянемо декілька методів внутрішнього сортування, коли число елементів, що підлягають сортуванню, достатньо мало, так що весь процес можливо здійснити в оперативній пам'яті ЕОМ (звідси і назва - внутрішнє сортування ):












Алгоритми сортування базуються на одному з наступних підходів:

Швидкість алгоритму залежить від багатьох факторів. При цьому, на звичай, враховують число порівнянь. Найпростіші алгоритми вимагають порядку N2 порівнянь, а кращі - використають N log2 N порівнянь. Існує кулька десятків різних методів сортувань. Кожен метод має свої переваги й недоліки, тому той самий метод може бути ефективним для одних даних і непридатним для інших.

Сортування вставками

Найпростіше сортування вставками відноситься до найбільш очевидних.

Блок-схема алгоритму: Фрагмент програми:





Program new;

Uses forms;


const n=200;

var a : array [1..n] of integer;

k : integer;

i, n, j : byte;

begin

{ введення елементів масиву А }

…………………………………..

for j : = 2 to n do

begin

i : = j-1;

k : = a[j] ;

while (i>0) and (k <= a[i]) do

begin

a[i+1] : = a[i];

i : = i –1;

end;

a[i+1] : = k;

end;

{ друк упорядкованого масиву А}

…………………………………………

end.

Масив ai , (i = 1, n) розміщається на тім же місці, після сортування впорядковуються по зростанню. Порівнюємо поточний елемент aj з aj-1 , aj-2 ... доки не виявимо місце між ai і ai+1 , куди потрібно вставити елемент aj. Тоді елементи ai+1 ... aj-1 просунемо на одне місце вперед (вверх) і помістимо новий елемент aj на ai+1 місце. Зручно поєднувати операції порівняння і переміщення, тому що елемент aj як би «проникає» на відведений йому рівень. Такий спосіб часто називають просіванням або зануренням.
Обмінне сортування методом «бульбашки»

Порівнюються між собою кожні сусідні елементи масиву і, у разі потреби, міняються місцями, тобто «найлегший» елемент, якби, спливає на поверхню. Потім цей рівень не розглядається, а оглядається рівень з другого до останнього, і знов найлегший із елементів, які залишились, спливає, і т.д.
Блок-схема алгоритму: Текст програми:




Begin

введення масиву

SL : = N;

Repeat

t : = 0;

for j : = 1 to SL-1 do

if a[j] > a[j+1] then

+ _ begin

buf : = a[j+1];

+ a[j+1] : = a[j];

a[j] : = buf;

змінюємо місцями сусідні елементи

t : = j;

end;

номер впорядкованого рівня

SL : = t;

Until t = 0;

Вивід упорядкованого масиву


Сортування за допомогою вибору

Сортування за допомогою вибору зводиться до наступного:

  1. Знайти найменший (або найбільший) елемент. Запам'ятати його порядковий номер і поміняти місцями з першим елементом.

  2. Знов продивитись елементи, починаючи, з другого до n і повторити вибір найменшого (найбільшого) елемента і, відповідно, змінити їх місцями, і т.д., поки не будуть впорядковані всі n елементів.


Блок-схема алгоритму: Текст програми:




Begin

ввід масиву

……………………………………

for i : =1 to n-1 do

begin

початкове значення min

min : = a[i] ;

k : = i ; for j : = i + 1 to n do if min > a[j] then

_ begin

+ min : = a[j] ;

k : = j ;

end;

a[k] : = a[i] ;

a[i] : = min ;

end ;

вивід впорядкованого масиву

end.


Сортування злиттям
Злиття означує об'єднання двох або більше послідовностей (масивів) в одну впорядковану послідовність.

Розглянемо більш детально алгоритм двохшляхового злиття.

Дано два впорядкованих масиви xi , i=1, n, yj , j=1, m. Отримати масив Zk, k=1, n+m.

  1. Визначаємо найменший елемент xi і yj .

  2. Порівнюємо найменші елементи і обраний найменший елемент записуємо в Z, виключаючи його з відповідного масиву (наприклад xi ).

  3. Відшукуємо новий min у масиві xi і порівнюємо його з min yj .

  4. Записуємо обраний min в Z і виключаємо його з відповідного масиву, і т.д. поки всі елементи xi й yj не будуть записані в Z.

Методи роботи з структурами «дерево»



Структура „дерево” є узагальненням лінійного списку. В списку кожен вузол має показник на другий вузол. В дереві, кожен вузол містить декілька показників на декілька вузлів. Якщо показника два (правий і лівий), таке дерево називається бінарним. Один із показників може бути рівним Nil. Якщо правий і лівий показник рівний Nil , такій вузол називається лист. Початкова точка дерева називається кореневим вузлом.

У кореневого вузла немає гілок які в нього входять, є тільки ті, що виходять з нього. Вершина, до якої виходить показник із другої вершини, називається потомком цієї вершини. Вершина, із якої виходить показник до другої вершини, називається предком.

Приклад структури «дерево».



В бінарному дереві часто притримуються згоди про те, що у всіх лівих вершинах повинні знаходитися менші за значенням елементи , а в правих – більші.

Основні операції над елементами дерева :

1. Занесення елементів в дерево.

2. Видалення елементів з дерева.

3. Обхід дерева.
Приклад опису структури «дерево»:

type tree = ^elem ; { показник на елемент дерева }

elem = record

info : integer; { інформаційне поле елемента дерева }

left : tree; { адресне поле елемента дерева –показник на лівого потомка }

right : tree; { адресне поле елемента дерева –показник на правого потомка}

end;

var beg : tree ; { показник на кореневий елемент (вузол) дерева }


Далі розглянемо основні операції зі структурою «дерево».
1. Занесення елементів в дерево.

procedure insert ( x : integer ; var beg : tree ) ;

var P, p1, P2 : tree ;

begin

New( P );

P^. info := x;

P^. left := Nil;

P^. right := Nil;

if ( beg = Nil ) then beg := P

else

begin

p1 := beg;

while p1<>Nil do

begin

P2:=p1;

if x
then p1 := p1^. left

else p1 := p1^. right;

end;

if x < P2^. info then p2^. left := p

else p2^. right := p;

end;

end;

2. Обхід дерева.
2.1 Одержання мінімального значення в дереві
function Getmin ( beg : tree) : integer ;

var p : tree ;

begin

p := nil;

while beg <> Nil do

begin

p := beg ;

beg := beg^. left ;

end;

if p = nil then begin

writeln ('derevo pustoe');

Getmin := -1 ;

end

else Getmin := P^. info ;

end;
2.2 Одержання максимального значення
function Getmax ( beg : tree ) : integer ;

var p : tree;

begin

p := nil;

while beg <> Nil do

begin

p := beg ;

beg := beg^. right ;

end;

if p = nil then begin

writeln ('derevo pustoe');

Getmax := -1;

end

else Getmax := P^. info;

end;

Бінарний пошук



Якщо масив невпорядкований, то використовується метод простого перебору всіх його елементів. На практиці досить часто здійснюється пошук у масиві, елементи котрого впорядковані за деяким критерієм. Для пошуку в таких масивах використовуються більш вдосконалені методи, один з них – метод бінарного пошуку, коли на першому кроці обирається середній елемент впорядкованого по зростанню масиву, з яким порівнюється зразок.

Можливі наступні результати порівняння:

1) Середній елемент дорівнює зразку завдання вирішене.

2) Середній елемент < зразка пошук буде продовжено у верхній (правій) частині масиву.

3) Середній елемент > зразка пошук буде продовжено у лівій частині масиву.

В двох останніх випадках знов обирається середній елемент, але вже із обраної частини масиву. Цей процес повторюється поки не буде знайдено елемент або не будуть переглянуті всі елементи.
Блок-схема алгоритму:




_




Методичні вказівки з виконання та оформлення лабораторної роботи



Згідно до навчального плану студентам необхідно виконати чотири завдання по темі 1.

Звіт повинен включати наступні частини:

  1. Теоретична частина. (Необхідно вивчити заданий у вашому варіанті метод сортування або пошуку).

  2. Блок-схема алгоритму розв’язання завдання.

  3. Програма мовою Pascal, яка відповідає розробленому в попередньому пункті алгоритму.

  4. Результат роботи програми. (Результат повинен включати вивід на печатку/екран номеру варіанта, кількості елементів масиву, первісний масив, відсортований масив, кількість порівнянь та кількість переміщення).

  5. Після виконання 4 робіт 1 теми необхідно скласти порівняльну характеристику методів за швидкістю сортування.

  6. Список використаної літератури.

Студенти повинні строго дотримуватися свого варіанту, який вказаний викладачем.

Зміст завдань слід переписувати повністю, а розв’язання має супроводжуватись поясненнями. Лабораторна робота виконується тільки після вивчення відповідних розділів курсу. Рішення завдань повинні бути записані акуратно, з необхідними поясненнями, кресленнями та рисунками. Лабораторні роботи виконуються в термін, вказаний у графіку, але не пізніше, ніж за 5 днів до початку кожного модуля.

Робота, яка виконана з порушеннями вказаних вимог, не зараховується і повертається студенту для переробки. Студент, що не виконав хоча б одну лабораторну роботу, до модуля та екзамену не допускається.
ЗАВДАННЯ ДО ТЕМИ 1.
Лабораторна робота №1 «Методи роботи зі списками»



Варіант 1

Створити файл, що складається з цілих чисел. Скласти підпрограму для створення списку з елементів файлу.



Варіант 2


Даний список А, що складається із записів: перше поле - дійсне число, друге - адреса наступного елементу. Скласти програму для вставки нового елементу Е1перед першим входженням елементу Е, якщо елемент є в списку А.

Варіант 3


Даний список В, що складається із записів: перше поле – слова з 10 літер, друге - адреса наступного елементу. Скласти підпрограму для видалення останнього елементу списку.



Варіант 4


Даний літеральний файл. Скласти підпрограму друку вмісту файлу в зворотному порядку.



Варіант 5


Дані два списки: А1 – перше поле - від’ємне число,

А2 – перше поле – додатне число.

Скласти підпрограму, яка додає в кінець списку А1 всі елементи списку А2.



Варіант 6


Даний список А, що складається із записів: перше поле - ціле число, друге - адреса наступного елементу. Скласти підпрограму для заміни всіх чисел рівних числу 10 на число У.



Варіант 7


Даний список С, що складається із записів: перше поле - літера, друге - адреса наступного елементу. Скласти програму для перевірки впорядкованості елементів в зворотному порядку.



Варіант 8


Даний файл, що складається з цілих чисел. Скласти підпрограму для створення списку з елементів файлу в зворотному порядку(використовуючи списки).

Варіант 9


Даний список А, що складається із записів: перше поле - дійсне число, друге - адреса наступного елементу. Скласти програму для вставки нового елементу Е1перед останнім входженням елементу Е, якщо елемент є в списку А.

Варіант 10


Даний список В, що складається із записів: перше поле – слова з 10 літер, друге - адресу наступного елементу. Скласти підпрограму для видалення п'ятого елементу списку.



Варіант 11


Даний літеральний файл. Скласти програму друку вмісту файлу в прямому порядку(використовуючи списки).

Варіант 12


Дані два списки: А2 – перше поле - від’ємне число,

А1 – перше поле – додатне число.

Скласти підпрограму, яка додає в кінець списку А1 перший і останній елементи списку А2.



Варіант 13


Даний список А, що складається із записів: перше поле - дійсне число, друге - адреса наступного елементу. Скласти підпрограму для обчислення кількості додатних значень списку.



Варіант 14


Даний список Р, що складається із записів: перше поле - літера, друге - адреса наступного елементу. Скласти підпрограму для перевірки впорядкованості елементів по спаданню кодів літерів.



Варіант 15


Даний файл, що складається з цілих чисел. Скласти підпрограму для створення списку з парних значень елементів файлу.



Варіант 16


Даний список А, що складається із записів: перше поле - число, друге - адреса наступного елементу. Скласти підпрограму для друку номерів непарних значень списку.



Варіант 17


Даний список В, що складається із записів: перше поле – слова з 10 літер, друге - адреса наступного елементу. Скласти підпрограму для видалення першого елементу списку, що починається на букву Ф.

Варіант 18


Даний літеральний файл. Скласти програму створення списку з вмісту файлу в зворотному порядку.

Варіант 19


Дані два списки: А1 – перше поле - від’ємне число,

А2 – перше поле – додатне число.

Скласти підпрограму, яка додає в кінець списку А1 всі елементи списку А2, зі значенням більшим за 3.

Варіант 20


Даний список А, що складається із записів: перше поле - дійсне число, друге - адреса наступного елементу. Скласти програму для створення нового списку з всіх елементів, зі значенням більшим за число Х, потім менших числа У.

Варіант 21


Даний список К, що складається із записів: перше поле - літера, друге - адреса наступного елементу. Скласти підпрограму для обчислення кількості цифр серед елементів списку.

Варіант 22


Даний файл, що складається з цілих чисел. Скласти підпрограму для створення списку з від’ємних елементів файлу.

Варіант 23


Даний список А, що складається із записів: перше поле - дійсне число, друге - адреса наступного елементу. Скласти підпрограму для вставки нового елементу Е1 після першого входження елементу Е, якщо елемент є в списку А.

Варіант 24


Даний список В, що складається із записів: перше поле – слова з 10 літер, друге - адресу наступного елементу. Скласти підпрограму для видалення третього елементу списку.

Варіант 25


Даний літеральний файл. Скласти програму створення списку з голосних букв файлу і друку вмісту файлу.

Варіант 26


Дані два списки: А1 – перше поле – числа,

А2 – перше поле – літера арифметичних операцій.

Скласти програму, яка додає в кінець списку А2 всі елементи списку А1.

Варіант 27


Дані два списки: А2 – перше поле - від’ємне число,

А1 – перше поле – додатне число.

Скласти підпрограму, яка додає в початок списку А2 другий елемент списку А1.

Варіант 28


Даний список А, що складається із записів: перше поле - дійсне число, друге - адреса наступного елементу. Скласти програму для обчислення кількості непарних значень списку.

Варіант 29


Даний список З, що складається із записів: перше поле - літера, друге - адреса наступного елементу. Скласти підпрограму для обчислення кількості знаків арифметичних операцій серед елементів списку.



Варіант 30


Даний файл, що складається з натуральних чисел. Скласти програму для створення списку з значень елементів файлу, з значеннями від 10 до 100.


Лабораторна робота №2 «Стандартні внутрішні методи сортування масивів»
Завдання.

Створити вектор А, використовуючи генератор випадкових чисел. Кількість елементів масиву розраховується за формулою n = 80 + 2i, де i – номер варіанту. Відсортувати отриманий масив. Додаткові дані наведені в таблиці по варіантах.




Номер


варіанту



Тип

елементів масиву


Метод

сортування


Тип

сортування

1

дійсний

вставкою

по незменшенню

2

цілий

вибором

по зменшенню

3

натуральний

вибором

по зростанню

4

символьний

вставкою

по незростанню

5

строковий

вставкою

по зростанню довжини

6

строковий

вибором

по алфавіту

7

символьний

вибором

по зростанню

8

натуральний

вставкою

по незростанню

9

цілий

вибором

по незменшенню

10

дійсний

вставкою

по зростанню

11

цілий

вибором

по незростанню

12

натуральний

вибором

по зменшенню

13

символьний

вставкою

по незменшенню

14

строковий

вибором

по зменшенню довжини

15

цілий

вибором

по зростанню

16

дійсний

вставкою

по зменшенню

17

натуральний

вибором

по незменшенню

18

символьний

вставкою

по зменшенню

19

строковий

вибором

проти алфавіту

20

символьний

вибором

по незростанню коду

21

строковий

вставкою

по незростанню довжини
  1   2   3   4   5   6


Міністерство освіти і науки України
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации