Слободской государственный колледж педагогики и социальных отношений. Специальность: 230115 Программирование в компьютерных системах

Практическая работа №6

Специальность: 230115 Программирование в компьютерных системах.

Дисциплина: Теория алгоритмов.

Тема: Создание рекурсивных алгоритмов.

Цель работы:

1. Учиться применять рекурсивный метод решения задач

2. Учиться строить рекурсивные алгоритмы.

Ход работы

Упражнения 1 группы

Перевод десятичного натурального числа в двоичное

Напишите сценарий, который для любого натурального числа строит его двоичное представление.

Опишите функцию recbin, которая получает в качестве параметра целое положительное число n, и формирует строку, являющуюся двоичным представлением n. Эту задачу можно свести к самой себе. Если в двоичном представлении n содержится k>o двоичных цифр, то первые k-i цифр представляют число, являющееся частным от деления n на 2, а последнюю цифру легко узнать, проверив четность числа n. Если к=1, то n=1, то и двоичное представление n равно 1, и этот случай рассмотрим отдельно. В теле функции recbin есть обращение к ней самой, но с другими, более простыми параметрами. При каждом вызове функции значение параметра уменьшается, поэтому наступит момент, когда параметр станет равным 1 и решение задачи будет тривиальным.

Вычисление факториала рекурсивным методом

Напишите программу, которая по любому натуральному nвычисляет n!

Опишите рекурсивную функцию вычисления факториала. В функции один параметр — натуральное число n. Тривиальный случай — это вычисление значения 1!. Заметим, что верно следующее соотношение n! = n * (n — 1)!, поэтому можно свести задачу вычисления n!к решению той же задачи, но с другим, более "простым" параметром

Определение чисел Фибоначчи рекурсивным методом

Напишите рекурсивную функцию, определяющую число Фибоначчи с номером n. По определению последовательности чисел Фибоначчи:

f₀ = f₁ = 1;

f_i = f_i - 1 + f_i - 2 при i >= 2.

Вычисление наибольшего общего делителя

Напишите программу, которая для двух заданных натуральных чисел определяет их наибольший общий делитель.

Рекурсивная функция nod имеет два параметра — числа n и m. Будем считать, что n>m. Если это не так, то параметры можно поменять местами. Если m = 0, то задача решена, наибольший общий делитель совпадает со значением n. Сведение задачи к подзадаче основано на следующем соотношении:

nod(n,m)=nod(m,n mod m)

Первый и второй параметры уменьшаются при каждом рекурсивном вызове, поэтому наступит момент, когда значение второго параметра станет равным о.