ПЛАН ЗАНЯТТЯ No 15
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Сортування масивів. Метод перестановок. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: систематизувати знання та вміння з побудови алгоритмів. Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Вирт Н. Алгоритмы и структуры данных: Пер с англ. – М.: Мир, 1989. –
360 с., ил. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду,
готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій. 5. Вивчення нового матеріалу: Тема лекції: Сортування масивів. Метод перестановок.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No11 Тема: Сортування масивів. Метод перестановок.
План 1. Поняття масиву . 2. Введення-виведення елементів одновимірного масиву. 3. Сортування одновимірних масивів методом перестановок.
- Поняття масиву . Часто для роботи з безліччю однотипних даних (цілочисельними значеннями, рядками, датами і т.п.) виявляється зручним використовувати масиви. Наприклад, можна створити масив для зберігання списку студентів, що навчаються в одній групі. Замість створення змінних для кожного студента, наприклад Студент1, Студент2 і т.д., досить створити один масив, де кожного прізвища зі списку буде присвоєно порядковий номер. Таким чином, можна дати наступне визначення. Масив - структурований тип даних, що складається з фіксованого числа елементів одного типу.
Масив на малюнку 1 має 8 елементів, кожен елемент зберігає число речовинного типу. Елементи в масиві пронумеровані від 1 до 8. Такого роду масив, який представляє собою просто список даних одного і того ж типу, називають простим або одновимірною масивом. Для доступу до даних зберігаються в певному елементі масиву, необхідно вказати ім'я масиву та порядковий номер цього елемента, який називається індексом.
Мал. 1 Одномерный числовой масив Якщо виникає необхідність зберігання даних у вигляді таблиць, у форматі рядків і стовпців, то необхідно використовувати багатовимірні масиви. На малюнку 2 приведений приклад масиву, що складається з чотирьох рядків і чотирьох стовпців. Це двовимірний масив. Рядки в ньому можна вважати першим виміром, а стовпці друга. Для доступу до даних, що зберігається в цьому масиві, необхідно вказати ім'я масиву та два індекси, перший повинен відповідати номеру рядка, а другого номеру стовпця в яких зберігається необхідний елемент.
Рис. 3.2 Двумірний числовий масив 2. Введення-виведення елементів одновимірного масиву. Під час введення масиву необхідно послідовно вводити 1-й, 2-й, 3-й і т.д. елементи масиву, аналогічним чином вчинити і при виведенні. Отже, необхідно організуватицикл. Блок-схема алгоритму введення елементів масиву зображена на мал. 3.
Висновок масиву організується аналогічно вводу. Розглянемо кілька прикладів обробки масивів. Алгоритми, за допомогою яких обробляють одномірні масиви, схожі на обробку послідовностей (обчислення суми, твори, пошук елементів за певною ознакою, вибірки і т.д.). Відмінність полягає в тому, що в масиві одночасно доступні всі його компоненти, тому стає можливою, наприклад, сортування його елементів і інші, більш складні перетворення.
- Сортування одновимірних масивів методом перестановок. Сортування являє собою процес упорядкування елементів у масиві в порядку зростання або зменшення їх значень. Наприклад, масив X з n елементів буде відсортований у порядку зростання значень його елементів, якщо X1 ≤ X2 ≤ ... ≤ Xn, і в порядку убування, якщо X1 ≥ X2 ≥ ... ≥ Xn.
Сортування методом перестановок ( "бульбашки") використовує метод обмінного сортування та заснований на виконанні в циклі операцій порівняння і при необхідності обміну сусідніх елементів. Розглянемо алгоритм бульбашкової сортування:
- Порівняємо перший елемент масиву з другим, якщо перший виявиться більше
другого, то поміняємо їх місцями. 2. Ті самі дії виконаємо для другого і третього, третього і четвертого, i-го і (i +1)-го, (n- 1)-го і n-го елементів. У результаті цих дій найбільший елемент стане на останнє n-е місце. 3. Тепер повторимо даний алгоритм спочатку, але останній n-й елемент, розглядати не будемо, тому що він вже зайняв своє місце. Після проведення даної операції найбільший елемент, що залишився масиву стане на (n-1)-е місце. 4. Так повторюємо до тих пір, поки не впорядкуємо весь масив.
У табл.1 докладно розписаний процес упорядкування елементів у масиві. Для перетворення масиву, що складається з n елементів, необхідно переглянути його n-1 раз, щоразу зменшуючи діапазон перегляду на один елемент. Зверніть увагу на те, що для перестановки елементів використовується буферна змінна b, в якій тимчасово зберігається значення елемента, що підлягає заміні.
Таблиця 1. Процес упорядкування елементів у масиві за зростанням
Номер елемента 1 2 3 4 5 Вихідний масив 7 3 5 4 2 Перший прогляд 3 5 4 2 7
Другий прогляд 3 4 2 5 7 Третій прогляд 3 2 4 5 7 Четвертий прогляд 2 3 4 5 7
- Приклад. Відсортувати масив х з n елементів в порядку зростання.
Алгоритмічна мова Блок-схема алг Сортування перестановками (нат n, дійсн Мас x[1:n])
арг. n, x рез. x поч дійсн. В, i, j Ввести n для і від 1 до n нц
Ввести x[i] кц для і від 1 до n-1 нц
для j від 1 до n-i нц якщо x[j]> x[j+1],
то B := x[j+1]
x[j+1]:= x[j] x[j]:=B все кц кц для і від 1 до n нц
Ввести x[i] кц кін
поч
i:=1,n
Введення x
i
i:=1,n-1
j:=1,n-i
x
j
n
-
> x
j+1
+ B:= x
j+1 x
j+1:=
x
j x
j
:=B
i:=1,n
Виведення x
i
кін
Перевірку правильності алгоритму можна провести заповнивши трасировочну таблицю:
Шаг Операція n x[1:n] i j B Перевірка умови
1 Введення n 4
2 Введення x
i
[7 3 5 4]
3 i:=1,3 1 i:=1,3
4 j:=1,3 1 j:=1,3
5 x
j
> x
j+1
1 7> 3, так
6
B:= x
j+1 x
j+1:=
x
j x
j
[3 7 5 4]
- j:=1,3 2
8 x
j
:=B
> x
j+1
7>5, так
9
B:= x
j+1 x
j+1:=
x
j x
j
[3 5 7 4]
10 j:=1,3 3
11 x
j
:=B
> x
j+1
7>4, так
12
B:= x
j+1 x
j+1:=
x
j x
j
[3 5 4 7]
13 i:=1,3 2
14 j:=1,2 1
15 x
j
:=B
> x
j+1
3>5,ні
16 j:=1, 2 2
17 x
j
> x
j+1
5>4, так
18
B:= x
j+1 x
j+1:=
x
j x
j
[3 4 5 7]
19 i:=1,3 3
20 j:=1,1 1
21 x
j
:=B
> x
j+1
3>4,ні
22 Виведення x
i
[3 4 5 7]
- Контрольні питання
- Поняття масиву?
2. Як ввести масив? 3. Як вивести масив? 4. Що таке сортування? 5. Алгоритм сортування методом перестановок.
Список літератури:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
Для перегляду тексту необхідно залогінитись.