Рекурсия

37 задач

Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.

РейтингЛюбой до 800 800–1199 1200–1599 1600+Без рейтинга

СначалаПодходящие Новые Популярные Простые Сложные

Ханойские башни#53708

Головоломка "Ханойские башни" состоит из трех колышков, пронумерованных числами 1, 2, 3. На колышек 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного колышка на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку с колышка 1 на колышек 2 за минимальное число перекладываний.

Напишите программу, которая решает головоломку для данного числа дисков n.

Входные данные
Вводится 1 число n.

Выходные данные
Необходимо вывести последовательность перекладываний в формате "Disk 1 move from 1 to 2" (диск 1 переложить c колышка 1 на колышек 2), печатая по одной инструкции в строке. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

Рекурсия

✓ 9✗ 12400лёгкаяВойти и решать

Все сочетания из n по k#47937

Даны два целых числа n и k, выведите все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Порядок элементов в одной комбинации не важен. То есть комбинация (1, 2, 3) и (3, 2, 1) считается одинаковой.
Выведите на экран все такие комбинации в лексикографическом порядке.

Входные данные
В первой строке записано целое число n, во второй - целое число k.

Ограничения

1 <= n <= 20
1 <= k <= n

Выходные данные
Выведите в лексикографическом порядке все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Каждая комбинация чисел должна выводиться в отдельной строке, числа в одной комбинации разделяются одним пробелом.

Перебор с возвратом Рекурсия

✓ 61✗ 50700средняяВойти и решать

Задача Магистра Математикуса#46766

Магистр Математикус обладает волшебными способностями, которые позволяют ему превращать положительные числа в 1 с помощью следующих операций:

Если число четное, он может разделить его на 2.
Если число нечетное, он может увеличить его на 1 или уменьшить на 1.

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

Входные данные
Программа получает на вход целое число n.

Ограничения на входные данные

1 <= n <= 2³¹ - 1

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	8	3
2	7	4

Рекурсия

✓ 16✗ 39700средняяВойти и решать

Перевод числа в десятичную систему счисления (рекурсивно)#46615

Напишите программу, которая переводит число N из системы счисления с основанием r в десятичную систему счисления.

Входные данные
Программа получает на вход два натуральных числа: N и r (2 <= r <= 9). Гарантируется, что число N является правильной записью числа в системе счисления c основанием r (то есть содержит цифры от 0 до r-1).

Выходные данные
Выведите на экран число в десятичной системе счисления.

Примеры

№	Входные данные	Выходные данные
1	`100 2`	`4`

Информатика Рекурсия Системы счисления

✓ 224✗ 527600лёгкаяВойти и решать

Степень двойки (рекурсивно)#46614

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

Операцией возведения в степень пользоваться нельзя!

Входные данные

Вводится натуральное число N (N < 10⁹).

Выходные данные

Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	1	YES
2	4	YES
3	5	NO

Рекурсия

✓ 119✗ 123400лёгкаяВойти и решать

Маленький Гриша научился выполнять с любым числом две операции: прибавлять к числу 3 и прибавлять к числу 5. Но, к сожалению, он еще не знает, что таким путем он не cможет из числа 1 получить любое число. Помогите Грише понять, сможет ли он из числа 1 получить число N или нет.

Входные данные

Программа получает на вход натуральное число N (N <= 200).

Выходные данные

Выведите слово YES, если число N можно получить из числа 1, или NO - в противном случае.

Примечание

Число 1 можно получить всегда, не выполняя при этом никаких действий.

Примеры

№	Входные данные	Выходные данные
1	5	NO
2	1	YES

Рекурсия

✓ 157✗ 297500лёгкаяВойти и решать

Все ПСП#39370

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 8).

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

Динамическое программирование Перебор Перебор с возвратом Рекурсия

✓ 221✗ 198700средняяВойти и решать

Площадь комнаты#38638

Требуется вычислить площадь комнаты в квадратном лабиринте.

Входные данные
В первой строке вводится число N – размер лабиринта (3 <= N <= 10). В следующих N строках задан лабиринт (‘.’ – пустая клетка, ‘*’ – стенка). И наконец, последняя строка содержит два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и что лабиринт окружен стенками со всех сторон.

Выходные данные
Требуется вывести единственное число – количество пустых клеток в данной комнате.

Примеры

№	Входные данные	Выходные данные
1	5 *** ..* ..* ..* ***** 2 4	3

Обход в глубину Рекурсия

✓ 59✗ 108700средняяВойти и решать

Быстрое возведение в степень#33680

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:
\(a^n=(a^2)^{n/2},\ при \ четном \ n, \\ a^n=a \cdot a^{n-1},\ при \ нечетном \ n.\)

Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn) .

Входные данные
Программа получает на вход вещественное число a и целое число n (a > 0, 0 <= n <= 10⁹). Каждое число в отдельной строке.

Выходные данные
Выведите \(a^n\) с точностью не менее 5 знаком после запятой.

Примеры

№	Входные данные	Выходные данные
1	2 7	128
2	1.00001 100000	2.71827

Рекурсия

✓ 2 305✗ 10 133500лёгкаяВойти и решать

Число сочетаний#33679

По данным числам n и k (0<=k<=n) вычислите \(С_n^k\) . Для решения используйте рекуррентное соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^k\).

Решение оформите в виде функции C(n, k).

Входные данные: Вводятся целые числа n и k.

Выходные данные: Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	4 2	6

Задачи на процедуры и функции Комбинаторика Рекурсия

✓ 2 905✗ 4 902400лёгкаяВойти и решать

Максимум последовательности#33647

Напишите рекурсивную функцию, которая вычисляет максимальное значение из последовательности целых чисел, поданных не её вход. Ввод заканчивается числом 0. Основная программа должна содержать вызов функции и вывод результата. Запрещено использовать циклы

Входные данные: Во входных строках записаны целые числа, по одному в каждой строке. В последней строке записано число 0.

Выходные данные: Программа должна вывести одно число – максимальное значение из всех элементов последовательности (не считая числа 0).

Примеры

№	Входные данные	Выходные данные
1	1 3 2 0	3

Рекурсия

✓ 153✗ 236500лёгкаяВойти и решать

Сумма элементов последовательности#33646

Напишите рекурсивную функцию, которая вычисляет сумму элементов последовательности целых чисел, поданных не её вход. Ввод заканчивается числом 0. Основная программа должна содержать вызов функции и вывод результата. Запрещено использовать циклы

Входные данные: Во входных строках записаны целые числа, по одному в каждой строке. В последней строке записано число 0.

Выходные данные: Программа должна вывести одно число – сумму всех элементов последовательности.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 0	6

Рекурсия

✓ 298✗ 263500лёгкаяВойти и решать

Чётные цифры#33644

Напишите рекурсивную функцию, которая считает количество чётных цифр введённого числа.
Основная программа должна содержать ввод исходных данных, вызов функции и вывод результата
Запрещено использовать циклы

Входные данные: Входная строка содержит одно натуральной число N .

Выходные данные: Программа должна вывести количество чётных цифр введённого числа.

Примеры

№	Входные данные	Выходные данные
1	123456	3
2	13579	0

Рекурсия

✓ 447✗ 402400лёгкаяВойти и решать

Функция#31902

Функция f(n) с натуральными аргументами и значениями определена так:

f(0) = 0

f(1) = 1

f(2n) = f(n)

f(2n + 1) = f(n) + f(n + 1)

Составить программу вычисления f(n) по заданному n.

Входные данные

Дано одно число n (1 <= n <= 10¹⁸).

Выходные данные

Выведите f(n).

Примеры

№	Входные данные	Выходные данные
1	10	3

Рекурсия

✓ 75✗ 412700средняяВойти и решать

Перебор строк №4#31900

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.

Ввод	Вывод
2	KK LL MM NN

(c) К.Ю. Поляков

Рекурсия

✓ 59✗ 94600лёгкаяВойти и решать

Перебор строк №3#31899

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из K букв (K<10), в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

Автор задачи: К.Ю. Поляков

Рекурсия

✓ 148✗ 204700средняяВойти и решать

Перебор строк №2#31898

В алфавите языке племени «Тумба-Юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв (n > 1), в которых вторая буква «K». Подсчитайте количество таких слов.

Примеры

№	Входные данные	Выходные данные
1	2	KK LK MK NK 4

(c) К.Ю. Поляков

Рекурсия

✓ 627✗ 1 150600лёгкаяВойти и решать

Ханойские башни#31845

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

Входные данные

Вводится натуральное число n ( 0 < n < 11).

Выходные данные

Программа должна вывести минимальный (по количеству произведенных операций) способ перекладывания пирамидки из данного числа дисков.

Примеры

№	Входные данные	Выходные данные
1	2	1 1 2 2 1 3 1 2 3

Рекурсия

✓ 301✗ 276600лёгкаяВойти и решать

Двоичные последовательности#31843

Вводится число N (1<=N<=9). Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не больше двух.

В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.

Рекурсия

✓ 354✗ 694700средняяВойти и решать

Звездочки#31842

Дана строка, содержащая только английские буквы (большие и маленькие). Добавить символ ‘*’ (звездочка) между буквами (перед первой буквой и после последней символ ‘*’ добавлять не нужно).

Входные данные

Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков.

Выходные данные

Вывести строку, которая получится после добавления символов '*'.

Примеры

№	Входные данные	Выходные данные
1	LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO	LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO

Рекурсия

✓ 632✗ 445400лёгкаяВойти и решать