В этом листке собраны тренировочные задачи. Их решение необязательно, но рекомендуется тем, кто плохо освоил задачи на рекурсию. Также в этом листке есть несколько довольно сложных задач, которые могут быть интересны всем. Задачи из этого листка не учитываются при выставлении оценок.
Задачи можно сдавать на языках C++ и Python, поэтому если вы хотите попрактиковаться в другом языке, то тоже можете сдавать задачи.
В задачах этого листка нельзя использовать циклы и массивы. Также могут быть и другие ограничения в каких-то конкретных задачах (например, запрет использования строк в арифметических задачах, запрет использования срезов в решениях на питоне).
Задачи проверяются только автоматически и сразу же получают OK при прохождении всех тестов. Однако, если при последующей проверке кода будет выявлено нарушение вышеизложенных требований или будут другие замечания к решению, статус OK может быть изменен.
Дано натуральное число \(n\). Выведите все числа от 1 до \(n\).
| Ввод | Вывод |
|---|---|
5 |
1 2 3 4 5 |
Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания,
если A < B, или в порядке убывания в противном случае.
| Ввод | Вывод |
|---|---|
5 |
5 4 3 2 1 |
В теории вычислимости важную роль играет функция Аккермана \(A(m, n)\), определенная следующим образом: \[ A(m, n) = \begin{cases} n + 1 & m = 0\\ A(m - 1, 1)& m > 0, n = 0\\ A(m - 1, A(m, n - 1))& m > 0, n > 0\\ \end{cases} \]
Даны два целых неотрицательных числа \(m\) и \(n\), каждое в отдельной строке. Выведите \(A(m, n)\).
| Ввод | Вывод |
|---|---|
2 |
7 |
Дано натуральное число N. Выведите слово YES, если число N является
точной степенью двойки, или слово NO в противном случае.
Операцией возведения в степень пользоваться нельзя!
| Ввод | Вывод |
|---|---|
8 |
YES |
3 |
NO |
Дано натуральное число N. Вычислите сумму его цифр.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется).
| Ввод | Вывод |
|---|---|
179 |
17 |
Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.
| Ввод | Вывод |
|---|---|
179 |
9 7 1 |
Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.
| Ввод | Вывод |
|---|---|
179 |
1 7 9 |
Дано натуральное число \(n>1\). Проверьте, является ли оно простым. Программа должна вывести слово
YES, если число простое и NO, если число составное.
Алгоритм должен иметь сложность \(O(\sqrt{n})\).
| Ввод | Вывод |
|---|---|
2 |
YES |
4 |
NO |
Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа \(n\) на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.
Дано натуральное число \(n>1\). Выведите все простые делители этого числа в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность \(O(\sqrt{n})\).
| Ввод | Вывод |
|---|---|
18 |
2 3 3 |
Дано слово, состоящее только из строчных латинских букв.
Проверьте, является ли это слово палиндромом. Выведите
YES или NO.
При решении этой задачи нельзя пользоваться циклами, в решениях на питоне нельзя использовать срезы с шагом, отличным от 1.
| Ввод | Вывод |
|---|---|
radar |
YES |
yes |
NO |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.
| Ввод | Вывод |
|---|---|
3 |
3 |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите первое, третье, пятое и т.д. из введенных чисел. Завершающий ноль выводить не надо.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.
| Ввод | Вывод |
|---|---|
7 |
7 |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите наибольшее значение числа в этой последовательности.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).
| Ввод | Вывод |
|---|---|
1 |
7 |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите среднее значение элементов этой последовательности (без учета последнего нуля).
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).
| Ввод | Вывод |
|---|---|
1 |
5.666666666666667 |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности, то есть элемента, который будет наибольшим, если из последовательности удалить наибольший элемент.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).
| Ввод | Вывод |
|---|---|
1 |
7 |
1 |
2 |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).
| Ввод | Вывод |
|---|---|
1 |
1 |
1 |
2 |
Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.
В этой задаче нельзя использовать глобальные переменные и параметры, передаваемые в функцию. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметров.
| Ввод | Вывод |
|---|---|
1 |
2 |
Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...
По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом for.
| Ввод | Вывод |
|---|---|
2 |
1 2 |
5 |
1 2 2 3 3 |
Даны натуральные числа \(k\) и \(s\). Определите, сколько существует \(k\)-значных натуральных чисел, сумма цифр которых равна \(d\). Запись натурального числа не может начинаться с цифры 0.
В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции.
| Ввод | Вывод |
|---|---|
3 |
69 |
Даны числа \(a\) и \(b\). Определите, сколько существует последовательностей из \(a\) нулей и \(b\) единиц, в которых никакие два нуля не стоят рядом.
| Ввод | Вывод |
|---|---|
2 |
3 |
Дано число \(n\), десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке.
При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика.
Фунция должна возвращать целое число, являющееся результатом работы программы, выводить число по одной цифре нельзя.
| Ввод | Вывод |
|---|---|
179 |
971 |