Вступ у програмування та алгоритми

Навіщо вчити програмування?

Уявіть: ви відкриваєте сайт з вакансіями і бачите, що програмісти — одні з найбільш запитуваних і високооплачуваних спеціалістів. Але чому? Відповідь проста — попит на кваліфікованих програмістів значно перевищує пропозицію. Програмування — це не просто «знання слів якоюсь мовою». Це спосіб мислення, вміння розкладати складні задачі на прості кроки та давати комп'ютеру чіткі інструкції.

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

Коротка подорож в історію

Перш ніж писати код, варто знати, як ми дійшли до сучасних мов програмування. Ця подорож — від механічних пристроїв до C++ — допоможе зрозуміти, чому мови програмування влаштовані саме так.

timeline
    title Еволюція програмування
    section Механічна ера
        1804 : Жаккар — перфокарти для ткацького верстата
        1890 : Голлеріт — табулятор (майбутня IBM)
    section Теоретичні основи
        1936 : Тюрінг — «Машина Тюрінга»
        1941 : Цузе — комп'ютер Z3 (двійкова система)
    section Перші комп'ютери
        1945 : ENIAC — перший електронний комп'ютер
        1948 : «Марк-1» — перша програма в пам'яті
        1949 : EDSAC — поява «асемблера»
    section Мови високого рівня
        1957 : Фортран — перша «справжня» мова
        1963 : Бейсік
        1970 : Паскаль (Ніклаус Вірт)
        1972 : Мова Сі (Денніс Рітчі)
    section Сучасна ера
        1983 : C++ (Б'ярн Страуструп)
        1995 : Java (Sun Microsystems)
        2001 : C# (Microsoft)

Ключові віхи

Перше знайомство з алгоритмами

Що таке алгоритм?

Щодня ми стикаємося з алгоритмами, навіть не усвідомлюючи цього. Ранковий ритуал, рецепт приготування страви, інструкція зі складання меблів — все це алгоритми.

Розглянемо простий приклад — приготування яєчні:

При виконанні цієї послідовності ми отримаємо гарячий сніданок. Але що станеться, якщо поміняти місцями кроки 2 і 3 — налити масло, а потім поставити пательню? Масло опиниться на плиті, а не на пательні!

Алгоритм (algorithm) — це чітка і строга послідовність дій, яка приводить до потрібного результату.

Уявіть роботу великого заводу з виробництва автомобілів. Потрібний результат — працюючий автомобіль, а не брак. Важлива не сама наявність результату, а його якість. Невірно написаний алгоритм — як зламаний конвеєр: він виробляє брак.

Властивості алгоритму

Щоб алгоритм був надійним і працював коректно, він повинен відповідати шести ключовим властивостям:

mindmap
  root((Алгоритм))
    Результативність
      Завжди є результат
    Коректність
      Правильний результат
    Точність
      Однозначні дії
    Зрозумілість
      Виконавець розуміє інструкції
    Дискретність
      Окремі послідовні кроки
    Масовість
      Підходить для класу задач

Типи алгоритмів

Не всі задачі розв'язуються однаково. Залежно від структури дій, виділяють три основні типи алгоритмів:

1. Лінійний алгоритм

Лінійний алгоритм — дії виконуються строго одна за одною, без жодних відхилень.

Аналогія: Рецепт з кулінарної книги — ви чітко знаєте, який продукт брати, у якій кількості і що з ним робити.

graph TD
    A([Початок]) --> B[Крок 1]
    B --> C[Крок 2]
    C --> D[Крок 3]
    D --> E([Кінець])

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#64748b,stroke:#334155,color:#ffffff
    style C fill:#64748b,stroke:#334155,color:#ffffff
    style D fill:#64748b,stroke:#334155,color:#ffffff
    style E fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

Приклад: Обчислити площу прямокутника — зчитати довжину, ширину та перемножити їх.

#include <iostream>

int main() {
    int length, width;
    std::cout << "Введіть довжину: ";
    std::cin >> length;
    std::cout << "Введіть ширину: ";
    std::cin >> width;

    int area = length * width;
    std::cout << "Площа прямокутника: " << area << std::endl;
    return 0;
}

2. Розгалужений алгоритм

Розгалужений алгоритм — виконується вибір одного з декількох можливих шляхів залежно від умови.

Аналогія: Ви лежите на дивані. Якщо дощ припинився — йдете гуляти, інакше — дивитесь телевізор. Залежно від погоди, ви можете піти лише одним шляхом.

graph TD
    A([Початок]) --> B{Умова?}
    B -- Так --> C[Дія 1]
    B -- Ні --> D[Дія 2]
    C --> E([Кінець])
    D --> E

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#f59e0b,stroke:#b45309,color:#ffffff
    style C fill:#64748b,stroke:#334155,color:#ffffff
    style D fill:#64748b,stroke:#334155,color:#ffffff
    style E fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

Приклад: Світлофор — якщо зелений колір — продовжуємо рух, інакше — зупиняємо автомобіль.

#include <iostream>
#include <string>

int main() {
    std::string color;
    std::cout << "Який колір світлофора? ";
    std::cin >> color;

    if (color == "green") {
        std::cout << "ПРОДОВЖУЙТЕ РУХ" << std::endl;
    } else {
        std::cout << "ЗУПИНІТЬСЯ!" << std::endl;
    }
    return 0;
}

3. Циклічний алгоритм

Циклічний алгоритм — повтор одних і тих самих дій, поки виконується певна умова.

Аналогія: Садівник заповнює клумбу квітами. Для кожної квітки: викопати ямку → полити → посадити → засипати землею. І так доти, доки не засадить усю клумбу.

graph TD
    A([Початок]) --> B{Умова циклу?}
    B -- Так --> C[Дія]
    C --> B
    B -- Ні --> D([Кінець])

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#f59e0b,stroke:#b45309,color:#ffffff
    style C fill:#64748b,stroke:#334155,color:#ffffff
    style D fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

Приклад: Друкувати «Привіт» 10 разів — повторювати дію, поки лічильник не досягне 10.

#include <iostream>

int main() {
    for (int i = 1; i <= 10; i++) {
        std::cout << i << ". Привіт, kostyl.dev!" << std::endl;
    }
    return 0;
}

Що бачить комп'ютер?

Коли ми запускаємо програму, комп'ютер не просто "виконує кроки". Він оперує пам'яттю та регістрами процесора. Вже на старті навчання важливо розуміти, як ваші змінні виглядають "під капотом".

Стан програми (Debugger)

Уявіть, що ми зупинили виконання алгоритму обчислення площі прямокутника на середині. Ось як би виглядав стан наших змінних у дебагері:

Сирі дані (Memory)

А ось так число 50 (яке у шістнадцятковій системі виглядає як 0x32) може виглядати безпосередньо в комірці оперативної пам'яті:

::

Графічний опис алгоритму: блок-схеми

Навіщо потрібні блок-схеми?

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

Блок-схема (flowchart) — графічний спосіб опису алгоритму, що складається з функціональних блоків, з'єднаних стрілками.

Елементи блок-схем

Приклад: Розгадування ребуса

Побудуємо блок-схему для простого алгоритму — розгадування ребуса, де з малюнка м'яча потрібно отримати слово «хом'як»:

graph TD
    A([Початок]) --> B[/"Визначаємо слово на малюнку — М'ЯЧ"/]
    B --> C["Відкидаємо останню літеру — Ч"]
    C --> D["Додаємо літери «ХО» та «К»"]
    D --> E[/"Відповідь — ХОМ'ЯК"/]
    E --> F([Кінець])

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#64748b,stroke:#334155,color:#ffffff
    style C fill:#64748b,stroke:#334155,color:#ffffff
    style D fill:#64748b,stroke:#334155,color:#ffffff
    style E fill:#64748b,stroke:#334155,color:#ffffff
    style F fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

Це приклад лінійного алгоритму — всі дії виконуються послідовно.

Приклад: Вовк, Коза і Капуста

Класична головоломка: фермер має перевезти вовка, козу та капусту через річку. У човні лише два місця (одне для фермера). На березі не можна залишити козу з капустою або вовка з козою.

graph TD
    A([Початок]) --> B["Перевезти козу"]
    B --> C["Повернутися за вовком"]
    C --> D["Перевезти вовка та забрати козу"]
    D --> E["Перевезти капусту"]
    E --> F["Повернутися за козою"]
    F --> G["Перевезти козу"]
    G --> H([Кінець])

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#64748b,stroke:#334155,color:#ffffff
    style C fill:#64748b,stroke:#334155,color:#ffffff
    style D fill:#f59e0b,stroke:#b45309,color:#ffffff
    style E fill:#64748b,stroke:#334155,color:#ffffff
    style F fill:#64748b,stroke:#334155,color:#ffffff
    style G fill:#64748b,stroke:#334155,color:#ffffff
    style H fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

Приклад: Світлофор (розгалужений алгоритм)

Автомобіль рухається дорогою. Водій бачить світлофор. Потрібно визначити дії водія залежно від кольору:

graph TD
    A([Початок]) --> B[/"Запитуємо колір світлофора"/]
    B --> C{Це зелений колір?}
    C -- Так --> D["Продовжуємо рух"]
    C -- Ні --> E["Зупиняємо автомобіль"]
    D --> F([Кінець])
    E --> F

    style A fill:#3b82f6,stroke:#1d4ed8,color:#ffffff
    style B fill:#64748b,stroke:#334155,color:#ffffff
    style C fill:#f59e0b,stroke:#b45309,color:#ffffff
    style D fill:#22c55e,stroke:#15803d,color:#ffffff
    style E fill:#ef4444,stroke:#dc2626,color:#ffffff
    style F fill:#3b82f6,stroke:#1d4ed8,color:#ffffff

У цьому прикладі:

• Вхідні дані — колір світлофора
• Вихідні дані — одна з двох дій (продовження руху або зупинка)
• Блок «Умова» (ромб) має два виходи — і саме тут алгоритм розгалужується

Практичні завдання

Рівень 1 — Базовий

Рівень 2 — Логічний

Рівень 3 — Творчий

Підсумок