Функции

Ранее была задача вычисления числа сочетаний из n элементов по k, для чего необходимо вычисление факториалов трех величин: n, k и n-k. Для этого можно сделать три цикла, что приводит к увеличению размера программы за счет трехкратного повторения похожего кода. Вместо этого лучше сделать одну функцию, вычисляющую факториал любого данного числа n и трижды использовать эту функцию в своей программе. Соответствующая функция может выглядеть так:

def factorial(n):
    f = 1
    for i in range(2, n + 1):
        f *= i
    return f

Этот текст должен идти в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial. Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной f. Функция завершается инструкцией return f, которая завершает работу функции и возвращает значение переменной f. Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения, также в функциях, не возвращающих значения, инструкция return может отсутствовать.

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

n = int(input())
k = int(input())
print(factorial(n) // (factorial(k) * factorial(n - k)))

Мы также можем, например, объявить функцию binomial, которая принимает два целочисленных параметра n и k и вычисляет число сочетаний из n по k:

def binomial(n, k)
    return factorial(n) // (factorial(k) * factorial(n - k))

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

print(binomial(n, k))

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

def max(a, b):
    if a > b:
        return a
    else:
        return b

Теперь мы можем реализовать функцию max3, находящую максимум трех чисел:

def max3(a, b, c):
    return max(max(a, b), c)

Функция max3 дважды вызывает функцию max для двух чисел: сначала, чтобы найти максимум из a и b, потом чтобы найти максимум из этой величины и c.

Локальные и глобальные переменные

Внутри функции можно использовать переменные, объявленные вне этой функции

def f():
    print(a)
a = 1
f()

Здесь переменной a присваивается значение 1, и функция f печатает это значение, несмотря на то, что выше функции f эта переменная не инициализируется. Но в момент вызова функции f переменной a уже присвоено значение, поэтому функция f может вывести его на экран.

Такие переменные (объявленные вне функции, но доступные внутри функции) называются глобальными.

Но если инициализировать какую-то переменную внутри функции, использовать эту переменную вне функции не удастся. Например:

def f():
    a = 1
f()
print(a)

Получим NameError: name 'a' is not defined. Такие переменные, объявленные внутри функции, называются локальными. Эти переменные становятся недоступными после выхода из функции.

Интересным получится результат, если попробовать изменить значение глобальной переменной внутри функции:

def f():
    a = 1
    print(a)
a = 0
f()
print(a)

Будут выведены числа 1 и 0. То есть несмотря на то, что значение переменной a изменилось внутри функции, то вне функции оно осталось прежним! Это сделано в целях “защиты” глобальных переменных от случайного изменения из функции (например, если функция будет вызвана из цикла по переменной i, а в этой функции будет использована переменная i также для организации цикла, то эти переменные должны быть различными). То есть если внутри функции модифицируется значение некоторой переменной, то переменная с таким именем становится локальной переменной, и ее модификация не приведет к изменению глобальной переменной с таким же именем.

Более формально: интерпретатор Питон считает переменную локальной, если внутри нее есть хотя бы одна инструкция, модифицирующая значение переменной (это может быть оператор =, += и т.д., или использование этой переменной в качестве параметра цикла for, то эта переменная считается локальной и не может быть использована до инициализации. При этом даже если инструкция, модифицирующая переменную никогда не будет выполнена: интерпретатор это проверить не может, и переменная все равно считается локальной. Пример:

def f():
    print(a)
    if False:
        a = 0
a = 1
f()

Возникает ошибка: UnboundLocalError: local variable 'a' referenced before assignment. А именно, в функции f идентификатор a становится локальной переменной, т.к. в функции есть команда, модифицирующая переменную a, пусть даже никогда и не выполняющийся (но интерпретатор не может это отследить). Поэтому вывод переменной a приводит к обращению к неинициализированной локальной переменной.

Чтобы функция могла изменить значение глобальной переменной, необходимо объявить эту переменную внутри функции, как глобальную, при помощи ключевого слова global:

def f():
    global a
    a = 1
    print(a)
a = 0
f()
print(a)

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

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

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

return (a, b)

Тогда результат вызова функции тоже нужно присваивать кортежу:

(n, m) = f(a, b)

Упражнения

A: Длина отрезка

Даны четыре действительных числа: \(x_1, y_1, x_2, y_2\) . Напишите функцию distance(x1, y1, x2, y2), вычисляющую расстояние между точкой \((x_1,y_1)\) и \((x_2,y_2)\). Считайте четыре действительных числа и выведите результат работы этой функции.

Ввод Вывод
0
0
1
1
1.4142135623730951

B: Принадлежит ли точка квадрату - 1

Даны два действительных числа \(x\) и \(y\). Проверьте, принадлежит ли точка с координатами \((x,y)\) заштрихованному квадрату (включая его границу). Если точка принадлежит квадрату, выведите слово YES, иначе выведите слово NO. На рисунке сетка проведена с шагом 1.

Решение должно содержать функцию IsPointInSquare(x, y), возвращающую True, если точка принадлежит квадрату и False, если не принадлежит. Основная программа должна считать координаты точки, вызвать функцию IsPointInSquare и в зависимости от возвращенного значения вывести на экран необходимое сообщение.

Функция IsPointInSquare не должна содержать инструкцию if.

Ввод Вывод
0
0
YES
3
-7
NO

C: Принадлежит ли точка квадрату - 2

Решите аналогичную задачу для такого квадрата:

Решение должно соответствовать требованиям для решения задачи B.

Ввод Вывод
0
0
YES
1
1
NO

D: Принадлежит ли точка области

Проверьте, принадлежит ли точка данной закрашенной области:

Решение оформите в виде функции IsPointInArea(x, y).

Решение должно соответствовать требованиям для решения задачи С.

Ввод Вывод
-1
2
YES
0
0
NO

E: Минимальный делитель числа

Дано натуральное число \(n>1\). Выведите его наименьший делитель, отличный от 1.

Решение оформите в виде функции MinDivisor(n). Алгоритм должен иметь сложность \(O(\sqrt{n})\).

Указание. Если у числа \(n\) нет делителя не превосходящего \(\sqrt{n}\), то число \(n\) — простое и ответом будет само число \(n\).

Ввод Вывод
4
2
5
5

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

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

Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Решение должно иметь сложность \(O(\sqrt{n})\).

Ввод Вывод
2
YES
4
NO

G: Дружественные числа

Дружественные числа — это два натуральных числа, таких, что сумма всех делителей одного числа (меньших самого этого числа) равна другому числу, и наоборот (дружественными являются, например, 220 и 284).

Напишите программу, которая проверяет пару чисел на "дружественность". Используйте функцию, которая вычисляет сумму делителей числа, которая должна иметь сложность \(O(\sqrt{n})\).

Программа должна вывести слово YES, если пара чисел является дружественной и NO, в противном случае.

Ввод Вывод
220
284
YES

H: Дружественные числа в диапазоне

Дружественные числа — это два натуральных числа, таких, что сумма всех делителей одного числа (меньших самого этого числа) равна другому числу, и наоборот (дружественными являются, например, 220 и 284).

Напишите программу, которая находит все пары дружественных чисел в заданном диапазоне.

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

Если в заданном диапазоне нет дружественных чисел, программа должна вывести 0.

Ввод Вывод
1000
5000
(1184,1210) (2620,2924)

I: Сумма цифр не меняется

Напишите программу, которая находит все числа в диапазоне от a до b, сумма цифр которых не меняется при умножении на 2, 3, 4, 5, 6, 7, 8 и 9 (например, число 9). Используйте функцию для вычисления суммы цифр числа.

Выведите числа, соответствующие условию задачи, в одну строку, в возрастающем порядке. Можете считать, что такие числа в указанном диапазоне обязательно найдутся.

Ввод Вывод
1
10
9

J: Гиперпростые числа

Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких последних цифр, тоже является простым. Например, число 733 — гиперпростое, так как и оно само, и числа 73 и 7 — простые.

Напишите программу, которая определяет, верно ли, что переданное ей число N — гиперпростое. Учтите, что число 1 не считается простым.

Ввод Вывод
733
YES

K: Гиперпростые числа в диапазоне

Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких последних цифр, тоже является простым. Например, число 733 — гиперпростое, так как и оно само, и числа 73 и 7 — простые.

Напишите программу, которая находит все гиперпростые числа в заданном диапазоне и выводит их в порядке возрастания в одну строку через пробел. Если ни одного числа не найдено, программа должна вывести 0.

Ввод Вывод
30
100
31 37 53 59 71 73 79

Рекурсия

                      Эпиграф:
                        def ShortStory():
                            print("У попа была собака, он ее любил.")
                            print("Она съела кусок мяса, он ее убил,")
                            print("В землю закопал и надпись написал:")
                            ShortStory()

Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что \(0!=1\), \(1!=1\). А как вычислить величину \(n!\) для большого \(n\)? Если бы мы могли вычислить величину \((n-1)!\), то тогда мы легко вычислим \(n!\), поскольку \(n!=n(n-1)\)!. Но как вычислить \((n-1)!\)? Если бы мы вычислили \((n-2)!\), то мы сможем вычисли и \((n-1)!=(n-1)(n-2)!\). А как вычислить \((n-2)!\)? Если бы... В конце концов, мы дойдем до величины \(0!\), которая равна \(1\). Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:

def factorial (n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.

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

  1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if n == 0, то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т.д.
  2. Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получиться бесконечная цепочка.

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

Максимальная глубина рекурсии

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

import sys

sys.setrecursionlimit(10 ** 9)

Упражнения на рекурсию

L: Сумма чисел

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

При решении этой задачи нельзя пользоваться списками и прочими динамическими структурами данных. Нельзя также использовать строки для сохранения всех введенных чисел. Рекурсия вам поможет.

Ввод Вывод
1
2
3
0
6

M: Разворот последовательности

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

При решении этой задачи нельзя пользоваться списками и прочими динамическими структурами данных. Нельзя также использовать строки для сохранения всех введенных чисел. Рекурсия вам поможет.

Ввод Вывод
1
2
3
0
0
3
2
1

Указание. Программа должна содержать функцию Reverse(), не принимающую параметров, которая считывает последовательность чисел при помощи функции input и выводящую эту же последовательность в обратном порядке на стандартный вывод, при помощи функции print, при этом функция не возвращает значения при помощи инструкции return.

N: Алгоритм Евклида

Для быстрого вычисления наибольшего общего делителя двух чисел используют алгоритм Евклида. Он построен на следующем соотношении: \(НОД(a,b)=НОД(a\bmod b,b)\).

Реализуйте рекурсивный алгоритм Евклида в виде функции gcd(a, b).

Ввод Вывод
12
16
4

O: Наименьшее общее кратное

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

Ввод Вывод
12
16
48

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

Возводить в степень можно гораздо быстрее, чем за \(n\) умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями:

\(a^n=(a^2)^{n/2}\) при четном \(n\),

\(a^n=a\cdot a^{n-1}\) при нечетном \(n\).

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

На вход программе подаётся вещественное число \(a\) и целое неотрицательное \(n\).

Ввод Вывод
1.000000001
1000000000
2.7182820387553908

Q: Количество вызовов функции (числа Фибоначчи)

Последовательность Фибоначчи определяется так: \[ \varphi_1=1, \varphi_2=1, ..., \varphi_{n}=\varphi_{n-1}+\varphi_{n-2}. \]

Можно написать функцию fib(n), которая по данному целому натуральному n возвращает \(n\)-e число Фибоначчи. А сколько раз запустится эта функция прежде, чем будет получено значение? Под данному числу n \(1\le n\le 40\) выведите одно число — количество вызовов функции.

Ввод Вывод
3
3
1
1

Q+: Полезна ли рекурсия?

Запустите программы, вычисляющие числа Фибоначчи при помощи рекурсивного и нерекурсивного алгоритма. Сравните время их работы для n=10, 15, 20, 25, 30, 35. Объясните результат.

R: Число сочетаний

По данным числам \(n\) и \(k\) \((0\le k\le n)\) вычислите \(С_n^k\). Для решения используйте рекуррентное соотношение \(C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}\).

Решение оформите в виде функции C(n, k).

Ввод Вывод
6
3
20

S: Сложение без сложения

Напишите рекурсивную функцию sum(a, b), возвращающую сумму двух целых неотрицательных чисел. Из всех арифметических операций допускаются только + 1 и - 1. Также нельзя использовать циклы.

Ввод Вывод
2
2
4

T: Рекурсивный перевод из двоичной в десятичную

Переведите данное число N \((1\le N\le 32767)\) из двоичной системы счисления в десятичную.

Необходимо вывести число N в десятичной системе счисления без ведущих нулей.

При решении задачи нельзя использовать операцию возведения в степень, а также циклы.

Ввод Вывод
1010
10

U: Сумма двоичных строк

Даны две строки, содержащие двоичные представления неотрицательных целых чисел \(a\) и \(b\).

Строки могут содержать до 10000 символов.

Напишите рекурсивную функцию вычисления их суммы \(a + b\) без использования перевода этих чисел в десятичную систему счисления.

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

Ввод Вывод
101
110
1011

V: Произведение двоичных строк

Даны две строки, содержащие двоичные представления неотрицательных целых чисел a и b.

Строки могут содержать до 10000 символов.

Напишите рекурсивную функцию вычисления их произведения \(a * b\) без использования перевода этих чисел в десятичную систему счисления.

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

Можно воспользоваться таким наблюдением: если произведение чисел \(x\) и \(y\) (при этом \(y\) чётное) заменить на произведение \(x * 2\) и \(y // 2\), то результат не изменится. Умножение двоичного числа на \(2\) это приписывание нуля справа, а деление — стирание последнего нуля.

Ввод Вывод
101
110
11110

W: Рекурсивный перевод из десятичной в P-ичную

Напишите рекурсивную процедуру для перевода десятичного числа в P-ичную систему счисления.

На вход программе сначала подается значение P (\(1 < P < 10\)), а во второй строке — десятичное число.

Вывод осуществляйте следующим образом: сначала выведите введенное число в десятичной системе счисления, за ним укажите его систему счисления в круглых скобках, то есть (10), затем ставится знак "=" и аналогично выводится результат работы вашей программы — число в P-ичной системе счисления. Весь вывод осуществляется без пробелов.

При решении задачи нельзя использовать операцию возведения в степень, а также возведение в степень.

Ввод Вывод
3
123
123(10)=11120(3)

X: Фишки

Дана полоска из клеток, пронумерованных от 1 до N слева направо. Разрешено снимать или ставить фишку на клетку с номером 1 или на клетку, следующую за самой левой из установленных фишек. Изначально полоска пуста. Нужно разместить фишки во всех клетках.

Программа получает на вход количество клеток в полоске \(N\) \((1\le N\le 10)\).

Программа должна вывести последовательность номеров клеток, с которыми совершается действие. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать \(10^4\). Если существует несколько возможных решений задачи, то разрешается вывести любое.

Тесты к этой задаче закрытые.

Ввод Вывод
3
1 2 -1 3 1

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

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из \(n\) дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

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

Указание: подумайте, как переложить пирамидку из одного диска? Из двух дисков? Из трех дисков? Из четырех дисков? Пусть мы научились перекладывать пирамидку из \(n\) дисков с произвольного стержня на любой другой, как переложить пирамидку из \(n+1\) диска, если можно пользоваться решением для \(n\) дисков.

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

Ввод Вывод
2
1 1 2
2 1 3
1 2 3

Z: Ремонт в Ханое

Постановлением ЮНЕСКО оригинал Ханойской башни был подвергнут реставрации. В связи с этим во время пользования головоломкой нельзя было перекладывать кольца с первого стержня сразу на третий и наоборот.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

Тесты к этой задаче закрытые.

Ввод Вывод
1
1 1 2
1 2 3
2
1 1 2
1 2 3
2 1 2
1 3 2
1 2 1
2 2 3
1 1 2
1 2 3

ZA: Циклические башни

На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 на 3, а со стержня 3 на 1.

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

Ввод Вывод
1
1 1 2
1 2 3
2
1 1 2
1 2 3
2 1 2
1 3 1
2 2 3
1 1 2
1 2 3

ZB: Несправедливые башни

В Ханое несправедливо запретили класть самый маленький диск (номер 1) на средний колышек (номер 2).

Решите головоломку с учетом этих ограничений. Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

Ввод Вывод
2
1 1 3
2 1 2
1 3 1
2 2 3
1 1 3

ZC: Сортирующие башни

Первоначально все диски лежат на стержне номер 1. Переместите диски с нечетными номерами на стержень номер 2, а с четными номерами - на стержень номер 3.

Вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000, при условии, что количество дисков не превосходит 10.

Ввод Вывод
2
1 1 2
2 1 3
3
1 1 2
2 1 3
1 2 3
3 1 2
1 3 2

ZD: Обменные башни

Как и в предыдущих задачах, дано три стержня, на первом из которых надето \(n\) дисков различного размера. Необходимо их переместить на стержень 3 по следующим правилам:

Самый маленький диск (номер 1) можно в любой момент переложить на любой стержень. Перемещение диска номер 1 со стержня a на стержень b будем обозначать 1 a b.

Можно поменять два диска, лежащих на вершине двух стержней, если размеры этих дисков отличаются на 1. Например, если на вершине стержня с номером a лежит диск размером 5, а на вершине стержня с номером b лежит диск размером 4, то эти диски можно поменять местами. Такой обмен двух дисков будем обозначать 0 a b (указываются номера стержней, верхние диски которых обмениваются местами).

Для данного числа дисков \(n\), не превосходящего 10, найдите решение головоломки. вам не нужно находить минимальное решение, но количество совершенных перемещений не должно быть больше 200000.

Ввод Вывод
1
1 1 3
2
1 1 3
0 1 3
1 1 3