Рекурсія. Рекурсивні процедури і функції

Міністерство освіти і науки України

Центральноукраїнський національний технічний університет

Механіко-технологічний факультет

Кафедра кібербезпеки та програмного забезпечення

Звіт

з виконаної лабораторної роботи № 2

дисципліни “ Технології розробки алгоритмів ”

на тему

“ Рекурсія. Рекурсивні процедури і функції ”

Виконав

студент академічної

групи КІ-15

Корнійчук С. Ю.

Перевірив

Викл.

Гермак В.С.

Кропивницький – 2017

Лабораторна робота №2

Тема: Рекурсія. Рекурсивні процедури і функції

Мета: Розглянути поняття рекурсії, дослідити доцільність застосування рекурсивних алгоритмів та заміну рекурсивних алгоритмів ітеративними

Хід роботи

Варіант 3

Завдання:

1) Напишіть рекурсивну підпрограму визначення кількості цифр натурального числа.

2) Запрограмуйте рекурсивний алгоритм розв'язання задачі про Ханойські вежі. Ця задача полягає в наступному:

Є три стержня і n дисків різного розміру. Диски можна надівати на стержні, утворюючи з них вежі. Спочатку всі диски в спадаючому порядку розташовані на стержні A. Задача полягає в тому, щоб перенести n дисків зі стержня А на стержень С, зберігши їх початковий порядок. При перенесенні потрібно керуватись наступними правилами:

а) На кожному кроці зі стержня на стержень переноситься рівно один диск;

б) Диск не можна класти на диск меншого розміру;

в) Для тимчасового зберігання можна використовувати стержень B.

Вежу зручно розглядати як таку, що складається з одного верхнього диску і вежі, утвореної іншими дисками.

[pic 1]

Завдання 1

Лістинг

def find_number_of_digits(number):

    if number < 0:

        number = -number

    if number <= 0:

        return 0

    return 1 + find_number_of_digits((number - number % 10)/10)

n = 0

while True:

...