У цій статті продовжимо говорити про musthave набори будь-якого гарного програміста. А ви знаєте, які цікаві алгоритми та їхні фішки дозволяють вирішувати великий спектр завдань?
- НОД та НОК
З цими поняттями мало бути всі знайомі ще зі школи. Все ж таки для визначеності нагадаємо, НОД — найбільший спільний дільник, а НОК – найменше загальне кратне.
Дані алгоритми дуже прості, проте, як показує статистика, не всі програмісти вміють їх писати ефективно. Вони зазвичай вивчаються одними з перших на курсі алгоритмів і структур даних, можливо тому не отримують належної уваги. Для тих, хто ще не встиг ознайомитися з ними чи вже встиг забути, короткий опис.
Алгоритм для пошуку НОК у принципі можна не запам'ятовувати, оскільки ми можемо висловити його через відомий НОД для тих самих двох чисел за формулою: НОК(A,C)=(AxC)/НОД (A,C).
А ось для пошуку НОД використовується алгоритм Евкліда. Полягає він у наступному:
1) більше ділимо на менше;
2) якщо ділиться без залишку, то менше і є НОД;
3) якщо є залишок, то більшу кількість замінюємо на залишок від розподілу;
4) повертаємося знову до першого пункту.
Просто, чи не так? Якщо раптом хтось все ж таки не зрозумів, скористайтеся гулом, де можна почитати докладніше.
- Графи та їх обходи
Сподіваюся, що читач знає, що таке граф (чи бодай чув про нього). Ось, якщо що, коротке пояснення.
Якщо говорити простими словами, то граф — це безліч найчастіше однотипних об'єктів, які мають якісь зв'язки. Теоретично графів ці об'єкти називають вершинами, а зв'язок між ними — ребрами.Просто уявити граф можна так: міста і дороги між ними (так-так, по суті карту будь-якої місцевості можна розглядати як графи, оскільки є вершини — точки на карті, а також ребра — дороги між ними).
До речі, графи можуть бути різними (орієнтованими й неорієнтованими, зв'язковими й ні, зваженими та незваженими, з циклами й без, і т. д.). Якщо раптом ви не знайомі з цією термінологією, то можна ознайомитись з нею хоча б на вікіпедії тут (повірте, зайвим це не буде).
Коли ви прохаєте навігатор прокласти дорогу, він знаходить найоптимальніший шлях, як?
По суті, пошук шляху на карті – певний складний алгоритм, який використовує багато даних та хитру їхню обробку, проте в його основі лежить один із простих алгоритмів пошуку найкоротшого шляху у графі. Усього існує багато різних алгоритмів на графах, але наведу внизу найголовніші, з якими рекомендую ознайомитись:
- DFS, BFS
- Алгоритм Дейкстри
- Алгоритми пошуку мінімальних остовних дерев у графі (Прима, Краскала)
- А* (для тих, хто хоче знати трохи більше)
Реалізації більшої частини цього можна знайти на порталі GeekForGeeks (https://www.geeksforgeeks.org/).
- Жадібні алгоритми
Пам'ятаєте у минулій статті йшлося про динамічне програмування (ДП)? Так ось, з жадібними алгоритмами все майже так само, як і з ДП — їх досить багато, вони вчать думати (розвивають мозок) і мають свої певні фішки, знаючи які можна вирішувати великий спектр завдань.
Тепер трохи поясню, що це за алгоритми й чому вони жадібні.
Насправді їхня ідея досить проста: ми на кожному кроці алгоритму намагаємось робити оптимальний вибір. Ось і вся суть!
Простий приклад. Припустимо нам треба дати решту на N гривень (і ми маємо необмежену кількість різних купюр номіналом: 1000, 500, 200, 100, 50, 20, 10, 5, 2 та 1). При цьому потрібно не просто дати решту, а зробити це, використовуючи мінімальну кількість купюр.
Тоді буде очевидним наступний крок: щоразу будемо по можливості вибирати купюру з найбільшим номіналом. Таким чином ми ніби відчуваємо себе жадібними (використовуємо мінімальну кількість купюр). Чи не складно, правда?
Однак, далеко не всі завдання цього класу такі прості. Той же алгоритм Краскала для пошуку мінімального остовного дерева в графі відноситься до жадібних. На тому ж GeekForGeeks є цілий розділ, присвячений жадібним алгоритмам, тому вперед!
Що ж, сподіваюся, ця стаття допоможе вам у вивченні дуже цікавого світу алгоритмів.
Успіхів!
Олег Топорков
