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

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

Например, такой код:

def f():

    print a

a = 1

f()

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

Если же инициализировать переменную внутри функции, то использовать её вне функции невозможно. Например, такой код:

def f():

    a = 1

f()

print(a)

завершится с ошибкой "builtins.NameError: name 'a' is not defined" (переменная a не определена). Переменные, значения которых изменяются внутри функции по умолчанию считаются локальными, т.е. доступными только внутри функции. Как только функция заканчивает свою работу, то переменная уничтожается.

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

Локальные переменные можно называть такими же именами, как и глобальные. Например, вывод такого кода:

def f():

    a = 1

    print(a, end=' ')

a = 0

f()

print(a)

Будет "1 0". Сначала произойдет вызов функции f, в которой будет создана локальная переменная a со значением 1 (получить доступ к глобальной переменной a из функции теперь нельзя), затем функция закончит свою работу и будет выведена глобальная переменная a, со значением которой ничего не случилось.

Переменная считается локальной даже в случае, если её присваивание происходило внутри условного оператора (даже если он никогда не выполнится):

def f():

    print(a)

    if False:

        a = 0

a = 1

f()

Эта программа завершится с ошибкой 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 math

def IsPrime(n1):
i = 2
k = 0
while i <= math.sqrt(n1) and n1 % i != 0:
i += 1
if 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 a
if n == 0:
return 1
return 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 0

a = 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 a
if n == 0:
return 1
if 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 % b
else:
b = b % a
elif a > b:
return a
else:
return b
return 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 n
return n + summa(n)

n = 0
print(summa(n))

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

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

Формат ввода

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

def rec():

    n = int(input())

    if n != 0:

        rec()

    print(n)

rec()

Кортежи

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