Программирование на языке Python

Программирование на языке Python
§ 54. Введение в язык Python

Простейшая программа
# Это пустая программа
комментарии после #
не обрабатываются
# -*- coding: utf-8 -*-
# Это пустая программа
кодировка utf-8 по умолчанию)
Windows: cp1251
"""
Это тоже комментарий
"""

Вывод на экран
print ( "2+2=?" )
print ( "Ответ: 4" )
Протокол:
2+2=? Ответ: 4
автоматический переход на новую строку
print ( '2+2=?' )
print ( 'Ответ: 4' )

Сложение чисел
Задача. Ввести с клавиатуры два числа и найти их сумму.
Протокол:
Введите два целых числа
25 30
25+30=55
компьютер
пользователь
компьютер считает сам!

Сумма: псевдокод
ввести два числа
вычислить их сумму
вывести сумму на экран
Псевдокод – алгоритм на русском языке с элементами языка программирования.

Переменные
Переменная – это величина, имеющая имя, тип и значение. Значение переменной можно изменять во время работы программы.
a
Значение
Имя

Имена переменных
МОЖНО использовать
латинские буквы (A-Z, a-z)
русские буквы (не рекомендуется!)
цифры
знак подчеркивания _
заглавные и строчные буквы различаются
НЕЛЬЗЯ использовать
скобки
знаки +, =, !, ? и др.
имя не может начинаться с цифры
Какие имена правильные?
AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

Как записать значение в переменную?
a = 5
оператор присваивания
5
Оператор – это команда языка программирования (инструкция).
Оператор присваивания – это команда для записи нового значения переменной.
a
a = 7
7

Ввод значения с клавиатуры
5
a

Ввод значения с клавиатуры
a = input()
ввести строку с клавиатуры и связать с переменной a
b = input()
с = a + b
print ( c )
Протокол:
21
33
2133
a = int( input() )
b = int( input() )
преобразовать в целое число

Ввод двух значений в одной строке
a, b = map ( int, input().split() )
input()
ввести строку с клавиатуры
21 33
input().split()
21
33
разделить строку на части по пробелам
map ( int, input().split() )
21
33
целые
применить
эту операцию
a, b = map ( int, input().split() )

Ввод с подсказкой
a = input ( "Введите число: " )
подсказка
Введите число:
26
a = int( input("Введите число: ") )

Изменение значений переменной
a = 5
b = a + 2
a = (a + 2)*(b – 3)
b = b + 1
a
5
b
=5+2
7
28
=(5+2)*(7-3)
=7+1
8

Вывод данных
print ( a )
значение переменной
print ( "Ответ: ", a )
значение и текст
print ( "Ответ: ", a+b )
вычисление выражения
print ( a, "+", b, "=", c )
2 + 3 = 5
через пробелы
print ( a, "+", b, "=", c, sep = "" )
2+3=5
sep = ""
убрать разделители

Сложение чисел: простое решение
a = int ( input() )
b = int ( input() )
c = a + b
print ( c )

print ( "Введите два числа: " )
a = int ( input() )
b = int ( input() )
c = a + b
print ( a, "+", b, "=", c )
Сложение чисел: полное решение
Протокол:
Введите два целых числа
25 30
25 + 30 = 55
компьютер
пользователь
подсказка

Форматный вывод
print("{:d}+{:d}={:d}".format(a,b,a+b))
a = 5
print ( "{:5d}{:5d}{:5d}".format
(a, a*a, a*a*a) )

Типы переменных
int # целое
float # вещественное
bool # логические значения
str # символьная строка
a = 5
print ( type(a) )
a = 4.5
print ( type(a) )
a = True
print ( type(a) )
a = "Вася"
print ( type(a) )

Зачем нужен тип переменной?
Тип определяет:
область допустимых значений
допустимые операции
объём памяти
формат хранения данных

Размещение переменных в памяти
a = 5
оператор присваивания
5
a
a = 4.5
4.5
«сборщик мусора»
b = a
b
a = 10
4.5
b
10
a

Арифметическое выражения
a = (c + b**5*3 - 1) / 2 * d
Приоритет (старшинство):
скобки
возведение в степень **
умножение и деление
сложение и вычитание
1
2
3
4
5
6
перенос на следующую строку
a = (c + b*5*3
- 1) / 2 * d
перенос внутри скобок разрешён

Деление
Классическое деление:
a = 9; b = 6
x = 3 / 4 # = 0.75
x = a / b # = 1.5
x = -3 / 4 # = -0.75
x = -a / b # = -1.5
Целочисленное деление (округление «вниз»!):
a = 9; b = 6
x = 3 // 4 # = 0
x = a // b # = 1
x = -3 // 4 # = -1
x = -a // b # = -2

Сокращенная запись операций
a += b # a = a + b
a -= b # a = a - b
a *= b # a = a * b
a /= b # a = a / b
a //= b # a = a // b
a %= b # a = a % b
a += 1
увеличение на 1
a = b = 0 # b = 0, a = b
a, b = 1, 2 # a = 1; b = 2
Множественное присваивание:

Программирование на языке Python
§ 55. Вычисления

Остаток от деления
% – остаток от деления
d = 85
b = d // 10 # 8
a = d % 10 # 5
d = a % b # 5
d = b % a # 3
Для отрицательных чисел:
a = -7
b = a // 2 # -4
d = a % 2 # 1
-7 = (-4)*2 + 1
остаток ≥ 0

Вещественные числа
Форматы вывода:
x = 123.456
print( x )
print("{:10.2f}".format(x))
123.456
всего знаков
в дробной части
print("{:10.2g}".format(x))
значащих цифр
1,2 ⋅ 102

Вещественные числа
Экспоненциальный формат:
x = 1./30000
print("{:e}".format(x))
x = 12345678.
print("{:e}".format(x))
3.333333e-05
1.234568e+07
3,333333 ⋅ 10–5
x = 123.456
print("{:e}".format(x))
print("{:10.2e}".format(x))
1.234560e+02
1,234568 ⋅ 107
всего знаков
в дробной части

Стандартные функции
abs(x) — модуль числа
int(x) — преобразование к целому числу
round(x) — округление
x = abs( -1.6 ) # 1.6
x = int( -1.6 ) # -1
x = round( -1.6 ) # -2
bin(x) — в двоичную систему
oct(x) — в восьмеричную систему
hex(x) — в шестнадцатеричную систему
x = bin( 29 ) # '0b11101'
x = oct( 29 ) # '0o35'
x = hex( 29 ) # '0x1d'

Математические функции
math.pi — число «пи»
math.sqrt(x) — квадратный корень
math.sin(x) — синус угла, заданного в радианах
math.cos(x) — косинус угла, заданного в радианах
math.exp(x) — экспонента ех
math.ln(x) — натуральный логарифм
math.floor(x) — округление «вниз»
math.ceil(x) — округление «вверх»
import math
подключить математический модуль
x = math.floor(1.6) # 1
x = math.ceil(1.6) # 2
x = math.floor(-1.6) #-2
x = math.ceil(-1.6) #-1

Документирование программы
from math import sqrt
print("Введите a, b, c:")
a, b, c = map(float, input().split())
D = b*b - 4*a*c
if D < 0:
print("Нет")
else:
x1 = (-b + sqrt(D))/(2*a)
x2 = (-b - sqrt(D))/(2*a)
print("x1={:5.3f} x2={:5.3f}".format(
x1, x2))

Документирование программы
Руководство пользователя:
назначение программы
формат входных данных
формат выходных данных
примеры использования программы
Назначение:
программа для решения уравнения
Формат входных данных:
значения коэффициентов a, b и c вводятся с клавиатуры через пробел в одной строке

Документирование программы
Формат выходных данных:
значения вещественных корней уравнения; если вещественных корней нет, выводится слово «нет»
Примеры использования программы:
1. Решение уравнения
Введите a, b, c: 1 -5 1
x1=4.791 x2=0.209
2. Решение уравнения
Введите a, b, c: 1 1 6
Нет.

Случайные числа
Случайно…
встретить друга на улице
разбить тарелку
найти 10 рублей
выиграть в лотерею
Случайный выбор:
жеребьевка на соревнованиях
выигравшие номера
в лотерее
Как получить случайность?

Случайные числа на компьютере
Электронный генератор
нужно специальное устройство
нельзя воспроизвести результаты
318458191041
564321
209938992481
458191
938992
малый период
(последовательность повторяется через 106 чисел)
Метод середины квадрата (Дж. фон Нейман)
в квадрате
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.
зерно

Линейный конгруэнтный генератор
X = (a*X+b) % c | интервал от 0 до c-1
X = (X+3) % 10 | интервал от 0 до 9
X = 0
зерно
→ 3
→ 6
→ 9
→ 2
→ 5
→ 8
→ 0
зацикливание
8
→ 1
→ 4
→ 7
Компилятор GCC:
a = 1103515245
b = 12345
c = 231

Генератор случайных чисел
Генератор на [0,1):
X = random.random() # псевдослучайное число
Y = random.random() # это уже другое число!
англ. random – случайный
Целые числа на отрезке [a,b]:
X = random.randint(1,6) # псевдосл. число
Y = random.randint(1,6) # уже другое!
import random
Генератор на [a, b] (вещественные числа):
X = random.uniform(1.2, 3.5)
Y = random.uniform(1.2, 3.5)

Генератор случайных чисел
Генератор на [0,1):
X = random(); # псевдослучайное число
Y = random() # это уже другое число!
Целые числа на отрезке [a,b]:
X = randint(10,60) # псевдослучайное число
Y = randint(10,60) # это уже другое число!
from random import *
подключить все!
Генератор на [a, b] (вещественные числа):
X = uniform(1.2, 3.5) # псевдосл. число
Y = uniform(1.2, 3.5) # уже другое число!

Задачи
«A»: Ввести с клавиатуры три целых числа, найти их сумму, произведение и среднее арифметическое.
Пример:
Введите три целых числа:
5 7 8
5+7+8=20
5*7*8=280
(5+7+8)/3=6.667
«B»: Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB.
Пример:
Введите координаты точки A:
5.5 3.5
Введите координаты точки B:
1.5 2
Длина отрезка AB = 4.272

Задачи
«C»: Получить случайное трехзначное число и вывести через запятую его отдельные цифры.
Пример:
Получено число 123.
Его цифры 1, 2, 3.

Программирование на языке Python
§ 56. Ветвления

Условный оператор
Задача: изменить порядок действий в зависимости от выполнения некоторого условия.
полная форма ветвления
if a > b:
M = a
else:
M = b

Условный оператор: неполная форма
неполная форма ветвления
M = a
if b > a:
M = b
M = max(a, b)
Решение в стиле Python:
M = a if a > b else b

Условный оператор
if a < b:
с = a
a = b
b = c
4
6
?
4
6
4
a
b
3
2
1
c
a, b = b, a
Решение в стиле Python:

Знаки отношений
>
<
>=
<=
==
!=
больше, меньше
больше или равно
меньше или равно
равно
не равно

Вложенные условные операторы
if a == b:
print("Одного возраста")
else:
if a > b: print("Андрей старше")
else:
print("Борис старше")
вложенный условный оператор
Задача: в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше?

Каскадное ветвление
if a == b:
print("Одного возраста")
elif a > b:
print("Андрей старше")
else:
print("Борис старше")

Каскадное ветвление
cost = 1500
if cost < 1000:
print ( "Скидок нет." )
elif cost < 2000:
print ( "Скидка 2%." )
elif cost < 5000:
print ( "Скидка 5%." )
else:
print ( "Скидка 10%." )
первое сработавшее условие
Скидка 2%.

Задачи
«A»: Ввести три целых числа, найти максимальное из них.
Пример:
Введите три целых числа:
1 5 4
Максимальное число 5
«B»: Ввести пять целых чисел, найти максимальное из них.
Пример:
Введите пять целых чисел:
1 5 4 3 2
Максимальное число 5

Задачи
«C»: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них старше.
Пример:
Возраст Антона: 15
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Борис старше всех.
Пример:
Возраст Антона: 17
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Антон и Борис старше Виктора.

Сложные условия
Задача: набор сотрудников в возрасте 25-40 лет (включительно).
if :
print("подходит")
else:
print("не подходит")
and
or
not
Приоритет :
отношения (<, >, <=, >=, ==, !=)
not («НЕ»)
and («И»)
or («ИЛИ»)
v >= 25 and v <= 40
сложное условие
«И»
«ИЛИ»
«НЕ»

Задачи
«A»: Напишите программу, которая получает три числа и выводит количество одинаковых чисел в этой цепочке.
Пример:
Введите три числа:
5 5 5
Все числа одинаковые.
Пример:
Введите три числа:
5 7 5
Два числа одинаковые.
Пример:
Введите три числа:
5 7 8
Нет одинаковых чисел.

Задачи
«B»: Напишите программу, которая получает номер месяца и выводит соответствующее ему время года или сообщение об ошибке.
Пример:
Введите номер месяца:
5
Весна.
Пример:
Введите номер месяца:
15
Неверный номер месяца.

Задачи
«C»: Напишите программу, которая получает возраст человека (целое число, не превышающее 120) и выводит этот возраст со словом «год», «года» или «лет». Например, «21 год», «22 года», «25 лет».
Пример:
Введите возраст: 18
Вам 18 лет.
Пример:
Введите возраст: 21
Вам 21 год.
Пример:
Введите возраст: 22
Вам 22 года.

Задачи
«A»: Напишите условие, которое определяет заштрихованную область.
«B»: Напишите условие, которое определяет заштрихованную область.

Задачи
«C»: Напишите условие, которое определяет заштрихованную область.

Программирование на языке Python
§ 57. Циклические алгоритмы

Что такое цикл?
Цикл – это многократное выполнение одинаковых действий.
Два вида циклов:
цикл с известным числом шагов (сделать 10 раз)
цикл с неизвестным числом шагов (делать, пока не надоест)
Задача. Вывести на экран 10 раз слово «Привет».

Повторения в программе
print("Привет“)
print("Привет")
...
print("Привет")

Блок-схема цикла
начало
конец
да
нет
тело цикла

Как организовать цикл?
счётчик = 0
пока счётчик < 10:
print("Привет“)
увеличить счётчик на 1
счётчик = 10
пока счётчик > 0:
print("Привет")
уменьшить счётчик на 1
✔
результат операции автоматически сравнивается с нулём!

Цикл с условием
Задача. Определить количество цифр в десятичной записи целого положительного числа, записанного в переменную n.
счётчик = 0
пока n > 0:
отсечь последнюю цифру n
увеличить счётчик на 1
n = n // 10
счётчик = счётчик + 1
счётчик += 1

Считаем цифры
count = 0
while :
n = n // 10
count += 1
тело цикла
начальное значение счётчика
n > 0
условие продолжения
заголовок цикла

Максимальная цифра числа
n = int(input())
M = -1
while n > 0:
d = n % 10
if d > M:
M = d
n = n // 10
print( M )
отсечь последнюю цифру
последняя цифра
пока остались цифры
поиск максимума
Задача. Определить максимальную цифру в десятичной записи целого положительного числа, записанного в переменную n.

Цикл с условием
k = 0
while k < 10:
print ( "привет" )
k += 1
При известном количестве шагов:
k = 0
while k < 10:
print ( "привет" )
Зацикливание:

Сколько раз выполняется цикл?
a = 4; b = 6
while a < b: a += 1
2 раза
a = 6
a = 4; b = 6
while a < b: a += b
1 раз
a = 10
a = 4; b = 6
while a > b: a += 1
0 раз
a = 4
a = 4; b = 6
while a < b: b = a - b
1 раз
b = -2
a = 4; b = 6
while a < b: a -= 1
зацикливание

Задачи
«A»: Напишите программу, которая получает два целых числа A и B (0 < A < B) и выводит квадраты всех натуральных чисел в интервале от A до B.
Пример:
Введите два целых числа:
10 12
10*10=100
11*11=121
12*12=144
«B»: Напишите программу, которая получает два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрицательными.
Пример:
Введите два числа:
10 -15
10*(-15)=-150

Задачи
«C»: Ввести натуральное число N и вычислить сумму всех чисел Фибоначчи, меньших N. Предусмотрите защиту от ввода отрицательного числа N.
Пример:
Введите число N:
10000
Сумма 17709

Задачи-2
«A»: Ввести натуральное число и найти сумму его цифр.
Пример:
Введите натуральное число:
12345
Сумма цифр 15.
«B»: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры, стоящие рядом.
Пример:
Введите натуральное число:
12342
Нет.
Пример:
Введите натуральное число:
12245
Да.

Задачи-2
«C»: Ввести натуральное число и определить, верно ли, что в его записи есть две одинаковые цифры (не обязательно стоящие рядом).
Пример:
Введите натуральное число:
12342
Да.
Пример:
Введите натуральное число:
12345
Нет.

Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока они не станут равны. Это число и есть НОД исходных чисел.
НОД(14,21) = НОД(14,7) = НОД(7, 7) = 7
пока a != b:
если a > b:
a -= b # a = a - b
иначе:
b -= a # b = b - a
while a != b:
if a > b:
a -= b
else:
b -= a
НОД(1998,2) =
НОД(1996,2) = … = НОД(2, 2) = 2

Алгоритм Евклида
Модифицированный алгоритм Евклида. Заменять большее число на остаток от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Другое (ненулевое) число и есть НОД чисел.
НОД(1998,2) = НОД(0,2) = 2
пока ???:
если a > b:
a = a % b
иначе:
b = b % a
a!=0 and b!=0:
если a != 0:
вывести a
иначе:
вывести b

Задачи
«3»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида.
Пример:
Введите два числа:
21 14
НОД(21,14)=7
«4»: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью модифицированного алгоритма Евклида. Заполните таблицу:

Задачи
«5»: Ввести с клавиатуры два натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида.
Пример:
Введите два числа:
1998 2
НОД(1998,2)=2
Обычный алгоритм: 998
Модифицированный: 1

Цикл с постусловием
while True:
if n > 0: break
условие выхода
print ( "Введите положительное число:" )
n = int ( input() )
тело цикла
при входе в цикл условие не проверяется
цикл всегда выполняется хотя бы один раз
Задача. Обеспечить ввод положительного числа в переменную n.
бесконечный цикл
прервать цикл

Программирование на языке Python
§ 58. Циклы по переменной

Цикл с переменной
Задача. Вывести 10 раз слово «Привет!».
while :
print("Привет!")
i = 0
i < 10
i += 1
for :
print("Привет!")
i in range(10)
в диапазоне [0,10)
Цикл с переменной:
range(10) → 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Цикл с переменной
Задача. Вывести все степени двойки от 21 до 210.
while : print ( 2**k )
k = 1
k <= 10
k += 1
for :
print ( 2**k )
k in range(1,11)
в диапазоне [1,11)
Цикл с переменной:
range(1,11) → 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Цикл с переменной: другой шаг
100
81
64
49
36
25
16
9
4
1
1
9
25
49
81
for :
print ( k**2 )
k in range(1,11,2)
for :
print ( k**2 )
k in range(10,0,-1)
шаг
10,9,8,7,6,5,4,3,2,1
1,3,5,7,9

Сколько раз выполняется цикл?
a = 1
for i in range( 3): a += 1
a = 4
a = 1
for i in range( 3,1): a += 1
a = 1
a = 1
for i in range( 1,3,-1): a += 1
a = 1
a = 1
for i in range( 3,1,-1): a += 1
a = 3

Задачи
«A»: Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111.
«B»: Натуральное число называется числом Армстронга, если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 13 + 53 + 33. Найдите все трёхзначные Армстронга.

Задачи
«С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 252 = 625. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N.
Пример:
Введите N:
1000
1*1=1
5*5=25
6*6=36
25*25=625
76*76=5776

Вложенные циклы
Задача. Вывести все простые числа в диапазоне
от 2 до 1000.
сделать для n от 2 до 1000
если число n простое то
вывод n
число n простое
нет делителей [2.. n-1]: проверка в цикле!
for n in range(2, 1001):
if число n простое:
print( n )

Вложенные циклы
for n in range(2, 1001):
count = 0
if count == 0:
print( n )
for k in range(2,n):
if n % k == 0:
count += 1
вложенный цикл

Вложенные циклы
for i in range(1,4):
for k in range(1,4):
print( i, k )
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Вложенные циклы
for i in range(1,5):
for k in range(1,i+1):
print( i, k )
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4

Поиск простых чисел – как улучшить?
count = 0
k = 2
while :
if n % k == 0:
count += 1
k += 1
while k <= math.sqrt(n):
…
while k*k <= n:
if n % k == 0: break
k += 1
if k*k > n:
print ( n )
k*k <= n
выйти из цикла
если вышли по условию

Задачи
«A»: Напишите программу, которая получает натуральные числа A и B (A выводит все простые числа в интервале от A до B.
Пример:
Введите границы диапазона:
10 20
11 13 17 19
«B»: В магазине продается мастика в ящиках по 15 кг,
17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?

Задачи
«C»: Ввести натуральное число N и вывести все натуральные числа, не превосходящие N и делящиеся на каждую из своих цифр.
Пример:
Введите N:
15
1 2 3 4 5 6 7 8 9 11 12 15

Программирование на языке Python
§ 59. Процедуры

Зачем нужны процедуры?
print ( "Ошибка программы" )
много раз!
def Error():
print( "Ошибка программы" )
n = int ( input() )
if n < 0:
Error()
вызов процедуры
Процедура:
define определить

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

Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде.
много раз!
Алгоритм:
178
⇒
101100102
7 6 5 4 3 2 1 0
1 0 1 1 0 0 1 02
разряды
n:=
n // 128
n % 128
n1 // 64

Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде.
Решение:
k = 128
while k > 0:
print ( n // k,
end = "" )
n = n % k
k = k // 2
178
⇒
10110010

Процедура с параметрами
printBin ( 99 )
значение параметра (аргумент)
def printBin( n ):
k = 128
while k > 0:
print ( n // k, end = "" )
n = n % k;
k = k // 2
Параметры – данные, изменяющие работу процедуры.
локальная переменная
def printSred( a, b ):
print ( (a + b)/2 )
Несколько параметров:

Локальные и глобальные переменные
a = 5
def qq():
a = 1
print ( a )
qq()
print ( a )
глобальная переменная
локальная переменная
1
5
a = 5
def qq():
print ( a )
qq()
5
a = 5
def qq():
global a
a = 1
qq()
print ( a )
1
global a
работаем с
глобальной переменной

Неправильная процедура
x = 5; y = 10
def xSum():
print ( x+y )
xSum()
def xSum():
print ( x+y )
процедура связана с глобальными переменными, нельзя перенести в другую программу
печатает только сумму x и y, нельзя напечатать сумму других переменных или сумму x*y и 3x
передавать данные через параметры

Правильная процедура
x = 5; y = 10
Sum2( x, y )
z=17; w=3
Sum2( z, w )
Sum2( z+x, y*w )
def Sum2(a, b):
print ( a+b )
a
b
x
y
z
w
5
10
17
3
22
30
15
20
52
Глобальные:
Локальные:
процедура не зависит от глобальных переменных
легко перенести в другую программу
печатает только сумму любых выражений

Задачи
«A»: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'.
Пример:
Введите N:
10
----------
«B»: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.
Пример:
Введите натуральное число:
1234
1
2
3
4

Задачи
«C»: Напишите процедуру, которая выводит на экран запись переданного ей числа в римской системе счисления.
Пример:
Введите натуральное число:
2013
MMXIII

Программирование на языке Python
§ 60. Функции

Что такое функция?
Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа).
s = input()
n = int( s )
x = randint( 10, 20 )

Что такое функция?
def lastDigit( n ):
d = n % 10
return d
Задача. Написать функцию, которая вычисляет младшую цифру числа (разряд единиц).
return d
передача результата
результат работы функции – значение d
# вызов функции
k = lastDigit( 1234 )
print( k )

Сумма цифр числа
def sumDigits( n ):
sum = 0
while n!= 0: sum += n % 10
n = n // 10
return sum
return sum
передача результата
Задача. Написать функцию, которая вычисляет сумму цифр числа.
# основная программа
sumDigits(12345)
# сразу вывод на экран
print ( sumDigits(12345) )
# сохранить в переменной
n = sumDigits(12345)

Использование функций
x = 2*sumDigits( n+5 )
z = sumDigits( k ) + sumDigits( m )
if sumDigits( n ) % 2 == 0:
print ( "Сумма цифр чётная" )
print ( "Она равна", sumDigits( n ) )
Одна функция вызывает другую:
def middle ( a, b, c ):
mi = min ( a, b, c )
ma = max ( a, b, c )
return a + b + c - mi - ma
вызываются min и max

Задачи
«A»: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
«B»: Напишите функцию, которая определяет сумму цифр переданного ей числа.
Пример:
Введите натуральное число:
123
Сумма цифр числа 123 равна 6.

Задачи
«C»: Напишите функцию, которая «переворачивает» число, то есть возвращает число, в котором цифры стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После переворота: 4321.

Как вернуть несколько значений?
def divmod ( x, y ):
d = x // y
m = x % y
return d, m
d – частное,
m – остаток
a, b = divmod ( 7, 3 )
print ( a, b ) # 2 1
q = divmod ( 7, 3 )
print ( q ) # (2, 1)
(2, 1)
кортеж – набор элементов
q[0]
q[1]

Задачи
«A»: Напишите функцию, которая переставляет три переданные ей числа в порядке возрастания.
Пример:
Введите три натуральных числа:
10 15 5
5 10 15
«B»: Напишите функцию, которая сокращает дробь вида M/N.
Пример:
Введите числитель и знаменатель дроби:
25 15
После сокращения: 5/3

Задачи
«C»: Напишите функцию, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел.
Пример:
Введите два натуральных числа:
10 15
НОД(10,15)=5
НОК(10,15)=30

Логические функции
def even(n):
if n % 2 == 0:
return True
else: return False
Логическая функция – это функция, возвращающая логическое значение (True/False).
def even(n):
return (n % 2 == 0)
k = int( input() )
if even( k ):
print( "Число", k, "чётное." )
else:
print( "Число", k, "нечётное." )

Логические функции
Задача. Найти все простые числа в диапазоне
от 2 до 1000.
for i in range(2,1001):
if i - простое :
print ( i )
i - простое
isPrime(i)
функция, возвращающая логическое значение (True/False)

Функция: простое число или нет?
def isPrime ( n ):
k = 2 while k*k <= n and n % k != 0:
k += 1
return (k*k > n)
return (k*k > n)
if k*k > n:
return True
else:
return False

Логические функции: использование
n = int ( input() )
while isPrime(n):
print ( n, "– простое число" )
n = int ( input() )

Задачи
«A»: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого.
Пример:
Введите натуральное число:
28
Число 28 совершенное.
Пример:
Введите натуральное число:
29
Число 29 не совершенное.

Задачи
«B»: Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1.
Пример:
Введите два натуральных числа:
28 15
Числа 28 и 15 взаимно простые.
Пример:
Введите два натуральных числа:
28 16
Числа 28 и 16 не взаимно простые.

Задачи
«С»: Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике.
Пример:
Введите натуральное число:
733
Число 733 гиперпростое.
Пример:
Введите натуральное число:
19
Число 19 не гиперпростое.

Программирование на языке Python
§ 61. Рекурсия

Что такое рекурсия?
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…

Что такое рекурсия?
Натуральные числа:
индуктивное определение
Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
Числа Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, …

Фракталы
Фракталы – геометрические фигуры, обладающие самоподобием.
Треугольник Серпинского:

Ханойские башни
за один раз переносится один диск
класть только меньший диск на больший
третий стержень вспомогательный
перенести (n-1, 1, 2)
1 -> 3
перенести (n-1, 2, 3)
перенести (n, 1, 3)

Ханойские башни – процедура
def Hanoi ( n, k, m ):
p = 6 - k - m
Hanoi ( n-1, k, p )
print ( k, "->", m )
Hanoi ( n-1, p, m )
номер вспомогательного стержня (1+2+3=6!)
сколько
откуда
куда
рекурсия
рекурсия

Ханойские башни – процедура
Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции.
def Hanoi ( n, k, m ):
p = 6 - k - m
Hanoi ( n-1, k, p )
print ( k, "->", m )
Hanoi ( n-1, p, m )
if n == 0: return
условие выхода из рекурсии
# основная программа
Hanoi( 4, 1, 3 )

Вычисление суммы цифр числа
Задача. Написать рекурсивную функцию, которая вычисляет сумму цифр числа.
s = sumDigits( 1234 )
n // 10
n % 10
sumDigits( n )= sumDigits( n // 10 )+(n % 10)
sumDigits( n )= n для n < 10
n

Вычисление суммы цифр числа
def sumDigits ( n ):
if n < 10: return n
d = n % 10
sum = d + sumDigits ( n // 10 )
return sum
рекурсивный вызов
sumDigits( 1234 )
4 + sumDigits( 123 )
4 + 3 + sumDigits( 12 )
4 + 3 + 2 + sumDigits( 1 )
4 + 3 + 2 + 1
последняя цифра

Вычисление суммы цифр числа
sumDigits ( 123 )
d = 3
sum = 3 + sumDigits ( 12 )
return 6
sumDigits ( 12 )
d = 2
sum = 2 + sumDigits ( 1 )
return 3
sumDigits ( 1 )
return 1

Вывод двоичного кода числа
def printBin ( n ):
if n == 0: return
printBin ( n // 2 )
print ( n % 2, end = "" )
условие выхода из рекурсии
напечатать все цифры, кроме последней
вывести последнюю цифру
10011
printBin( 19 )
printBin( 9 )
printBin( 4 )
printBin( 2 )
printBin( 1 )
printBin( 0 )
Задача. Написать рекурсивную процедуру, которая выводит двоичную запись числа.

Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.
def NOD ( a, b ):
if a == 0 or b == 0:
if a > b:
return NOD( a - b, b )
else:
return NOD( a, b – a )
return a + b;
рекурсивные вызовы
условие окончания рекурсии

Задачи
«A»: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574)=1234.
«B»: Напишите рекурсивную функцию, которая раскладывает число на простые сомножители.
Пример:
Введите натуральное число:
378
378 = 2*3*3*3*7

Задачи
«C»: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной функции.
Пример:
Введите натуральное число:
4
Количество разложений: 4.

Как работает рекурсия?
def Fact(N):
print ( "->", N )
if N <= 1: F = 1
else:
F = N * Fact ( N – 1 )
print ( "<-", N )
return F
-> N = 3
-> N = 2
-> N = 1
<- N = 1
<- N = 2
<- N = 3
Факториал:

Стек
Стек – область памяти, в которой хранятся локальные переменные и адреса возврата.
Fact(3)
Fact(2)
Fact(1)
значение параметра
адрес возврата
локальная переменная

Рекурсия – «за» и «против»
с каждым новым вызовом расходуется память в стеке (возможно переполнение стека)
затраты на выполнение служебных операций при рекурсивном вызове
программа становится более короткой и понятной
возможно переполнение стека
замедление работы
def Fact ( n ):
f = 1
for i in range(2,n+1):
f *= i
return f
итерационный алгоритм

Анализ рекурсивных функций
Задача. Что выведет эта программа?
def f( x ):
if x < 3:
return 1
else:
return f( x-1 ) + 2
print( f( 5 ) )
Метод подстановки:
f(5) = f(4) + 2
f(4) = f(3) + 2
f(3) = f(2) + 2
f(2) = 1
= 3 + 2 = 5
= 1 + 2 = 3
линейная структура

Анализ рекурсивных функций
Задача. Что выведет эта программа?
def f( x ):
if x < 3:
return 1
else:
return f(x-1) + 2* f(x-2)
print( f( 5 ) )
дерево
3
3
5
11

Анализ рекурсивных функций
Чему равно f (5)?
Табличный метод :
11
f(3) = f(2) + 2*f(1) = 3
f(4) = f(3) + 2*f(2) = 5
f(5) = f(4) + 2*f(3) = 11

Анализ рекурсивных функций
Задача. Сколько звёздочек выведет эта программа?
def f( x ): if x > 0: g(x-1)
def g( x ):
print( "*" )
if x > 1: f(x-3)
f( 11 )

Анализ рекурсивных функций
Задача. Сколько звёздочек выведет эта программа?
def f( x ): if x > 0:
g( x-1 )
f( x-2 )
print( "*" )
def g( x ):
print( "*" )
if x > 1: f(x-3)
f( 9 )

Анализ рекурсивных функций
f (1) = g(0) + f (–1) + 1 = 3
f (2) = g(1) + f (0) + 1 = 3
g (2) = 1 + f (–1) = 2

Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[email protected]