Дано целое число \(n\ge 0\). Вычислите сумму чисел \(0 + 1 + ... + n\) не используя формулу суммы арифметической прогрессии и циклы.
Решение оформите в виде рекурсивной функции sum0n(n: int) -> int,
получающей в качестве параметра значение \(n\) и возвращающей нужную сумму.
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
sum0n(5) |
15 |
Дано целое число \(n\gt 0\). Посчитайте сумму его цифр, не используя строковые операции
и циклы. Решение оформите в виде рекурсивной функции sum_of_digits(n),
возвращающей сумму цифр числа \(n\).
На проверку сдайте только тело функции.
Указание. Отбросьте от числа последнюю цифру, тем самым сведите задачу к меньшему числу.
| Вызов функции | Возвращаемое значение |
|---|---|
sum_of_digits(179) |
17 |
Дано целое число \(n\gt 0\). Определите, не используя строковые операции
и циклы. Решение оформите в виде рекурсивной функции min_digit(n),
возвращающей значение минимальной цифры числа \(n\). На проверку сдайте только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
min_digit(179) |
1 |
Дано целое число \(n\gt 0\). Определите не используя циклы, является ли это число точной степенью числа 2.
Решение оформите в виде рекурсивной функции is_power2(n: int) -> bool,
возвращающей значение типа bool. Для чисел 1, 2, 4, 8 и т.д. функция
должна возвращать True, для остальных чисел — False.
На проверку сдайте только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
is_power2(8) |
True |
is_power2(3) |
False |
Последовательность Фибоначчи \(\{\varphi_n\}\) определяется так: \(\varphi_0=0\), \(\varphi_1=1\), \(\varphi_{n}=\varphi_{n-1}+\varphi_{n-2}\), при \(n \gt 1\).
Напишите рекурсивную функцию fib(n), которая по данному целому неотрицательному \(n\)
возвращает \(\varphi_n\).
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
fib(6) |
8 |
Вычислите число сочетаний \(\text{C}_n^k\) используя рекуррентое соотношение \( \text{C}_n^k=\text{C}_{n-1}^{k-1}+\text{C}_{n-1}^{k} \).
Решение оформите в виде рекурсивной функции combination(n, k),
где \(0\le k \le n\).
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
combination(7, 3) |
35 |
Сделаем такое преобразование.
\[ \text{C}_n^k = \dfrac{n!}{k!(n-k)!}=\dfrac{n\cdot(n-1)!}{k\cdot (k-1)!(n-k)!}=\frac{n}{k}\text{C}_{n-1}^{k-1}. \]Вычислите число сочетаний \(\text{C}_n^k\) используя полученное рекуррентное соотношение.
Решение оформите в виде рекурсивной функции combination(n, k).
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
combination(7, 3) |
35 |
Можно написать рекурсивную функцию возведения в степень.
def power(a, n):
if n == 0:
return 1
return a * power(a, n - 1)
Такая функция имеет сложность \(O(n)\). Но возводить в степень можно гораздо быстрее, чем за \(n\) умножений. Для этого нужно воспользоваться cледующими рекуррентными соотношениями:
\[ a^n=\cases{ (a^2)^{n/2}\mbox{, при четном \(n\);}\cr a\cdot a^{n-1}\mbox{, при нечетном \(n\).}} \]Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет \(O(\log n)\).
Решение оформите в виде функции power(a, n), где \(n\ge 0\). Использовать
стандартную функцию pow и оператор ** запрещается.
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
power(1.000000001, 1000000000) |
2.718282030814511 |
Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(\mbox{НОД}(a,b)=\mbox{НОД}(a\bmod b,b)\).
Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b), возвращающей искомое значение.
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
gcd(12, 16) |
4 |
Напишите функцию product(a),
которая по данному списку чисел возвращает произведение
элементов данного списка, не используя циклы.
Список содержит только числа, но может быть пустым.
Сдайте на проверку только тело функции.
| Вызов функции | Возвращаемое значение |
|---|---|
product([1, 7, 9]) |
63 |
Напишите рекурсивную функцию print_numbers(n),
которая выводит на экране целые числа от 1 до \(n\),
по одному числу в строке. Циклы и генераторы списков использовать нельзя.
Функция не должна возвращать значение.
Указание. Число \(n\) является параметром. Как свести задачу «вывести числа от 1 до \(n\)» к задаче с меньшим значением параметра?
Сдайте на проверку только тело функции.
| Вызов функции | Вывод |
|---|---|
print_numbers(3) |
1 |
Напишите рекурсивную функцию print_numbers(a, b),
которая выводит на экране целые числа от \(a\) до \(b\),
по одному числу в строке. Если \(a\lt b\), то числа выводятся
в порядке возрастания, если \(a\gt b\) — в порядке убывания.
Циклы и генераторы списков использовать нельзя. Функция не должна возвращать значение.
Сдайте на проверку только тело функции.
| Вызов функции | Вывод |
|---|---|
print_numbers(3, 6) |
3 |
print_numbers(7, 4) |
7 |
Напишите рекурсивную функцию read(),
не получающей параметров и не возвращающей значения.
Вызов этой функции должен приводить к считыванию со стандартного ввода чисел, до тех пор, пока не будет введено число, равное 0. При этом функция должна выводить на экран считанное число, если оно является нечётным.
Указание. При считывании нуля функция должна завершить работу. Иначе функция считывает число, выводит его на экран, если оно нечётное, а потом рекурсивно вызывает себя же.
В решении нельзя использовать циклы. Сдайте на проверку только тело функции.
| Вызов функции | Ввод | Вывод |
|---|---|---|
read() |
179 |
179 |