Рекурсия.
- Во всех задачах этого листка запрещается пользоваться циклами и глобальными переменными.
- В первых пяти задачах запрещается использовать переменные в рекурсивных функциях.
- Ноль присоединяется к множеству натуральных чисел.
Задачи
1.
в первых трех пунктах этой задачи разрешается использовать лишь одну рекурсивную функцию с одним параметром.
Для заданного натурального n вывести все числа от 1 до n:
- в обратном порядке.
- в прямом порядке.
- сперва в обратном порядке, а затем в прямом.
- сперва в прямом порядке, а затем в обратном, используя только дополнительную рекурсивную функцию.
- сперва в прямом порядке, а затем в обратном, используя только дополнительный параметр.
- сперва в обратном порядке, а затем в прямом только четные.
2.
- Написать рекурсивный вариант функции возведения в натуральную степень.
- Написать функцию, вычисляющую произведение двух натуральных чисел. (операцией умножения пользоваться запрещается.)
- Написать рекурсивный вариант функции возведения в натуральную степень, используя только операции прибавления и вычитания единицы (++ и — соответственно).
3.
Для заданного n вычислить n –й член последовательности Фибоначчи.
4.
Для заданного натурального n и b (1 < b < 11) вывести запись числа n в системе счисления с основанием b.
5.
- Для заданных натуральных m и n вывести прямоугольник m на n.
- Для заданного натурального n прямоугольный равнобедренный треугольник с прямым углом слева вверху и с катетами равными n.
- Для заданного натурального n прямоугольный равнобедренный треугольник с прямым углом слева внизу и с катетами равными n.
- Для заданного натурального n равнобедренный треугольник с вертикальным основанием слева, равным 2n – 1.
- Для заданного натурального n равнобедренный треугольник вершиной вниз с высотой n и основанием 2n-1.
- Такой же треугольник вершиной вверх.
Примеры:
..***********.....*******...*...........*.......*************..........*.........***********.....******....**..........**.......***********..........***........***********.....*****.....***.........***.......*********..........*****.......***********.....****......****........****.......*******..........*******......***********.....***.......*****.......***.........*****..........*********.....***********.....**........******......**...........***..........***********....***********.....*.........*******.....*.............*..........*************......................................................................................(a)........(b).........(c).......(d)...........(e)..............(f).........m=11,n=7;.....n=7;........n=7;......n=4;..........n=7;.............n=7;.....Примечание: Точки в примерах поставлены вместо пробелов исключительно из-за своеобразия формата вако-вики.
6. ("Ханойские башни")
Есть три стержня A, B, и C. На стержень A надето n дисков, причем диски отличаются размером и лежат меньший на большем. Задача состоит в том, чтобы перенести все диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, За один раз разрешается переносить только один диск, причём нельзя класть больший диск на меньший.
Написать программу, которая воспроизведет инструкцию по порядку переноса дисков. Каждая инструкция записывается в формате:
<имя стержня, откуда переносится диск> -> <имя стержня, куда переносится диск>Пример для n=2:
A -> B
A -> C
B -> C
Примечание: желательно найти два решения этой задачи: (a) с использованием дополнительной переменной; (b) с использованием дополнительного параметра
7. (необязательно)
Фракталы.
Используя какую-нибудь графическую библиотеку, постройте изображения следующих фракталов:
- треугольник Серпинского
- квадрат Серпинского
- кривая Леви
- кривая дракона
- снежинка Коха
8.
Вывести в порядке возрастания все правильные дроби со знаменателями, не превышающим заданного n.
9.
Найти число сочетаний из n по k (-1 < k < n+1 < 60)
- -1 < k < n+1 < 12
- -1 < k < n+1 < 36