ПЛАН ЗАНЯТТЯ No 17
Дата: група: Дисципліна: Алгоритми та структури даних. Тема: Сортування масивів. Метод вибору. Мета:
Методична: закріпити методику проведення лекційного заняття. Дидактична: вивчити поняття двовимірного масиву, розглянути сортування масивів методом вибору . Виховна: зміцнювати бажання вивчення дисципліни.
Вид заняття: лекційне заняття. Форми та методи проведення заняття: інформаційно- рецептивні, фронтальне опитування, викладання нового матеріалу.
Міжпредметні зв’язки:
- Дисципліни, що забезпечують: математичний аналіз, лінійна алгебра та аналітична геометрія.
- Дисципліни, що забезпечуються: алгоритмічні мови та програмування, об'єктно-орієнтоване програмування.
Науково-методичне забезпечення:
- Вирт Н. Алгоритмы и структуры данных: Пер с англ. – М.: Мир, 1989. –
360 с., ил. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
ХІД ЗАНЯТТЯ.
- Організаційний момент: перевірка відсутніх, зовнішнього вигляду,
готовності аудиторії. 2. Повідомлення теми, формування мети та основних завдань. 3. План викладання нового матеріалу: надано в конспекті лекції. 4. Актуалізація опорних знань:
- Дати визначення похідної;
- Дати визначення первісної, невизначеного інтегралу;
- Дати визначення диференціалу;
- Визначити зв’язок неперервності та диференційованості;
- Необхідні умови інтегрованості функції;
- Таблиця похідних, таблиця інтегралів основних елементарних функцій.
5. Вивчення нового матеріалу: Тема лекції: Сортування масивів. Метод вибору.
- Мотивація вивчення матеріалу: диференціальні рівняння – це основний сучасний засіб розв’язання прикладних задач, який дає змогу описати математичну модель на зрозумілій мові. Тому, сучасному студенту необхідно вміти не тільки розв’язувати основні типи звичайних диференціальних рівнянь, але моделювати за допомогою диференціальних рівнянь текстові задачі.
- План вивчення нового матеріалу: надається в конспекті лекції. 6. Виклад нового матеріалу: конспект лекції надається. 7. Закріплення нового матеріалу: обговорення окремих питань алгоритмів. 8. Підведення підсумків заняття. 9. Домашнє завдання:
Викладач М.П.Леверя
Лекція No12 Тема: Сортування масивів. Метод вибору.
План 1. Поняття двовимірного масиву . 2. Введення-виведення елементів двовимірного масиву. 3. Сортування одновимірних масивів методом перестановок.
- Поняття двовимірного масиву . Двовимірний масив - це масив, де кожному елементу ставиться у відповідність два індекси.
Для початку роботи з масивом готуємо місце в пам'яті. Для цього описуємо його, використовуючи зарезервоване слово Масив, після якого в квадратних дужках вказуємо розмірність масиву, причому враховуємо, що на першому місці вказуються індекси рядків, а на другому - стовпчиків, і обов'язково тип елементів. Опис двовимірного массиву:
<тип_елементів_масиву> Мас <Ім'я_масиву>[][]
Зверніть увагу на те, що значень у рядках або стовпчиках масиву не обов'язково буде стільки, скільки ми оголосили, але не більше. Звертання до елементу двовимірного масиву: Ім'я_масиву[<індекс_рядка>, <інд_стовпчика>]
- Введення-виведення елементів двовимірного масиву.
Під час введення масиву необхідно послідовно вводити 1-й, 2-й, 3-й і т.д. елементи масиву, аналогічним чином вчинити і при виведенні. Для роботи з масивом потрібен будь-який оператор повторення. Вочевидь, що у двовимірному масиві необхідно використовувати їх два: один цикл, внутрішній, потрібен для переходу між елементами рядка (тобто, по стовпчиках), а другий, зовнішній, - для переміщення між рядками.
Якщо в матриці кількість рядків і стовпчиків однакова, то таку матрицю називають квадратною (на відміну від звичайної прямокутної таблиці). Тільки в квадратних матрицях існують головна та бічна діагоналі.
i=1,n
j=1,m
Ввод x[i][j]
Елементи, що стоять на головній діагоналі, мають індекси (1, 1), (2, 2), (3, 3), ... (і, і). ..., (n, n), тобто номер рядка дорівнює номеру стовпчика.
Елементи, що стоять на бічній діагоналі, мають такі індекси (1, n), (2, n-1), (3, n-2), ..., (і, n+1-і), (n,1), тобто індекси елементів взаємозалежні за формулою j= n+1 - i. 3.Сортування масивів методом вибору.
Алгоритм сортування вибором: 1. Знайдемо в масиві найбільший елемент і поміняємо його місцями з
останнім елементом. 2. Повторимо алгоритм пошуку максимального елемента, зменшивши кількість переглядаються елементів на одиницю і змінимо його місцями з передостаннім елементом. 3. Описану вище операцію пошуку проводимо до повного упорядкування
елементів у масиві. Так як в блоці 9 відбувається зміна змінної n, то на початку алгоритму її значення необхідно зберегти.
Процес упорядкування елементів у масиві за зростанням
Номер елемента 1 2 3 4 5 Вихідний масив 7 3 5 4 2 Перший прогляд 2 3 5 4 7 Другий прогляд 2 3 4 5 7
Для впорядкування масиву за спаданням необхідно переміщати мінімальний елемент.
Приклад. Відсортувати масив х з n елементів в порядку зростання методом вибору.
Алгоритмічна мова Блок-схема алг Сортування вибором (нат n, дійсн Мас x[1:n])
арг. n, x рез. x поч дійсн. В, max; нат i, j, nom
Ввести n для і від 1 до n нц
Ввести x[i] кц k:=n для j від 1 до k нц max:=x[1] nom:=1 для i від 2 до n
нц якщо x[j]> max
то
max:=x
j nom:=i все кц B := x[nom] x[nom]:= x[n] x[n]:=B n:=n-1 кц для і від 1 до n нц
Вивести x[i] кц кін
поч
i:=1,n
Введення x
i
j:=1,k
i:=2,n
x
j
n
k:=n
max:=x
1
nom:=1
n:=n-1
b:=x
nom x
nom
:= x
n x
n
:=b
> max
-
+ max:=x
j nom:=i
i:=1,n
Виведення x
i
кін
5. Контрольні питання
- Поняття двовимірного масиву? 2. Як ввести двовимірний масив? 3. Як вивести двовимірний масив? 4. Алгоритм сортування масиву методом вибору.
Список літератури:
- Алтухов Е.В., Рыбалко Л.А., Савченко В.С. Основы информатики и
вычислительной техники: Учеб. пособие для учащ. средн. спец. уч. заведений. – М.: Высш. шк., 1992. – 303 с. 2. Савченко В.С. Разработка алгоритмов: от простого к сложному. Учебное
пособие для классов с углубленным изучением информатики. – Донецк, 1996 – 320 с.
Для перегляду тексту необхідно залогінитись.