Algorithms 9 grade

Зміст

Тема 0. Повторення……………………………………………………………. 3

0.1. Введення та виведення у консоль……………………………….. 3

0.2. Види алгоритмів……………………………………………………………. 9

Тема 1. Одновимірні масиви…………………………………………. 13

1.1. Поняття про одновимірний масив…………………………….. 13

1.2. Перебір елементів масиву………………………………………….. 15

Практична робота №1 Елементарна робота з одновимірними масивами………………………………………………….16

1.3. Пошук у масиві………………………………………………………………18

1.4. Лінійний пошук……………………………………………………………..19

Практична робота №2 Лінійний пошук………………………………21

1.5. Бінарний пошук…………………………………………………………….23

Практична робота №3 Бінарний пошук……………………………..25

1.6. Пошук мінімуму та максимуму……………………………………..27

Практична робота №4 Пошук мінімуму та максимуму в одновимірному масиві………………………………………………………..28

1.7. Сортування одновимірних масивів……………………………..30

1.8. Сортування бульбашкою………………………………………………31

Практична робота №5 Сортування бульбашкою……………….34

1.9. Сортування вставками…………………………………………………..36

Практична робота №6 Сортування вставками……………………39

Контрольна робота №1 Одновимірні масиви та робота з ними………………………………………………………………………………………41

Тема 2. Двовимірні масиви……………………………………………..43

Тема 0.

Повторення

0.1. Введення та виведення у консоль

У мові програмування С++ для того, щоб вивести дані у консоль треба використати функцію std::cout та оператор “<<“. Так найпростіша програма, яка буде виводити строку “Hello, World!” буде виглядати наступним чином:

#include <iostream>

int main(){

std::cout << "Hello, World!" << std::endl;

}

Натомість, для введення використовується функція std::cin та оператор >>. Розглянемо, як виглядатиме проста програма, яка зчитуваме число та зберігатиме його у пам’яті.

#include <iostream>

int main(){

int a;

std::cin >> a;

}

Зверніть увагу, що для роботи цих функцій необхідно підключити бібліотеку iostream.

Завдання 1. Заповнити пропуски таким чином, щоб отримати робочу програму, яка зчитує два цілих числа a та b і виводить строку “a + b = c”, де замість a та b стоять їх значення, а замість с – сума a та b.

Завдання 2. На наступній сторінці подано філворд, де розміщено 17 ключових слів. Вам потрібно віднайти усі з них.

0.2. Види алгоритмів

Алгоритми поділяються на три основні види: лінійні, розгалужені та циклічні (див. рис.). У свою чергу розгалужені розподіляють на алгоритми з повним і неповним розгалуженням, а циклічні характеризують за видом циклу.

Завдання 3. Визначити види алгоритмів за блок-схемою.

Тема 1.

Одновимірні масиви

1.1. Поняття про одновимірний масив

(Класичне означення) Одновимірний масив являє собою послідовність елементів одного виду.

У більшості мов програмування одновимірні масиви реалізовані саме за класичним означенням. Проте є виключення, у яких елементи масиву можуть бути різного типу*.

Для тих, хто хоче знати більше:

* З точки зору інформатики така структура даних носить назву список.

Відео 1. Реалізація одновимірних масивів мовою програування С++

1.2. Перебір елементів масиву

Практична робота №1 Елементарна робота з одновимірними масивами

1.3. Пошук у масиві

Сформулюємо основну задачу, яка постає перед нами.

Задача. Знайти, чи зустрічається елемент у масиві чи ні.

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

Ми будемо розв’язувати цю задачу двома базовими алгоритмами: лінійний пошук та бінарний пошук.

1.4. Лінійний пошук

Ідея цього алгоритму є дуже простою. Треба просто взяти кожен елемент масиву і порівняти зі зразком.

До переваг цього алгоритму можна віднести простоту реалізації та спроможність працювати на невідсортованих масивах.

До недоліків відносять досить низьку швидкість роботи цього алгоритму.

Практична робота №2 Лінійний пошук

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

Практична робота №3 Бінарний пошук

1.6. Пошук мінімуму та максимуму

Практична робота №4 Пошук мінімуму та максимуму в одновимірному масиві

1.7. Сортування одновимірних масивів

1.8. Сортування бульбашкою

Відео 2. Сортування бульбашкою

Практична робота №5 Сортування бульбашкою

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

Відео 3. Сортування вставками

Практична робота №6 Сортування вставками

Контрольна робота №1 Одновимірні масиви та робота з ними

Тема 2

Двовимірні масиви