Задание на L11

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

Тема: «Рекурсивні алгоритми»

Теоретичні відомості

Рекуррентность - это рекурсивное определение функции. Они широко распространены в математике. Возможно, наиболее знакомая из такого рода функций - это факториал. Факториал - это произведение натуральных чисел от единицы до какого - либо данного натурального числа.

Значения функции факториал задаются выражением: 0!=1, n=n*(n-1)!. Они образуют множество {1,2,6,…}:

0!=1, 1=1*0!, 2=2*1!, 6=3*2! и т.д.

Все его элементы, кроме первого, определяются рекурсивно.

Как видим, функция факториал задаётся рекуррентным соотношением порядка 1 и начальным отрезком 0!=1. Вообще, любое рекуррентное соотношение порядка k вместе с заданием первых k элементов последовательности является примером рекурсивного определения.

В рекурсивном определении не должно быть “заколдованного круга”, когда объект определяется с помощью себя самого или с помощью других, но заданных через него же.

Пример

“У попа была собака, поп её любил, она съела кусок мяса, поп её убил, в землю закопал и на камне написал, что у попа…” и т.д. Эта печальная история не имеет конца, и нельзя сказать, что же именно поп написал на камне.

Чтобы подобная “бесконечность” не возникала в рекурсивном определении, должны выполняться следующие условия:

1. множество определяемых объектов является частично упорядоченным;

2. каждая убывающая по этому упорядочению последовательность элементов заканчивается некоторым минимальным элементом;

3. минимальные элементы определяются нерекурсивно;

4. неминимальные элементы определяются с помощью элементов, которые меньше их по этому упорядочению.

Если процедура р содержит явное обращение к самой себе, то она называется явно рекурсивной. Если процедура р содержит обращение к некоторой процедуре q, которая в свою очередь содержит прямое или косвенное обращение к р, то р - называется косвенно рекурсивной.

Но рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом, в программе (функции) должен присутствовать еще один важный элемент - так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс.

Что необходимо знать для реализации рекурсивного процесса? Со входом в рекурсию осуществляется вызов метода, а для выхода необходимо помнить точку возврата, т.е. то место программы откуда мы пришли и куда нам нужно будет возвратиться после завершения метода. Место хранения точек возврата называется стеком вызовов и для него выделяется определенная область оперативной памяти. В этом стеке запоминаются не только адреса точек возврата, но и копии значений всех параметров. По этим копиям восстанавливается при возврате вызывающий метод. При развертывании рекурсии за счет создания копий параметров возможно переполнение стека. Это является основным недостатком рекурсивного метода. С другой стороны, рекурсивные методы позволяют перейти к более компактной записи алгоритма.

Следует понимать, что любой рекурсивный метод можно преобразовать в обычный метод. И практически любой метод можно преобразовать в рекурсивный, если выявить рекуррентное соотношение между вычисляемыми в методе значениями.

Использование рекурсивных подпрограмм требует осторожности и умения оценить возможную глубину рекурсии и общее количество вызовов. Не всегда стоит писать рекурсивные подпрограммы непосредственно по рекурсивному определению. Дело в том, что выполнение каждого вызова подпрограммы требует дополнительных действий компьютера. Поэтому циклический вариант описания вычислений выполняется, как правило, быстрее рекурсивного. Также не следует употреблять рекурсию для вычисления элементов рекуррентных последовательностей. При большой глубине рекурсии это вообще может привести к исчерпанию автоматической памяти и аварийному завершению программы.

Индивидуальные задания

Содержание отчета

1. Тема, короткие теоретические сведения.

2. Задание согласно варианта.

3. Блок-схема.

4. Текст программы.

5. Результат работы программы (скриншоты).

6. Выводы.

1. Составить рекурсивную программу, которая выводит все представления позитивного целого числа n в виде суммы последовательностей невозрастающих целых позитивных элементов.

2. Разработать рекурсивный метод, который по заданному натуральному числу N (N1000) выведет на экран все натуральные числа не больше N в порядке возрастания. Например, для N=8, на экран выводится 1 2 3 4 5 6 7 8.

3. Скласти програму, яка подає всі зростаючі послідовності довжиною k, елементами яких є натуральні числа від 1 до n. Використати рекурсію.

4. Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками. Разрешена только рекурсия и целочисленная арифметика.

Ввод	Вывод
179	9 7 1

5. Дано натуральне число N. Виведіть усі його цифри по одній, в звичайному порядку, розділяючи їх пропусками або новими рядками. Дозволена тільки рекурсія і цілочисельна арифметика.

Ввод	Вывод
179	1 7 9

6. Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное.

Ввод	Вывод
2	YES
4	NO

задача сама по себе нерекурсивна, т.к. проверка числа n на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.

7. Разработать рекурсивный метод для вывода на экран всех возможных разложений натурального числа n на множители (без повторений). Например, для n=12 на экран должно быть выведено:

2*2*3=12

2*6=12

3*4=12

8. Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO.

Ввод	Вывод
radar	YES
yes	NO

9. Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.

В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

Ввод	Вывод
3 1 2 0	3 1

10. Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите первое, третье, пятое и т.д. из введенных чисел. Завершающий ноль выводить не надо.

В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

Ввод	Вывод
7 2 9 5 0	7 9

11. Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите наибольшее значение числа в этой последовательности.

В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Ввод	Вывод
1 7 2 4 0	7

12. Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите среднее значение элементов этой последовательности (без учета последнего нуля).

В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке.

Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Ввод	Вывод
1 7 9 0	5.666666666666667

13. Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности, то есть элемента, который будет наибольшим, если из последовательности удалить наибольший элемент.

В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.

Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).

Ввод	Вывод
1 7 9 0	7
1 2 2 1 0	2

14. Дано натуральное четное число n. Разработать рекурсивный метод для вывода на экран следующей картинки:

*********	(0 пробелов, n звездочек)
********	(1 пробел, n-1 звездочка)
*******	(2 пробела, n-2 звездочки)
…
*	(n-1 пробел, 1 звездочка)

15. Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.

В этой задаче нельзя использовать глобальные переменные и параметры, передаваемые в функцию. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметров.

Ввод	Вывод
1 0 1 0 0 1	2

16. Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...

По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом for.

Ввод	Вывод
2	1 2
5	1 2 2 3 3

17. Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. Запись натурального числа не может начинаться с цифры 0.

В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции.

Ввод	Вывод
3 15	69

18. Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.

Ввод	Вывод
2 2	3

19. Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.

Ввод	Вывод
5 1	5 4 3 2 1

20. Написать функцию Аккермана A(m,n), определенную следующим образом:

21. Написать функцию C(m,n) вычисления биномиальных коэффициентов по следующей формуле:

при 0<m<n.

22. Написать функцию умножения двух чисел, используя только операцию сложения.

23. Разработать рекурсивный метод для вывода на экран стихотворения:

10 лунатиков жили на луне

10 лунатиков ворочались во сне

Один из лунатиков упал с луны во сне

9 лунатиков осталось на луне

9 лунатиков жили на луне

9 лунатиков ворочались во сне

Один из лунатиков упал с луны во сне

8 лунатиков осталось на луне

…...

И больше лунатиков не стало на луне

24. Задан набор слов. Построить из них любую цепочку таким образом, чтобы символ в конце слова совпадал с символом в начале следующего.

25. Задан массив целых. Построить из них любую последовательность таким образом, чтобы последняя цифра предыдущего числа совпадала с первой цифрой следующего.

26. Для данного n напечатайте коэффициенты разложения полинома (1 + x)n.

27. Вычислить, используя рекурсию, выражение

28.Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае. Операцией возведения в степень пользоваться нельзя!

Ввод	Вывод
8	YES
3	NO

29.Напишіть рекурсивну функцію визначення найбільшого загального дільника двох цілих чисел. Алгоритм Евкліда.