Программирование Питон

Зачем нужен тип переменной?

Тип определяет:

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

Как записать значение в переменную?

!

оператор присваивания

При записи нового значения старое удаляется из памяти!

a

a = 5

5

7

a = 7

Оператор – это команда языка программирования (инструкция).

Оператор присваивания – это команда для записи нового значения переменной.

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

a

5

!

• Программа ждет, пока пользователь введет значение и нажмет Enter .
• Введенное значение записывается в переменную a (связывается с именем a )

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

ввести строку с клавиатуры и связать с переменной a

a = input ()

b = input ()

Протокол:

21

33

2133

с = a + b

?

print ( c )

Почему?

!

Результат функции input – строка символов!

преобразовать в целое число

a = int ( input () )

b = int ( input () )

Ввод двух значений в одной строке

a, b = map ( int , input (). split () )

input ()

21 33

ввести строку с клавиатуры

21

33

input (). split ()

разделить строку на части по пробелам

целые

применить

map ( int , input (). split () )

33

21

эту операцию

к каждой части

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

28

= (5+2)*(7-3)

a

5

b

7

= 5+2

8

= 7+1

Вывод данных

значение переменной

print ( a )

print ( "Ответ: " , a )

значение и текст

перечисление через запятую

вычисление выражения

print ( "Ответ: " , a+b )

print ( a, "+" , b, "=" , c )

через пробелы

2 + 3 = 5

sep = ""

print ( a, "+" , b, "=" , c, sep = "" )

2+3=5

убрать разделители

Сложение чисел: простое решение

a = int ( input () )

b = int ( input () )

c = a + b

print ( c )

?

Что плохо?

Сложение чисел: полное решение

p rint ( "Введите два числа: " )

a = int ( input () )

b = int ( input () )

c = a + b

print ( a, "+" , b, "=" , c )

подсказка

компьютер

Протокол:

Введите два целых числа

25 30

25+30=55

пользователь

Форматный вывод

целое

a = 123

print ( "{:5d}" . format (a) )

123

5

5 знаков

a = 123

print ( "{:5d}{:5d}{:5d}" . format

(a, a*a, a*a*a) )

2 5

12 5

5

5 знаков

5 знаков

5 знаков

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

§ 56. Вычисления

Типы данных

• int # целое float # вещественное bool # логические значения str # символьная строка
• int # целое
• float # вещественное
• bool # логические значения
• str # символьная строка

a = 5

print ( type (a) )

a = 4.5

print ( type (a) )

a = True

print ( type (a) )

a = " Вася "

print ( type (a) )

Арифметическое выражения

3

5

4

6

2

1

a = (c + b ** 5 * 3 - 1 ) / 2 * d

Приоритет ( старшинство ):

• скобки
• возведение в степень **
• умножение и деление
• сложение и вычитание

перенос на следующую строку

\

a = (c + b * 5 * 3 - 1 ) \

/ 2 * d

перенос внутри скобок разрешён

a = (c + b * 5 * 3

- 1 ) / 2 * d

30

Деление

Классическое деление:

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

Остаток от деления

% – остаток от деления

• % – остаток от деления

d = 85

b = d // 0 # 8

a = d % 10 # 5

d = a % b # 5

d = b % a # 3

• d = 85 b = d // 0 # 8 a = d % 10 # 5 d = a % b # 5 d = b % a # 3

Для отрицательных чисел :

• Для отрицательных чисел :

!

Как в математике!

a = -7

b = a // 2 # -4

d = a % 2 # 1

• a = -7 b = a // 2 # -4 d = a % 2 # 1

остаток  0

-7 = ( -4 )*2 + 1

Сокращенная запись операций

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 += 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

Вещественные числа

!

Целая и дробная части числа разделяются точкой !

Форматы вывода :

x = 123.456

print ( x )

print ( "{:10.2f}" . format (x))

123.456

123.46

всего знаков

в дробной части

print ( "{:10.2g}" . format (x))

1.2e+02

значащих цифр

1,2  10 2

Вещественные числа

Экспоненциальный формат :

3,333333  10 –5

x = 1. / 30000

print ( "{:e}" . format (x))

x = 12345678.

print ( "{:e}" . format (x))

3 .333333e - 0 5

1.234568e+07

1,234568  10 7

x = 123.456

print ( "{:e}" . format ( x))

print ( "{:10.2e}" . format ( x))

1.234560 e +02

1.23e+02

всего знаков

в дробной части

Стандартные функции

abs (x) — модуль числа

int (x) — преобразование к целому числу

round (x) — округление

sqrt (x) — квадратный корень

sin (x) — синус угла, заданного в радианах

cos (x) — косинус угла, заданного в радианах

exp (x) — экспонента е х

ln (x) — натуральный логарифм

floor (x) — округление «вниз»

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

Случайные числа

Случайно…

Случайный выбор :

• встретить друга на улице
• разбить тарелку
• найти 10 рублей
• выиграть в лотерею

• жеребьевка на соревнованиях
• выигравшие номера в лотерее

Как получить случайность?

Случайные числа на компьютере

Электронный генератор

• нужно специальное устройство
• нельзя воспроизвести результаты

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

Метод середины квадрата (Дж. фон Нейман)

зерно

в квадрате

564321

• малый период (последовательность повторяется через 10 6 чисел)

458191

318458191041

209938992481

938992

Генератор случайных чисел

import random

англ. random – случайный

Генератор на [0,1) :

X = r a ndom () ; # псевдослучайное число

Y = r a ndom () # это уже другое число!

Целые числа на отрезке [a,b] :

X = randint (a, b ) # псевдослучайное число

Y = randint (a, b ) # это уже другое число!

Задачи

« 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

§ 57. Ветвления

b? ? M = a M = b Если a = b? if a b: M = a else : M = b вывод M отступы " width="640"

Условный оператор

Задача: изменить порядок действий в зависимости от выполнения некоторого условия.

полная форма ветвления

да

нет

a b?

?

M = a

M = b

Если a = b?

if a b:

M = a

else :

M = b

вывод M

отступы

a: M = b M = a да нет b a? M = b неполная форма ветвления вывод M Решение в стиле Python: M = max (a, b) M = a if a b else b " width="640"

Условный оператор: неполная форма

M = a

if b a:

M = b

M = a

да

нет

b a?

M = b

неполная форма ветвления

вывод M

Решение в стиле Python:

M = max (a, b)

M = a if a b else b

b: с = a a = b b = c ? Что делает ? b a 4 6 6 4 ? Можно ли обойтись без переменной c ? 4 ? Решение в стиле Python: c a , b = b, a " width="640"

3

2

1

Условный оператор

if a b:

с = a

a = b

b = c

?

Что делает ?

b

a

4

6

6

4

?

Можно ли обойтись

без переменной c ?

4

?

Решение в стиле Python:

c

a , b = b, a

больше, меньше = больше или равно = меньше или равно = = равно != не равно " width="640"

Знаки отношений

больше, меньше

=

больше или равно

=

меньше или равно

= =

равно

!=

не равно

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

Вложенные условные операторы

Задача : в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше?

?

Сколько вариантов ?

if a b:

print ( " Андрей старше " )

else :

if a == b:

print ( " Одного возраста " )

else :

print ( " Борис старше " )

вложенный условный оператор

?

Зачем нужен ?

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

Каскадное ветвление

if a b:

print ( " Андрей старше " )

elif a == b:

print ( " Одного возраста " )

else :

print ( " Борис старше " )

!

elif = else if

Каскадное ветвление

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 and v 40 if : print ( "не подходит" ) else : print ( "не подходит " ) or «ИЛИ» not «НЕ» Приоритет : отношения ( , , , = , == , != ) not («НЕ») and («И») or («ИЛИ») " width="640"

Сложные условия

Задача : набор сотрудников в возрасте 25-40 лет (включительно).

сложное условие

and

«И»

v = 25 and v 40

if :

print ( "не подходит" )

else :

print ( "не подходит " )

or

«ИЛИ»

not

«НЕ»

Приоритет :

• отношения ( , , , = , == , != )

• not («НЕ»)
• and («И»)
• or («ИЛИ»)

Задачи

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

Пример :

Введите три числа:

5 5 5

Все числа одинаковые.

Пример :

Введите три числа:

5 7 5

Два числа одинаковые.

Пример :

Введите три числа:

5 7 8

Нет одинаковых чисел.

Задачи

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

Пример :

Введите номер месяца:

5

Весна.

Пример :

Введите номер месяца:

15

Неверный номер месяца.

Задачи

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

Пример :

Введите возраст: 18

Вам 18 лет.

Пример :

Введите возраст: 21

Вам 21 год.

Пример :

Введите возраст: 2 2

Вам 22 года.

Задачи

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

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

Задачи

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

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

§ 58. Циклические алгоритмы

Что такое цикл?

Цикл – это многократное выполнение одинаковых действий.

Два вида циклов :

• Два вида циклов :

• цикл с известным числом шагов ( сделать 10 раз ) цикл с неизвестным числом шагов (делать, пока не надоест)
• цикл с известным числом шагов ( сделать 10 раз )
• цикл с неизвестным числом шагов (делать, пока не надоест)

Задача . Вывести на экран 10 раз слово «Привет».

?

Можно ли решить известными методами ?

Повторения в программе

print ( " Привет “ )

print ( " Привет " )

...

print ( " Привет " )

?

Что плохо ?

Блок-схема цикла

начало

да

конец

нет

тело цикла

0 : print ( " Привет " ) уменьшить счётчик на 1  ? Какой способ удобнее для процессора ? " width="640"

Как организовать цикл?

счётчик = 0

пока счётчик 10 :

print ( " Привет “ )

увеличить счётчик на 1

результат операции автоматически сравнивается с нулём!

счётчик = 10

пока счётчик 0 :

print ( " Привет " )

уменьшить счётчик на 1



?

Какой способ удобнее для процессора ?

0 : отсечь последнюю цифру n увеличить счётчик на 1 ? Как отсечь последнюю цифру ? n = n // 10 ? Как увеличить счётчик на 1 ? счётчик = счётчик + 1 счётчик + = 1 " width="640"

Цикл с условием

Задача . Определить количество цифр в десятичной записи целого положительного числа, записанного в переменную n .

n

счётчик

1234

0

123

1

12

2

1

0

3

4

счётчик = 0

пока n 0 :

отсечь последнюю цифру n

увеличить счётчик на 1

?

Как отсечь последнюю цифру ?

n = n // 10

?

Как увеличить счётчик на 1 ?

счётчик = счётчик + 1

счётчик + = 1

0 n = n // 10 count += 1 тело цикла ! Цикл с предусловием – проверка на входе в цикл! " width="640"

Цикл с условием

начальное значение счётчика

условие продолжения

count = 0 ;

while :

заголовок цикла

n 0

n = n // 10

count += 1

тело цикла

!

Цикл с предусловием – проверка на входе в цикл!

Цикл с условием

При известном количестве шагов:

k = 0

while k 10 :

print ( "привет" )

k += 1

Зацикливание:

k = 0

while k 10 :

print ( "привет" )

b: a += 1 1 раз b = -2 a = 4 ; b = 6 while a b: b = a - b зацикливание a = 4 ; b = 6 while a b: a -= 1 " width="640"

Сколько раз выполняется цикл?

2 раза

a = 6

a = 4 ; b = 6

while a b: a += 1

1 раз

a = 10

a = 4 ; b = 6

while a b: a += b

0 раз

a = 4

a = 4 ; b = 6

while a b: a += 1

1 раз

b = -2

a = 4 ; b = 6

while a b: b = a - b

зацикливание

a = 4 ; b = 6

while a b: a -= 1

0 : break print ( "Введите положительное число:" ) n = int ( input () ) тело цикла условие выхода прервать цикл при входе в цикл условие не проверяется цикл всегда выполняется хотя бы один раз " width="640"

Цикл с постусловием

Задача . Обеспечить ввод положительного числа в переменную n .

бесконечный цикл

while True :

if n 0 : break

print ( "Введите положительное число:" )

n = int ( input () )

тело цикла

условие выхода

прервать цикл

• при входе в цикл условие не проверяется
• цикл всегда выполняется хотя бы один раз

Задачи

« A »: Напишите программу, которая получает два целых числа A и B (0

Пример :

Введите два целых числа:

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

Нет.

Пример :

Введите натуральное число:

12 2 4 5

Да.

Задачи-2

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

Пример :

Введите натуральное число:

12342

Да.

Пример :

Введите натуральное число:

1234 5

Нет.

Цикл с переменной

Задача . Вывести 10 раз слово «Привет!».

?

Можно ли сделать с циклом «пока» ?

 

while :

print ( " Привет!" )

 

i = 0 ;

i 10

i + = 1

Цикл с переменной:

в диапазоне [0, 10 )

for :

print ( " Привет! " )

i in range ( 10 )

!

Не включая 10 !

range ( 10 )  0 , 1, 2, 3, 4, 5, 6, 7, 8, 9

Цикл с переменной

Задача . Вывести все степени двойки от 2 1 до 2 10 .

?

Как сделать с циклом «пока» ?

 

while :

print ( 2 **k )

 

k = 0 ;

k 10

k + = 1

Цикл с переменной:

в диапазоне [ 1 , 11 )

for :

print ( 2 **k )

k in range ( 1 , 11 )

!

Не включая 1 1 !

range ( 1 , 11 )  1, 2, 3, 4, 5, 6, 7, 8, 9 , 10

Цикл с переменной: другой шаг

10, 9 ,8,7,6,5,4,3,2,1

шаг

10 0

81

64

49

36

25

16

9

4

1

for :

print ( k** 2 )

k in range ( 10 , 0 , -1 )

?

Что получится ?

1,3,5,7,9

1

9

25

49

81

for :

print ( k** 2 )

k in range ( 1 , 11 , 2 )

Сколько раз выполняется цикл?

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

a = 1

for i in range ( 1 , 3 , -1 ): a += 1

a = 3

a = 1

for i in range ( 3 , 1 , -1 ): a += 1

Задачи

« A »: Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111.

« B »: Натуральное число называется числом Армстронга , если сумма цифр числа, возведенных в N-ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 1 3 + 5 3 + 3 3 . Найдите все трёхзначные Армстронга.

Задачи

«С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 25 2 = 6 25 . Напишите программу, которая получает натуральное число 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 , 1000 1 ):

if число n простое :

print ( n )

Вложенные циклы

for n in range( 2 , 1000 1 ) :

count = 0 ;

if count == 0 :

print ( n )

for k in range ( 2 ,n):

if n % k == 0 :

count += 1

вложенный цикл

Вложенные циклы

1 1

2 1

2 2

3 1

3 2

3 3

4 1

4 2

4 3

4 4

for i in range( 1 , 45 ):

for k in range( 1 ,i+1):

print ( i, k )

?

Как меняются переменные?

!

Переменная внутреннего цикла изменяется быстрее!

n : print ( n ) если вышли по условию " width="640"

Поиск простых чисел – как улучшить?

while k math. sqrt ( n ):

…

?

Что плохо?

count = 0

k = 2

while :

if n % k == 0 :

count += 1

k += 1

?

Как ещё улучшить?

k*k n

выйти из цикла

while k*k n:

if n % k == 0 : break

k += 1

if k * k n :

print ( n )

если вышли по условию

Задачи

« A »: Напишите программу, которая получает натуральные числа A и B (A

Пример :

Введите границы диапазона:

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 ( "Ошибка программы" )

define определить

n = int ( input () )

if n 0 :

Error()

вызов процедуры

Что такое процедура?

Процедура – вспомогательный алгоритм, который выполняет некоторые действия.

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

Процедура с параметрами

Задача . Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде.

много раз!

Алгоритм:

178



10110010 2

?

Как вывести первую цифру ?

разряды

7 6 5 4 3 2 1 0

1 0 1 1 0 0 1 0 2

n :=

n / / 128

n % 128

?

n 1 // 64

Как вывести вторую цифру ?

0 : print ( n // k, end = "" ) n = n % k k = k // 2  10110010 178 ! Результат зависит от n ! " width="640"

Процедура с параметрами

Задача . Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде.

Решение:

n

k

178

50

вывод

128

64

50

1

0

32

18

16

1

2

2

1

8

4

2

0

0

2

0

1

1

0

0

0

k = 128

while k 0 :

print ( n // k,

end = "" )

n = n % k

k = k // 2



10110010

178

!

Результат зависит от n !

0 : print ( n // k, end = "" ) n = n % k; k = k // 2 локальная переменная значение параметра ( аргумент ) printBin ( 99 ) Несколько параметров: def printSred( a, b ): print ( (a + b)/ 2 ) " width="640"

Процедура с параметрами

Параметры – данные, изменяющие работу процедуры.

def printBin( n ):

k = 128

while k 0 :

print ( n // k, end = "" )

n = n % k;

k = k // 2

локальная переменная

значение параметра ( аргумент )

printBin ( 99 )

Несколько параметров:

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():

global a

a = 1

qq()

print ( a )

a = 5

def qq():

print ( a )

qq()

5

global a

1

Задачи

« A »: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'.

Пример :

Введите N:

10

----------

« B »: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.

Пример :

Введите натуральное число:

1234

1

2

3

4

Задачи

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

Пример :

Введите натуральное число:

2013

MMXIII

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

§ 60. Функции

Что такое функция?

Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа).

Задача . Написать функцию, которая вычисляет сумму цифр числа.

Алгоритм:

сумма = 0

пока n != 0 :

сумма += n % 10

n = n // 10

Сумма цифр числа

def sumDigits( n ):

s um = 0

while n!= 0 :

sum += n % 10

n = n // 10

return sum

передача результата

return sum

# основная программа

print ( sumDigits( 12345 ) )

Использование функций

x = 2 *sumDigits(n+ 5 )

z = sumDigits(k) + sumDigits(m)

if sumDigits(n) % 2 == 0 :

print ( " Сумма цифр чётная " )

print ( " Она равна " , sumDigits(n) )

!

Функция, возвращающая целое число, может использоваться везде, где и целая величина!

Одна функция вызывает другую:

вызываются min и max

def middle ( a, b, c ):

mi = min ( a, b, c )

ma = max ( a, b, c )

return a + b + c - mi - ma

?

Что вычисляет?

Задачи

« 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 )

кортеж – набор элементов

Задачи

« A »: Напишите функцию, которая переставляет три переданные ей числа в порядке возрастания.

Пример :

Введите три натуральных числа:

10 15 5

5 10 15

« B »: Напишите функцию, которая сокращает дробь вида M/N.

Пример :

Введите числитель и знаменатель дроби:

25 15

После сокращения: 5/3

Задачи

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

Пример :

Введите два натуральных числа:

10 15

НОД(10,15)=5

НОК(10,15)=30

Логические функции

Задача . Найти все простые числа в диапазоне от 2 до 100.

for i in range ( 2 , 10 0 1 ):

if   i   -   простое   :

print ( i )

isPrime ( i )

i   -   простое

функция, возвращающая логическое значение ( True / False )

n) if k*k n: return True else : return False return (k*k n) " width="640"

Функция: простое число или нет?

?

Какой алгоритм?

def isPrime ( n ):

k = 2

while k*k n and n % k != 0 :

k += 1

return (k*k n)

if k*k n:

return True

else :

return False

return (k*k n)

Логические функции: использование

!

Функция, возвращающая логическое значение, может использоваться везде, где и логическая величина!

n = int ( input () )

while isPrime(n):

print ( n, "– простое число" )

n = int ( input () )

Задачи

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

Пример :

Введите натуральное число:

28

Число 28 совершенное.

Пример :

Введите натуральное число:

2 9

Число 2 9 не совершенное.

Задачи

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

Пример :

Введите два натуральных числа:

28 15

Числа 28 и 15 взаимно простые.

Пример :

Введите два натуральных числа:

28 1 6

Числа 28 и 1 6 не взаимно простые.

Задачи

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

Пример :

Введите натуральное число:

733

Число 733 гиперпростое.

Пример :

Введите натуральное число:

19

Число 19 не гиперпростое.

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

§ 61 . Рекурсия

Что такое рекурсия?

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

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

…

Что такое рекурсия?

Натуральные числа :

индуктивное определение

• 1 – натуральное число
• если – натуральное число, то – натуральное число

Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.

Числа Фибоначчи :

при

1, 1, 2, 3, 5, 8, 13, 21, 34, …

110

Фракталы

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

Треугольник Серпинского:

3 перенести (n- 1 , 2 , 3 ) " width="640"

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

3

2

1

• за один раз переносится один диск
• класть только меньший диск на больший
• третий стержень вспомогательный

перенести (n, 1 , 3 )

перенести (n- 1 , 1 , 2 )

1 - 3

перенести (n- 1 , 2 , 3 )

" , m ) Hanoi ( n- 1 , p, m ) рекурсия рекурсия ? Что плохо? ! Рекурсия никогда не остановится! " width="640"

Ханойские башни – процедура

сколько

откуда

куда

номер вспомогательного стержня (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 )

рекурсия

рекурсия

?

Что плохо?

!

Рекурсия никогда не остановится!

" , m ) Hanoi ( n- 1 , p, m ) условие выхода из рекурсии if n == 0 : return # основная программа Hanoi ( 4 , 1 , 3 ) " width="640"

Ханойские башни – процедура

Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции.

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 )

Вывод двоичного кода числа

условие выхода из рекурсии

def printBin ( n ):

if n == 0 : return

printBin ( n // 2 )

print ( n % 2 , end = "" )

напечатать все цифры, кроме последней

вывести последнюю цифру

printBin ( 0 )

printBin ( 1 )

printBin ( 2 )

?

printBin ( 4 )

Как без рекурсии?

printBin ( 9 )

printBin ( 19 )

10011

= 10 : sum += sumDig ( n // 10 ) return sum последняя цифра рекурсивный вызов ? Где условие окончания рекурсии? sumDig ( 1234 ) 4 + sumDig ( 123 ) 4 + 3 + sumDig ( 12 ) 4 + 3 + 2 + sumDig ( 1 ) 4 + 3 + 2 + 1 " width="640"

Вычисление суммы цифр числа

def sumDig ( n ):

sum = n % 10

if n = 10 :

sum += sumDig ( n // 10 )

return sum

последняя цифра

рекурсивный вызов

?

Где условие окончания рекурсии?

sumDig ( 1234 )

4 + sumDig ( 123 )

4 + 3 + sumDig ( 12 )

4 + 3 + 2 + sumDig ( 1 )

4 + 3 + 2 + 1

b: return NOD( a - b, b ) else : return NOD( a, b – a ) условие окончания рекурсии return a + b ; рекурсивные вызовы " width="640"

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

Алгоритм Евклида . Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.

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.

N = 3 - N = 2 - N = 1 N = 1 N = 2 N = 3 def Fact(N): print ( "-" , N ) if N 1 : F = 1 else : F = N * Fact ( N – 1 ) print ( " , N ) return F ? Как сохранить состояние функции перед рекурсивным вызовом? " width="640"

Как работает рекурсия?

Факториал:

- N = 3

- N = 2

- N = 1

N = 1

N = 2

N = 3

def Fact(N):

print ( "-" , N )

if N 1 : F = 1

else :

F = N * Fact ( N – 1 )

print ( " , N )

return F

?

Как сохранить состояние функции перед рекурсивным вызовом?

Стек

Стек – область памяти, в которой хранятся локальные переменные и адреса возврата.

SP

адрес возврата

значение параметра

локальная переменная

SP

Fact(3)

3

A

F

SP

Fact( 2 )

3

A

F

2

A F

F

SP

Fact(1)

3

A

F

2

A F

F

1

A F

F

Рекурсия – «за» и «против»

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

• программа становится более короткой и понятной

• возможно переполнение стека
• замедление работы

!

Любой рекурсивный алгоритм можно заменить нерекурсивным!

def Fact ( n ):

f = 1

for i in range ( 2 ,n+ 1 ):

f *= i

return f

итерационный алгоритм

122

Конец фильма

ПОЛЯКОВ Константин Юрьевич

д.т.н., учитель информатики

ГБОУ СОШ № 163, г. Санкт-Петербург

kpolyakov@mail.ru

ЕРЕМИН Евгений Александрович

к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

eremin@pspu.ac.ru

Источники иллюстраций

• old-moneta.ru
• www.random.org
• www.allruletka.ru
• www.lotterypros.com
• logos.cs.uic.edu
• ru.wikipedia.org  
• иллюстрации художников издательства «Бином»
• авторские материалы