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


Олимпиадный тренинг

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

Степень числа

Рекурсия

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

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

Примеры

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

Как поделить картошку

Рекурсия

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

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

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

Рекурсия

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

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


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

Наибольшая строка

Рекурсия

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

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

Перебор строк №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) К.Ю. Поляков
 

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

Рекурсия

Возводить в степень можно гораздо быстрее, чем за 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

Троечные последовательности

Рекурсия

Вводится число 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
 

Все числа от n до 1

Рекурсия

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

Примеры

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

Количество цифр

Рекурсия

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

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

Функция - 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

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

Рекурсия

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


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

Лесенки

Рекурсия

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

Звездочки

Рекурсия

Дана строка, содержащая только английские буквы (большие и маленькие). Добавить символ ‘*’ (звездочка) между буквами (перед первой буквой и после последней символ ‘*’ добавлять не нужно).
 
Входные данные
Вводится строка ненулевой длины. Известно также, что длина строки не превышает 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

Произведение битов

Рекурсия

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

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

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

Примеры

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


 

Функция

Рекурсия

Функция 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

Скобки-2

Рекурсия

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

Функция Аккермана

Рекурсия

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

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


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


 

Сумма делителей

Рекурсия

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

Примеры

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

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

Рекурсия

Вводится число 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
 

Чётные цифры

Рекурсия

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

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

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

Примеры

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

Длинный НОД

Рекурсия НОД и алгоритм Евклида

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

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

Вычисление факториала

Рекурсия

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

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

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

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

Сумма чисел от 1 до n

Рекурсия

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

Примеры

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

Разложение на слагаемые

Рекурсия

Требуется вывести все различные представления натурального числа 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

Только квадраты

Рекурсия

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

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

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

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

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

Рекурсия

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

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

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

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

Сумма битов

Рекурсия

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

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

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

Примеры

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

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

Рекурсия

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

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

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

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

Заполнение конем

Рекурсия

Дана шахматная доска 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 

Монетки

Рекурсия

В Волшебной стране используются монетки достоинством 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

Сумма кубов

Рекурсия

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

Выяснилось, что почти все чи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

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

Рекурсия

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 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