Категорії «Рекурсія»

Пошук найкоротшого шляху

Зазвичай завдання пошуку шляху на графі формулюється так: знайти найкращий маршрут. під найкращим маршрутом, як правило, розуміють найкоротший. Знайти найкоротший маршрут можна вибором з усіх знайдених. Однак зовсім не обов’язково шукати всі маршрути. Можна вчинити інакше: під час вибору черговий точки перевірити, чи не перевищить довжина формованого маршруту довжину вже знайденого шляху, якщо ця точка …

Пошук шляху

Механізм рекурсії вельми ефективний при програмуванні задач пошуку. В якості ще одного прикладу розглянемо задачу пошуку шляху між двома містами. Якщо кілька міст з’єднані дорогами, то очевидно, що потрапити з одного міста в інший можна різними маршрутами. Завдання полягає в знаходженні всіх можливих маршрутів. Карта доріг між містами може бути зображена у вигляді графа – …

Крива Гільберта

Наступна програма викреслює в діалоговому вікні криву Гільберта. На рис. 12.7 наведені криві Гільберта першого, другого і третього порядків. Якщо придивитися, то видно, що крива другого порядку виходить шляхом з’єднання прямими лініями чотирьох кривих першого порядку. Аналогічним чином виходить крива третього порядку, але при цьому в якості “цеглинок” використовуються криві другого порядку. Таким чином, щоб …

Пошук файлів

Як приклад використання рекурсії розглянемо задачу пошуку файлів. Нехай потрібно отримати список всіх файлів, наприклад, з розширенням bmp, які знаходяться в зазначеному користувачем каталозі і у всіх підкаталогах цього каталогу. Словесно алгоритм обробки каталогу може бути представлений так: 1. Вивести список всіх файлів задовольняють критерію запиту. 2. Якщо в каталозі є підкаталоги, то обробити кожен …

Поняття рекурсії

Рекурсивний називається об’єкт, частково складається або визначається за допомогою самого себе. Факторіал – це класичний приклад рекурсивного об’єкта. Факторіал числа п – це твір цілих чисел від 1 до п. Позначається факторіал числа п так: n !. Згідно з визначенням n! = 1 х 2 х 3 х … х (п – 1) х п …