Файл: Типы данных и функции вывода.docx

Все переменные, которыми мы пользовались до сегодняшнего дня, были глобальными. Глобальные переменные видны во всех функциях программы. Например, такой код:def f(): print aa = 1f()напечатает 1 и выполнится без ошибок. Переменная a - глобальная, поэтому мы можем смотреть на её значение из любой функции. На момент вызова функции f переменная a уже создана, хотя описание функции и идет раньше присваивания.Если же инициализировать переменную внутри функции, то использовать её вне функции невозможно. Например, такой код:def f(): a = 1f()print(a)завершится с ошибкой "builtins.NameError: name 'a' is not defined" (переменная a не определена). Переменные, значения которых изменяются внутри функции по умолчанию считаются локальными, т.е. доступными только внутри функции. Как только функция заканчивает свою работу, то переменная уничтожается.Таким образом, если в функции происходило присваивание какой-то переменной, то эта переменная считается локальной. Если присваиваний не происходило, то переменная считается глобальной.Локальные переменные можно называть такими же именами, как и глобальные. Например, вывод такого кода:def f(): a = 1 print(a, end=' ')a = 0f()print(a)Будет "1 0". Сначала произойдет вызов функции f, в которой будет создана локальная переменная a со значением 1 (получить доступ к глобальной переменной a из функции теперь нельзя), затем функция закончит свою работу и будет выведена глобальная переменная a, со значением которой ничего не случилось.Переменная считается локальной даже в случае, если её присваивание происходило внутри условного оператора (даже если он никогда не выполнится):def f(): print(a) if False: a = 0a = 1f()Эта программа завершится с ошибкой builtins.UnboundLocalError: local variable 'a' referenced before assignment (обращение к переменной до инициализации). Любое присваивание значения переменной внутри тела функции делает переменную локальной.С помощью специальной команды global можно сделать так

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

def f():

    global a

    a = 1

    print(a, end=' ')

a = 0

f()

print(a)

выведет "1 1", т.к. значение глобальной переменной будет изменено внутри функции.

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

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

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

Задание по программированию: Проверка числа на простоту

Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Решение оформите в виде функции IsPrime(n), которая возвращает True для простых чисел и False для составных чисел. Программа должна иметь сложность O(корень из n): количество действий в программе должно быть пропорционально квадратному корню из n (иначе говоря, при увеличении входного числа в k раз, время выполнения программы должно увеличиваться примерно в корень из k раз).Формат вводаВводится натуральное число.import mathdef IsPrime(n1):i = 2k = 0while i <= math.sqrt(n1) and n1 % i != 0:i += 1if i > math.sqrt(n1):return "YES"return "NO"n = int(input())print(IsPrime(n))

Рекурсия

Мы уже пробовали запускать функцию из другой функции и все работало. Ничто не мешает запустить из функции саму себя – тогда просто создастся новый экземпляр функции, который будет выполнять те же команды. Такой процесс называется рекурсией. Представим себе, что у нас есть миллиард человек (это будущие экземпляры функции), сидящих в ряд, и у каждого из них есть листочек для записи (это его локальная память). Нам нужно произносить числа и написать инструкцию для людей так, чтобы они в итоге сказали все числа из последовательности в обратном порядке. Пусть каждый из них будет записывать на своем листочке только одно число. Тогда инструкция для человека будет выглядеть так:1) Запиши названное число2) Если число не последнее – потереби следующего за тобой человека, пришла его очередь работать3) Когда следующий за тобой человек сказал, что он закончил – назови записанное число4) Скажи тому, кто тебя теребил (предыдущий человек), что ты закончил Формализуем задачу. Пусть задается последовательность натуральных чисел, заканчивающаяся нулем. Необходимо развернуть ее с помощью рекурсии.def rec(): n = int(input()) if n != 0: rec() print(n)rec()Эта функция осуществляет действие (вывод числа) на рекурсивном спуске, т. е. после рекурсивного вызова.

Использование рекурсии

Рассмотрим задачу, где действия выполняются как на рекурсивном подъёме, так и на рекурсивном спуске. Пусть дана последовательность, которая оканчивается нулём. Необходимо вывести все чётные члены последовательности в прямом порядке, а затем все нечётные члены последовательности в обратном порядке. Её решение будет выглядеть так: def rec(): n = int(input()) if n != 0: if n % 2 == 0: print(n) rec() if n % 2 != 0: print(n)rec()Каждый экземпляр функции считывает в свою локальную переменную n число, если оно чётное, то сразу выводит его и запускает следующий экземпляр. После того, как все последующие экземпляры функции окончили работу (и вывели последующие нечётные числа в обратном порядке), функция выводит число, если оно было нечетным.

Рассмотрим еще один пример: подсчитать факториал числа, не пользуясь циклами:def factorial(n): if n == 0: return 1 return n * factorial(n - 1)n = int(input())print(factorial(n))Тем, кто знаком с методом математической индукции, будет довольно просто осознать рекурсию. Как и в математической индукции, в рекурсии должна быть база (момент, когда функция не вызывает другую рекурсивную функцию) и переход (правило, по которому считается результат по известному результату для меньшего параметра). Наша функция подсчета факториала делает только свою работу, но пользуется результатами чужого труда. Например, если функция получила на вход параметр 4, то должна вернуть 4 умноженное на 3! (который будет посчитан другими функциями). В случае факториала аналогом "базы индукции" может выступать 0! - по определению он равен единице.Эти примеры иллюстрируют общую схему написания рекурсивных функций: сначала проверяется условие, когда функция должна закончиться, а дальше делается все остальное. При этом параметр должен сходиться к значению базы. Обычно это означает, что при каждом следующем вызове рекурсии параметр должен уменьшаться.

Задание по программированию: Возведение в степень

Дано действительное положительное число a и целое неотрицательное число n. Вычислите aⁿ, не используя циклы и стандартную функцию pow, но используя рекуррентное соотношение aⁿ=a⋅aⁿ⁻¹.Решение оформите в виде функции power(a, n) (которая возвращает aⁿ).Формат вводаВводятся действительное положительное число a и целое неотрицательное число n.Формат выводаВыведите ответ на задачу: print(power(a, n)).def power(a, n):if n == 1:return aif n == 0:return 1return a * power(a, n - 1)a = float(input())n = int(input())print(power(a, n))

Задание по программированию: Сложение без сложения

Напишите рекурсивную функцию sum(a, b), возвращающую сумму двух целых неотрицательных чисел. Из всех арифметических операций допускаются только +1 и -1. Также нельзя использовать циклы.Формат вводаВводятся два удовлетворяющих условию задачи числа. Числа не превышают 900.def Sum(a, b):if b >= 0:return a + Sum(1, b - 1)return 0a = int(input())b = int(input())print(Sum(a, b))

Задание по программированию: Быстрое возведение в степень

Возводить в степень можно гораздо быстрее, чем за n умножений! Для этого нужно воспользоваться следующими рекуррентными соотношениями: aⁿ = (a²)ⁿ/² при четном n, aⁿ=a⋅aⁿ⁻¹ при нечетном n. Реализуйте алгоритм быстрого возведения в степень. Если вы все сделаете правильно, то сложность вашего алгоритма будет O(logn).Формат вводаВводится действительное число a и целое неотрицательное число n.def power(a, n):if a == 0:return aif n == 0:return 1if n % 2 == 0:return power(a * a, n / 2)return a * power(a * a, (n - 1) / 2)a = int(input())n = int(input())print(power(a, n))

Задание по программированию: Сократите дробь

Даны два натуральных числа n и m. Сократите дробь (n / m), то есть выведите два других числа p и q таких, что (n / m) = (p / q) и дробь (p / q) — несократимая. Решение оформите в виде функции ReduceFraction(n, m), получающая значения n и m и возвращающей кортеж из двух чисел: return p, q.Тогда вывод можно будет оформить как print(*ReduceFraction(n, m)).Формат вводаВводятся два натуральных числа.def func(a, b):if a != 0 and b != 0:if a > b:a = a % belse:b = b % aelif a > b:return aelse:return breturn func(a, b)a = int(input())b = int(input())d = func(a, b)

Задание по программированию: Сумма последовательности

Дана последовательность чисел, завершающаяся числом 0. Найдите сумму всех этих чисел, не используя цикл.Формат вводаВводится последовательность целых чисел, оканчивающаяся числом 0 (само число 0 в последовательность не входит, а служит как признак ее окончания).Формат выводаВыведите ответ на задачу.def summa(n):n = int(input())if n == 0:return nreturn n + summa(n)n = 0print(summa(n))

Задание по программированию: Разворот последовательности

Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке. При решении этой задачи нельзя пользоваться массивами и прочими динамическими структурами данных.Рекурсия вам поможет.Формат вводаВводится последовательность целых чисел, оканчивающаяся числом 0.def rec(): n = int(input()) if n != 0: rec() print(n)rec()

Кортежи

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