Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Рекурсия

Условие задачи  
ID 31839
Вычисление факториала
Темы: Рекурсия   

Составить программу с рекурсивной функцией для расчета факториала.

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

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

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

ID 31838
Сумма битов
Темы: Рекурсия   

Составить программу с рекурсивной функцией для расчета суммы битов в натуральном числе.

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

Выходные данные
Выводите сумму битов.

Примеры

Входные данные Выходные данные
1 16 1
2 7 3

ID 31837
Произведение битов
Темы: Рекурсия   

Составить программу с рекурсивной функцией для расчета произведения битов в натуральном числе.

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

Выходные данные
Выводите произведение битов.

Примеры

Входные данные Выходные данные
1 16 0
2 7 1


 

ID 31842
Звездочки
Темы: Рекурсия   

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

Примеры
Входные данные Выходные данные
1 LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO L*I*t*B*e*o*F*L*c*S*G*B*O*F*Q*x*M*H*o*I*u*D*D*W*c*q*c*V*g*k*c*R*o*A*e*o*c*X*O

ID 31841
Количество цифр
Темы: Рекурсия   

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

Примеры
Входные данные Выходные данные
1 74kz31n8pn26f2iv10c7u8x356gl73jlka67i929z08i5mnn35h0n 28

ID 31840
Наибольшая строка
Темы: Рекурсия   

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

Примеры
Входные данные Выходные данные
1 11111111 1

ID 21716
Сумма чисел от 1 до n
Темы: Рекурсия   

Напишите программу, содержащую рекурсивную функцию, которая  решает задачу нахождения суммы чисел от 1 до n (n <= 100)
Нельзя в программе использовать циклы и формулу суммы арифметической прогрессии
Основная программа должна содержать ввод исходных данных, вызов функции и вывод ответа
На вход программе подается число n

Примеры

Входные данные Выходные данные
1 5 15

ID 21723
Сумма делителей
Темы: Рекурсия   

Для данного натурального числа n вычислите сумму всех его натуральных делителей, включая 1 и само число. Решение оформите в виде РЕКУРСИВНОЙ функции с одним параметром. Основная программа должна содержать ввод исходных данных, вызов функции и вывод ответ
Запрещено использовать циклы в программе

Примеры

Входные данные Выходные данные
1 6 12

ID 21715
Степень числа
Темы: Рекурсия   

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

На вход программе подаются два числа x и n

Примеры

Входные данные Выходные данные
1 2 5 32

ID 33645
Только квадраты
Темы: Рекурсия   

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

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

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

Примеры
Входные данные Выходные данные
1 1
2
3
4
0
4 1

ID 33646
Сумма элементов последовательности
Темы: Рекурсия   

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

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

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

Примеры
Входные данные Выходные данные
1 1
2
3
0
6

ID 33647
Максимум последовательности
Темы: Рекурсия   

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

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

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

Примеры
Входные данные Выходные данные
1 1
3
2
0
3

ID 18692
Длинный НОД
Темы: Рекурсия    НОД и алгоритм Евклида   

Даны два числа. Найти их наибольший общий делитель.
 
Входные данные: Вводятся два натуральных числа, не превышающих 10^9, (запись 10^9 обозначает "10 в 9-й степени", то есть 1000000000).
Выходные данные: Выведите НОД введенных чисел

Примеры
Входные данные Выходные данные
1 42 12 6

ID 21719
Функция Аккермана
Темы: Рекурсия   

В теории вычислимости важную роль играет функция Аккермана A(m,n), определенная следующим образом:

Даны два целых неотрицательных числа m и n, каждое в отдельной строке. Выведите A(m,n).


Примеры
Входные данные Выходные данные
1 2
2
7


 

ID 31902
Функция
Темы: Рекурсия   

Функция f с натуральными аргументами и значениями определена так:
 
f(0) = 0
f(1) = 1
f(2n) = f(n)
f(2n + 1) = f(n) + f(n + 1)
Составить программу вычисления f(n) по заданному n.
 
Входные данные
Дано одно число n (1 ≤ n ≤ 1018).
 
Выходные данные
Выведите f(n)
 
Ввод Вывод
10 3

ID 31793
Функция - 2
Темы: Рекурсия   

Описана рекурсивная функции с тремя параметрами F(a, b, c):
 
если a ≤ 0 или b ≤ 0 или c ≤ 0, то F(a, b, c) = 1
если a > 20 или b > 20 или c > 20, то F(a, b, c) = F(20, 20, 20)
если a < b и b < c, то F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c)
иначе F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1)
 
Входные данные
Входные данные содержат три целых числа a, b, c - параметры функции F (-104 ≤ a,b,c ≤ 104).
 
Выходные данные
В ответе выведите значение функции F(a, b, c).
 
Ввод Вывод
1 1 1 2
2 2 2 4
10 4 6 523
50 50 50 1048576

ID 31784
Заполнение конем
Темы: Рекурсия   

Дана шахматная доска nхn. Пусть конь стоит на клетке (1,1). Необходимо найти такую последовательность ходов коня, при которой он побывает на каждой клетке доски ровно по одному разу.
 
Входные данные
На вход программе подается натуральное число n (n8).
 
Выходные данные
Если обход невозможен, то выведите в выходной файл 0, если возможен, то 1, а на следующих строчках выведите матрицу nn, иллюстрирующую порядок обхода. Выравнивать числа по столбцам не обязательно.
 
Примечание. Скорость работы рекурсивной программы в этой задаче существенно зависит от порядка, в каком будут рассматриваться варианты хода коня из очередной клетки. Одним из удачных порядков является размещение всех восьми вариантов хода "по кругу".
 
Ввод Вывод
3 0
5
1
1 20 17 12 3 
16 11 2 7 18 
21 24 19 4 13 
10 15 6 23 8 
25 22 9 14 5 

ID 31803
Разложение на слагаемые
Темы: Рекурсия   

Требуется вывести все различные представления натурального числа N в виде суммы натуральных чисел. Представления, отличающиеся друг от друга порядком слагаемых, не являются различными.
 
Входные данные
Входная строка содержит целое число N (2 ≤ N ≤ 40).
 
Выходные данные
В ответе выведите все различные представления числа N без повторов в виде суммы по одному на отдельной строке. Как слагаемые, так и сами суммы могут следовать в произвольном порядке.
 
Ввод Вывод
4
1 1 1 1
1 2 1
1 3
2 2
4
5
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
1 4
5

ID 23410
Лесенки
Темы: Рекурсия   

Лесенкой называется набор кубиков, в котором каждый более верхний 
слой содержит кубиков меньше, чем предыдущий.
 
---
| |
---------
| | | | |
-----------
| | | | | |
-----------------
| | | | | | | | |
-----------------
 
Подсчитать число лесенок, которое можно построить из N кубиков.
 
Входные данные
Во входном файле записано число N (1<=N<=100).
 
Выходные данные
В выходной файл вывести искомое число лесенок.
 
Пример
Пример входного файла
3
 
Пример выходного файла
2
 

ID 31794
Монетки
Темы: Рекурсия   

В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные
На вход программы  сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

Выходные данные
Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).
 

Ввод Вывод
100 6
11 20 30 40 11 99
3
40 30 30

ID 31795
Сумма кубов
Темы: Рекурсия   

Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов натуральных чисел. Вася решил придумать аналогичное утверждение для кубов - он хочет узнать, сколько кубов достаточно для представления любого числа. Его первая рабочая гипотеза - восемь.

Выяснилось, что почти все чиcла, которые Вася смог придумать, представляются в виде суммы не более чем восьми кубов. Однако число 239, например, не допускает такого представления. Теперь Вася хочет найти какие-либо другие такие числа, а также, возможно, какую-либо закономерность в представлениях всех остальных чисел, чтобы выдвинуть гипотезу относительно вида всех чисел, которые не представляются в виде суммы восьми кубов.

Помогите Васе написать программу, которая проверяла бы, возможно ли представить данное натуральное число в виде суммы не более чем восьми кубов натуральных чисел, и если это возможно, то находила бы какое-либо такое представление.

Входные данные
Вводится натуральное число N <= 2*109.

Выходные данные
Требуется вывести не более восьми натуральных чисел, кубы которых в сумме дают N. Если искомого представления не существует, то в выходной файл необходимо вывести слово IMPOSSIBLE.
 

Ввод Вывод
239 IMPOSSIBLE
17 2 2 1


Источник: https://informatics.msk.ru/mod/statements/view3.php?id=254&chapterid=158#1

ID 31844
Троечные последовательности
Темы: Рекурсия   

Вводится число N. Сгенерируйте в анти-лексикографическом порядке все последовательности длины N (1≤N≤9), состоящие из чисел 3, 4, 5, в которых количество троек не превосходит двух.
 
В "анти-лексикографическом" обозначает "в порядке, обратном к лексигографическому" (см. пример).
 
В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.
В анти-лексикографическом, соответственно, наоборот. 
 

Примеры
Входные данные Выходные данные
1 3
5 5 5
5 5 4
5 5 3
5 4 5
5 4 4
5 4 3
5 3 5
5 3 4
5 3 3
4 5 5
4 5 4
4 5 3
4 4 5
4 4 4
4 4 3
4 3 5
4 3 4
4 3 3
3 5 5
3 5 4
3 5 3
3 4 5
3 4 4
3 4 3
3 3 5
3 3 4
 

ID 31900
Перебор строк №4
Темы: Рекурсия   

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

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


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

ID 31899
Перебор строк №3
Темы: Рекурсия   

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию. 
 
Ввод Вывод
3 KKK
KKL
KKM
KKN
KLL
KMM
KNN
LKK
LLK
LLL
LLM
LLN
LMM
LNN
MKK
MLL
MMK
MML
MMM
MMN
MNN
NKK
NLL
NMM
NNK
NNL
NNM
NNN
28


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

ID 31898
Перебор строк №2
Темы: Рекурсия   

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


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

ID 33644
Чётные цифры
Темы: Рекурсия   

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

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

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

Примеры

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

ID 21718
Все числа от n до 1
Темы: Рекурсия   

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

Примеры

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

ID 31792
Как поделить картошку
Темы: Рекурсия   

Вася и Петя пошли копать картошку. В конце дня они накопали N мешков с картошкой весом W1, W2, ... WN. Как им поделить мешки с картошкой между собой, чтобы разница масс была минимальной.

Входные данные
В первой строке  записано число N – количество мешков (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы мешков W1, W2 , … WN (1 ≤ Wi ≤ 105).
 
Выходные данные
В единственную строку нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух куч с мешками.
 
Ввод Вывод
5
5 3 5 7 8
2

ID 31843
Двоичные последовательности
Темы: Рекурсия   

Вводится число N. Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не превосходит 2-х.
 
В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.
 
1≤N≤9

Примеры
Входные данные Выходные данные
1 3
2 2 4
2 2 5
2 4 2
2 4 4
2 4 5
2 5 2
2 5 4
2 5 5
4 2 2
4 2 4
4 2 5
4 4 2
4 4 4
4 4 5
4 5 2
4 5 4
4 5 5
5 2 2
5 2 4
5 2 5
5 4 2
5 4 4
5 4 5
5 5 2
5 5 4
5 5 5
 

ID 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

ID 33680
Быстрое возведение в степень
Темы: Рекурсия   

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

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

Входные данные: Вводится вещественное число a и целое число n.
Выходные данные: Выведите ответ на задачу.

Нельзя использовать стандартное возведение в степень.

Примеры

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

ID 31804
Скобки-2
Темы: Рекурсия   

Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок.
 
Входные данные
В первой строке находится единственное число N. \(1 <= N <= 14\), N - чётное.
 
Выходные данные
Каждое выражение выводится в отдельной строке.
 

 

Примеры
Входные данные Выходные данные
1 2
()
[]
2 4
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]

ID 38318
Взвешивание
Темы: Перебор    Рекурсия   

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

Входные данные
Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

Выходные данные
В первой строке выведите веса гирек, которые нужно поместить на левую чашу весов, во второй строке — гирьки, которые нужно поместить на правую чашу. Если на какую-то чашу ни одной гирьки помещать не нужно — выведите в этой строке число 0. Если с помощью данных гирек привести весы в равновесие нельзя, выведите одно число –1. Если вариантов несколько, выведите любой из них.
 

Примеры
Входные данные Выходные данные
1 5
2
3 5
0
5
2 5
3
6 3 4
4
3 6
3 5
1
2
-1

ID 38609
Разбиение на невозрастающие слагаемые, лексикографический порядок
Темы: Рекурсия    Разбиения   

Дано натуральное число N. Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.

Входные данные
Задано единственное число N. (N ≤ 40)

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

Примеры
Входные данные Выходные данные
1 5 1 1 1 1 1 
2 1 1 1 
2 2 1 
3 1 1 
3 2 
4 1 

ID 38638
Площадь комнаты
Темы: Обход в глубину    Рекурсия   

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

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

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

Примеры
Входные данные Выходные данные
1
5
*****
**..*
*.*.*
*..**
*****
2 4
3