Вывести все числа от 1 до числа введенного с клавиатуры c

Обновлено: 16.05.2024

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

Задачи можно сдавать на языках C++ и Python, поэтому если вы хотите попрактиковаться в другом языке, то тоже можете сдавать задачи.

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

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

A: От 1 до n

Дано натуральное число $n$. Выведите все числа от 1 до $n$.

Ввод	Вывод

B: От A до B

Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A < B , или в порядке убывания в противном случае.

Ввод	Вывод

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

В теории вычислимости важную роль играет функция Аккермана $A(m, n)$, определенная следующим образом: \[ A(m, n) = \begin n + 1 & m = 0\\ A(m - 1, 1)& m > 0, n = 0\\ A(m - 1, A(m, n - 1))& m > 0, n > 0\\ \end \]

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

Ввод	Вывод

D: Точная степень двойки

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

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

E: Сумма цифр числа

Дано натуральное число N. Вычислите сумму его цифр.

При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется).

Ввод	Вывод

F: Цифры числа справа налево

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

При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

Ввод	Вывод

G: Цифры числа слева направо

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

Ввод	Вывод

H: Проверка числа на простоту

Дано натуральное число $n>1$. Проверьте, является ли оно простым. Программа должна вывести слово YES , если число простое и NO , если число составное. Алгоритм должен иметь сложность $O(\sqrt)$.

Ввод	Вывод

Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа $n$ на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.

I: Разложение на множители

Дано натуральное число $n>1$. Выведите все простые делители этого числа в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность $O(\sqrt)$.

Ввод	Вывод

J: Палиндром

Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO .

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

Ввод	Вывод

K: Вывести нечетные числа последовательности

Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.

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

Ввод	Вывод

L: Вывести члены последовательности с нечетными номерами

Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите первое, третье, пятое и т.д. из введенных чисел. Завершающий ноль выводить не надо.

Ввод	Вывод

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

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

В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Ввод	Вывод

N: Среднее значение последовательности

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

В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке.

Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Ввод	Вывод

O: Второй максимум

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

В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.

Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).

Ввод	Вывод

P: Количество элементов, равных максимуму

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

В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.

Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Ввод	Вывод

Q: Количество единиц

Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.

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

Ввод	Вывод

R: Треугольная последовательность

Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, .

По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом for.

Ввод	Вывод

S: Заданная сумма цифр

Даны натуральные числа $k$ и $s$. Определите, сколько существует $k$-значных натуральных чисел, сумма цифр которых равна $d$. Запись натурального числа не может начинаться с цифры 0.

В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции.

Ввод	Вывод

T: Без двух нулей

Даны числа $a$ и $b$. Определите, сколько существует последовательностей из $a$ нулей и $b$ единиц, в которых никакие два нуля не стоят рядом.

Ввод	Вывод

U: Разворот числа

Дано число $n$, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке.

При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика.

1 Потоковый ввод/вывод

Эти объекты называются потоками ввода/вывода. В дальнейших уроках мы узнаем и о других разновидностях таких потоков. Потоковый ввод/вывод осуществляется операциями >> и << соответственно. Использовать их можно следующим образом:

В этой программе создается 3 переменных целого типа данных ( int ), в конце урока приведена более подробная информация об этом и других стандартных типах. Тут, как и в hello world использолся вызов функции std::cin.get() для задержки закрытия окна. На самом деле эта функция ( get ) ожидает ввода символа пользователем.

Объект std::cin является потоком ввода, к нему можно применять оператор >> для получения значений переменных с клавиатуры:

Теперь значения переменных задаются не программистом, а пользователем (в процессе использования программы).

С помощью объекта cin и операции >> можно присвоить значение любой переменной. Например, если переменная x описана как целочисленная, то команда cin>>x; означает, что в переменную x будет записано некое целое число, введенное с клавиатуры. Если необходимо ввести несколько переменных, то можно написать:
cin >> x >> y >> z; .

2 Основные операции над числами

Директива using namespace std; сообщает компилятору, что в этом месте вы используете имена из пространства имен std , за счет нее вы, в частности, можете писать cout или cin вместо std::cout и std::cin . Тему пространств имен мы подробно изучим в следующих уроках.

Теперь рассмотрим изученное на примере более сложной задачи (наконец, заставим наш компьютер посчитать что-нибудь полезное):

Известны плотность p , высота h и радиус основания R цилиндрического слитка.
Найти объем V , массу m и площадь S основания слитка.

Составим текст программы, учитывая что:
$$S = \pi \cdot R \cdot R, \\
V = S \cdot h,\\
m = p \cdot V.$$

Результаты работы программы:

Исследуя эту программу, обратите внимание на:

3 Справочный материал

3.1 Переменные и типы данных

Переменная это область памяти заполненная данными, которые называются значением переменной. У каждой переменной должно быть своё уникальное имя на латинице с учетом регистра. Переменные делятся на целочисленные, дробные, символьные, логические (т.е «да» или «нет»).

Для решения задачи в любой программе выполняется обработка каких-либо данных. К основным типам данных языка C++ относят:

Для формирования других типов данных используют основные и так называемые спецификаторы:

short — короткий;
long — длинный;
signed — знаковый;
unsigned — беззнаковый.
const — константа.

В таблице приведена справочная информация о различных комбинациях типов данных с учетом спецификаторов для операционной системы Windows:

Имя типа	Размер (в байтах)	Диапазон значений
int (signed int)	4	От -2 147 483 648 до 2 147 483 647
unsigned int	4	От 0 до 4 294 967 295
bool	1	false или true
char (unsigned char)	1	-128 до 127 знаков по умолчанию
signed char	1	От -128 до 127
unsigned char	1	От 0 до 255
short (signed short)	2	От -32 768 до 32 767
unsigned short	2	От 0 до 65 535
long (signed long)	4	От -2 147 483 648 до 2 147 483 647
unsigned long	4	От 0 до 4 294 967 295
long long (signed long long)	8	От -9 223 372 036 854 775 808 до 9 223 372 036 854 775 807
unsigned long long	8	От 0 до 18 446 744 073 709 551 615
float	4	3,4E +/- 38 (7 знаков)
double (long double)	8	1,7E +/- 308 (15 знаков)
wchar_t	2	От 0 до 65 535

Переменная типа bool может принимать только два значения true (истина) или fasle (ложь), тем не менее, в памяти занимает не 1 бит, а 1 байт. Любое значение, не равное нулю, интерпретируется как true .

3.2 Битовые операции

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

Ниже показано как выполняется операция логического ИЛИ для такого фрагмента кода:

3.3 Приведение типов

В C++ различают два вида преобразования типов данных: явное и неявное.

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

Наивысший приоритет получает тот тип, при котором произойдет минимальная потеря информации (в результате округления). Не стоит злоупотреблять неявным преобразованием типов, так как могут возникнуть разного рода непредвиденные ситуации.

В этом примере при присваивании выполнится неявное приведение переменной типа float к типу int . В результате работы программы на экран будет выведено число 123 .

Явное преобразование в отличие от неявного осуществляется программистом. Записать это можно следующим образом:
b = (int) a;
или
b = int(a);

Тут мы явно указываем, что переменной b нужно присвоить значение a, приведенное к типу int .

В С++ определены следующие операторы:

Тип static_cast <Тип> (объект);

С помощью static_cast нельзя убрать константность у переменной, но это по силам следующему оператору.

3.4 Составное присваивание, инкремент/декремент

В ваших программах часто нужно выполнить что-то типа
a = a+b;
вместо такой конструкции можно использовать специальный вид оператора:
a += b;

Еще чаще в программах нужно увеличивать или уменьшать значение переменной ровно на единицу:

Аналогично работает постфиксный и префиксный декремент (оператор -- ).

Здравствуйте!
Интересно, когда нужно использовать целую переменную, часто ли пишут что-то кроме int? Когда на практике это бывает нужно?

В каком-нибудь небольшом цикле, к примеру, от 0 до 9, в учебниках обычно используют тип int.

Хотя, опять же, заморачиваться с этим на ранних этапах разработки не стоит. Лучше пораньше выпустить программу, а потом уже заниматься ее профилированием.

Задача A. Четные числа
Выведите (через пробел) все четные числа от a до b (включительно).

Задача B. Остаток
Вводятся 4 числа: a, b, c и d.
Выведите все числа на отрезке от a до b, дающие остаток c при делении на d.

Задача C. Квадраты
Выведите все числа на отрезке от a до b, являющиеся полными квадратами.

Задача H. Делители числа
Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).

Задача I. Количество делителей
Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x <= 30000).

Задача J. Сумма ста
Вычислите сумму данных 100 натуральных чисел. Вводятся 100 чисел, сумму которых необходимо посчитать.

Задача K. Сумма чисел
Вычислите сумму данных N натуральных чисел. Вводится число N, а затем N чисел, сумму которых необходимо вычислить.

Задача M. Нули
Вводится число N, а затем N чисел. Подсчитайте, сколько среди данных N чисел нулей.

Задача N. Подсчет чисел
Подсчитайте, сколько среди данных N чисел нулей, положительных чисел, отрицательных чисел. Вводится число N, а затем N чисел. Необходимо вывести сначала число нулей, затем число положительных и отрицательных чисел.

Задача O. Ноль или не ноль
Проверьте, есть ли среди данных N чисел нули. Вводится число N, а затем N чисел. Выведите YES, если среди введенных чисел есть хотя бы один нуль, или NO в противном случае.

Вариант 2.
Ту же самую идею можно описать короче.

Задача P. Уравнение по возрастанию
Вводятся 4 числа: a, b, c и d.
Найдите все целые решения уравнения ax 3 + bx 2 + cx + d = 0 на отрезке [0,1000] и выведите их в порядке возрастания.

Задача Q. Уравнение по убыванию
Вводятся 4 числа: a, b, c и d.
Найдите все целые решения уравнения ax 3 + bx 2 + cx + d = 0 на отрезке [0,1000] и выведите их в порядке убывания.

Задача R. Количество решений
Вводятся 5 чисел: a, b, c, d и e.
Найдите все целые решения уравнения ( ax 3 + bx 2 + cx + d ) / ( x - e ) = 0 на отрезке [0,1000] и выведите их количество.

Вариант 1.
При таком варианте реализации мы печатаем столько раз текущее значение cur сколько оно само обозначает count , после чего обнуляем подсчет одинаковых выводов count и переходим на следующее текущее значение cur и т.д.

Сегодня мы узнаем с вами, как отделить каждую цифру от числа начиная от младшего разряда, заканчивая старшим. Это нам частенько пригодится в дальнейшем.

Разделение числа на цифры

Идея алгоритма:
Для каждого числа необходимо найти его разряд.

1 => единица;
42 => 4 десятка и 2 единицы;
829 => 8 сотен, 2 десятка, 9 единиц.

Поиск разрядов числа

Нам дано число: 123456789

Последнюю цифру мы легко найдем, нам достаточно наше число разделить 10 с остатком. А что делать с предпоследней цифрой? Тут как минимум есть два варианта:

/10 – откинули последнюю цифру, а затем снова %10;
%10 и его степень. Способ довольно неудобный. Поэтому мы не будем им пользоваться.

Первый вариант кажется достаточно удобным. Мы будем получать нужную нам цифру в ходе каждой итерации цикла.

123456789 % 10 = 9;
123456789 / 10 = 12345678;
Переходим к следующей итерации
12345678 % 10 = 8;
12345678 / 10 = 1234567;

И так далее пока не переберем все число.

Алгоритм разделения числа на цифры

Ввести число a;
Запустить цикл;
Найти цифру при помощи a % 10;
Вывести цифру (или использовать ее в задаче);
Уменьшить а в 10 раз.

Этот цикл будет работать до тех пор, пока n не превратится в 0.

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

Использование алгоритма

Мы можем применять данный алгоритм в этих случаях

Анализ зависимостей в цифрах числа;
Определение присутствия цифры;
Подсчёт цифр;
Подсчёт количества цифр;
Замена цифр в числе;
Анализ чисел в других системах счисления;
Анализ бинарных данных.

Решение задач

Разбор задачи Счастливый билет

Например, мы хотим написать программу, которая проанализирует билет, который нам дали в автобусе, является он счастливым или нет? Если вы не помните или не знали, как это делается, напомню. Билет считается счастливым, когда сумма первых трех чисел равняется сумме трех последних.

Нам вводится номер билета и необходимо проверить, является ли он счастливым.
Давайте посчитаем. Посмотрите на номер нашего билета: 306 450.

Если мы просуммируем 3+0+6 == 4+5+0;
То получим в первой и второй сумме чисел одинаковое значение 9 == 9;
Это означает, что наш билет счастливый.

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

Алгоритм решения

Ввести число;
Разделять его на цифры;
Первые три числа добавлять в sum1;
Последние три числа добавлять в sum2;
Сравнить sum1 и sum2.

Разложи на цифры

Дано восьмизначное число, необходимо написать в строку каждую цифру данного числа через пробел, начиная с разряда единиц.
Формат входных данных
Дано целое число N (10 000 000 Tags

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).

Задачи

При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.

Как же решать задачи на рекурсию ?

В первую очередь надо понимать что рекурсия это своего рода перебор. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции.

Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.

Для обоснования можно привести такие доводы.

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

После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий — итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно — завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.

Задача по приведению рекурсии к итеративному подходу симметрична.

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

Более подробно с этим можно познакомиться тут

Так же как и у перебора (цикла) у рекурсии должно быть условие остановки — Базовый случай (иначе также как и цикл рекурсия будет работать вечно — infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Условие остановки или же Базовый случай
Условие продолжения или Шаг рекурсии — способ сведения задачи к более простым.

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня

Рассмотрим же теперь задачи с различным уровнем сложности.
Попробуйте их решить самостоятельно используя метод описанный выше. При решении попробуйте думать рекурсивно. Какой базовый случай в задаче? Какой Шаг рекурсии или рекурсивное условие?

Поехали! Решения задач предоставлены на языке Java.

A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.

B: От A до B
Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.

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

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

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

E: Сумма цифр числа
Дано натуральное число N. Вычислите сумму его цифр.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется).

F: Цифры числа справа налево
Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

G: Цифры числа слева направо
Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

H: Проверка числа на простоту
Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Алгоритм должен иметь сложность O(logn).
Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа n на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.

I: Разложение на множители
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность O(logn).

J: Палиндром
Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO.
При решении этой задачи нельзя пользоваться циклами, в решениях на питоне нельзя использовать срезы с шагом, отличным от 1.

K: Вывести нечетные числа последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

L: Вывести члены последовательности с нечетными номерами
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите первое, третье, пятое и т.д. из введенных чисел. Завершающий ноль выводить не надо.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

M: Максимум последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите наибольшее значение числа в этой последовательности.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

N: Среднее значение последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите среднее значение элементов этой последовательности (без учета последнего нуля).
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

O: Второй максимум
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности, то есть элемента, который будет наибольшим, если из последовательности удалить наибольший элемент.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).

P: Количество элементов, равных максимуму
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Q: Количество единиц
Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.
В этой задаче нельзя использовать глобальные переменные и параметры, передаваемые в функцию. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметров.

R: Треугольная последовательность
Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4,…
По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом for.

S: Заданная сумма цифр
Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. Запись натурального числа не может начинаться с цифры 0.
В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции.

T: Без двух нулей
Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.

U: Разворот числа
Дано число n, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке.
При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика.
Фунция должна возвращать целое число, являющееся результатом работы программы, выводить число по одной цифре нельзя.
Update от Eivind

Вот и все. Надеюсь решение задач принесло вам столько же удовольствия сколько и мне!

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

Читайте также: