1 of 126

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

1

2 of 126

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

§ 54. Алгоритм и его свойства

2

3 of 126

Что такое алгоритм?

3

Мухаммед ал-Хорезми

(ок. 783–ок. 850 гг.)

Алгоритм — это точное описание порядка действий, которые должен выполнить исполнитель для решения задачи за конечное время.

Исполнитель – это устройство или одушёвленное существо (человек), способное понять и выполнить команды, составляющие алгоритм.

Формальные исполнители: не понимают �(и не могут понять) смысл команд.

Алгоритмизация и программирование, язык Python, 10 класс

4 of 126

Свойства алгоритма

4

Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное время.

Детерминированность (определённость) — при каждом запуске алгоритма с одними и теми же исходными данными получается один и тот же результат.

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

Конечность (результативность) — для корректного набора данных алгоритм должен завершаться через конечное время.

Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату.

Алгоритмизация и программирование, язык Python, 10 класс

5 of 126

Как работает алгоритм?

5

дискретный

объект

1 2 3 4

алгоритм

шаг 1

шаг 2

шаг 3

2 3 4 5

5 4 3 2

дискретный

объект

25 16 9 4

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

Алгоритмизация и программирование, язык Python, 10 класс

6 of 126

Способы записи алгоритмов

6

естественный язык

псевдокод

установить соединение

пока не принята команда «стоп»

принять команду

выполнить команду

завершить сеанс связи

установить соединение

начало цикла

принять команду

выполнить команду

конец цикла при команда = 'stop'

завершить сеанс связи

Алгоритмизация и программирование, язык Python, 10 класс

7 of 126

Способы записи алгоритмов

7

блок-схема

установитьСоединение

начало цикла

cmd:= получитьКоманду

выполнитьКоманду(cmd)

конец при cmd = 'stop'

закрытьСоединение

программа

принять команду

установить соединение

завершить соединение

выполнить команду

«стоп»?

да

нет

Алгоритмизация и программирование, язык Python, 10 класс

8 of 126

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

§ 55. Простейшие программы

8

9 of 126

Простейшая программа

9

# Это пустая программа

Что делает эта программа?

?

комментарии после # �не обрабатываются

# -*- coding: utf-8 -*-

# Это пустая программа

кодировка utf-8 по умолчанию)

Windows: cp1251

"""

Это тоже комментарий

"""

Алгоритмизация и программирование, язык Python, 10 класс

10 of 126

Вывод на экран

10

print ( "2+2=?" )

print ( "Ответ: 4" )

Протокол:

2+2=?

Ответ: 4

автоматический переход на новую строку

print ( '2+2=?' )

print ( 'Ответ: 4' )

Алгоритмизация и программирование, язык Python, 10 класс

11 of 126

Задания

11

«B»: Вывести на экран текст «лесенкой»

Вася

пошел

гулять

«C»: Вывести на экран рисунок из букв

Ж

ЖЖЖ

ЖЖЖЖЖ

ЖЖЖЖЖЖЖ

HH HH

ZZZZZ

Алгоритмизация и программирование, язык Python, 10 класс

12 of 126

Сложение чисел

12

Задача. Ввести с клавиатуры два числа и найти их сумму.

Протокол:

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

25 30

25+30=55

компьютер

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

компьютер считает сам!

Как ввести числа в память?
Где хранить введенные числа?
Как вычислить?
Как вывести результат?

?

Алгоритмизация и программирование, язык Python, 10 класс

13 of 126

Сумма: псевдокод

13

ввести два числа

вычислить их сумму

вывести сумму на экран

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

Компьютер не может исполнить псевдокод!

!

Алгоритмизация и программирование, язык Python, 10 класс

14 of 126

Переменные

14

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

a

Значение

Имя

Алгоритмизация и программирование, язык Python, 10 класс

15 of 126

Имена переменных

15

МОЖНО использовать

латинские буквы (A-Z, a-z)

русские буквы (не рекомендуется!)
цифры

знак подчеркивания _

заглавные и строчные буквы различаются

НЕЛЬЗЯ использовать

скобки
знаки +, =, !, ? и др.

имя не может начинаться с цифры

Какие имена правильные?

AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

Алгоритмизация и программирование, язык Python, 10 класс

16 of 126

Типы переменных

16

a = 4

print ( type(a) )

целое число (integer)

a = 4.5

print ( type(a) )

вещественное число

a = "Вася"

print ( type(a) )

символьная строка

a = True

print ( type(a) )

логическая

Алгоритмизация и программирование, язык Python, 10 класс

17 of 126

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

17

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

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

Алгоритмизация и программирование, язык Python, 10 класс

18 of 126

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

18

a = 5

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

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

!

5

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

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

a

a = 7

7

Алгоритмизация и программирование, язык Python, 10 класс

19 of 126

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

19

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

!

5

a

Алгоритмизация и программирование, язык Python, 10 класс

20 of 126

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

20

a = input()

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

b = input()

с = a + b

print ( c )

Протокол:

21

33

2133

Почему?

?

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

!

a = int( input() )

b = int( input() )

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

Алгоритмизация и программирование, язык Python, 10 класс

21 of 126

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

21

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

Алгоритмизация и программирование, язык Python, 10 класс

22 of 126

Ввод с подсказкой

22

a = input ( "Введите число: " )

подсказка

Введите число:

26

Что не так?

?

a = int( input("Введите число: ") )

Алгоритмизация и программирование, язык Python, 10 класс

23 of 126

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

23

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

Алгоритмизация и программирование, язык Python, 10 класс

24 of 126

Вывод данных

24

print ( a )

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

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

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

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

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

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

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

2 + 3 = 5

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

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

2+3=5

sep = ""

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

Алгоритмизация и программирование, язык Python, 10 класс

25 of 126

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

25

a = int ( input() )

b = int ( input() )

c = a + b

print ( c )

Что плохо?

?

Алгоритмизация и программирование, язык Python, 10 класс

26 of 126

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

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

a = int ( input() )

b = int ( input() )

c = a + b

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

26

Протокол:

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

25 30

25 + 30 = 55

компьютер

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

подсказка

Алгоритмизация и программирование, язык Python, 10 класс

27 of 126

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

27

a = 123

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

5 знаков

123

5

a = 5

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

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

целое

5 знаков

5

5 знаков

25

5 знаков

125

Алгоритмизация и программирование, язык Python, 10 класс

28 of 126

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

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

28

29 of 126

Типы данных

29

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

a = 5

print ( type(a) )

a = 4.5

print ( type(a) )

a = True

print ( type(a) )

a = "Вася"

print ( type(a) )

Алгоритмизация и программирование, язык Python, 10 класс

30 of 126

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

30

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

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

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

1

2

3

4

5

6

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

/ 2 * d

\

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

a = (c + b*5*3

- 1) / 2 * d

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

Алгоритмизация и программирование, язык Python, 10 класс

31 of 126

Деление

31

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

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

Алгоритмизация и программирование, язык Python, 10 класс

32 of 126

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

32

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

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

Алгоритмизация и программирование, язык Python, 10 класс

33 of 126

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

33

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

Алгоритмизация и программирование, язык Python, 10 класс

34 of 126

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

34

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

!

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

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²

Алгоритмизация и программирование, язык Python, 10 класс

35 of 126

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

35

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

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.23e+02

1,234568 ⋅ 10⁷

всего знаков

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

Алгоритмизация и программирование, язык Python, 10 класс

36 of 126

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

36

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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс

37 of 126

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

37

Случайно…

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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс

38 of 126

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

38

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

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

318458191041

564321

209938992481

458191

938992

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

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

в квадрате

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

зерно

Алгоритмизация и программирование, язык Python, 10 класс

39 of 126

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

39

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

X = random.random() # псевдослучайное число

Y = random.random() # это уже другое число!

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

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

X = random.randint(1,6) # псевдосл. число

Y = random.randint(1,6) # уже другое!

import random

Алгоритмизация и программирование, язык Python, 10 класс

40 of 126

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

40

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

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

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

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

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

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

from random import *

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

подключить все!

Алгоритмизация и программирование, язык Python, 10 класс

41 of 126

Задачи

41

«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

Алгоритмизация и программирование, язык Python, 10 класс

42 of 126

Задачи

42

«C»: Получить случайное трехзначное число и вывести через запятую его отдельные цифры.

Пример:

Получено число 123.

Его цифры 1, 2, 3.

Алгоритмизация и программирование, язык Python, 10 класс

43 of 126

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

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

43

44 of 126

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

44

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

M = a

a > b?

M = b

да

нет

вывод M

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

Если a = b?

?

if a > b:

M = a

else:

M = b

отступы

Алгоритмизация и программирование, язык Python, 10 класс

45 of 126

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

45

M = b

b > a?

да

нет

вывод M

M = a

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

M = a

if b > a:

M = b

M = max(a, b)

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

M = a if a > b else b

Алгоритмизация и программирование, язык Python, 10 класс

46 of 126

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

46

if a > b:

с = a

a = b

b = c

Что делает?

?

4

6

?

4

6

4

a

b

3

2

1

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

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

?

c

a, b = b, a

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

Алгоритмизация и программирование, язык Python, 10 класс

47 of 126

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

47

>

<

>=

<=

==

!=

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

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

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

равно

не равно

Алгоритмизация и программирование, язык Python, 10 класс

48 of 126

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

48

if a > b:

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

else:

if a == b:

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

else:

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

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

Зачем нужен?

?

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

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

?

Алгоритмизация и программирование, язык Python, 10 класс

49 of 126

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

49

if a > b:

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

elif a == b:

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

else:

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

elif = else if

!

Алгоритмизация и программирование, язык Python, 10 класс

50 of 126

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

50

cost = 1500

if cost < 1000:

print ( "Скидок нет." )

elif cost < 2000:

print ( "Скидка 2%." )

elif cost < 5000:

print ( "Скидка 5%." )

else:

print ( "Скидка 10%." )

Что выведет?

?

первое сработавшее условие

Скидка 2%.

Алгоритмизация и программирование, язык Python, 10 класс

51 of 126

Задачи

51

«A»: Ввести три целых числа, найти максимальное из них.

Пример:

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

1 5 4

Максимальное число 5

«B»: Ввести пять целых чисел, найти максимальное из них.

Пример:

Введите пять целых чисел:

1 5 4 3 2

Максимальное число 5

Алгоритмизация и программирование, язык Python, 10 класс

52 of 126

Задачи

52

«C»: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них старше.

Пример:

Возраст Антона: 15

Возраст Бориса: 17

Возраст Виктора: 16

Ответ: Борис старше всех.

Пример:

Возраст Антона: 17

Возраст Бориса: 17

Возраст Виктора: 16

Ответ: Антон и Борис старше Виктора.

Алгоритмизация и программирование, язык Python, 10 класс

53 of 126

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

53

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

if :

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

else:

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

and

or

not

Приоритет :

отношения (<, >, <=, >=, ==, !=)
not («НЕ»)
and («И»)
or («ИЛИ»)

v >= 25 and v <= 40

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

«И»

«ИЛИ»

«НЕ»

Алгоритмизация и программирование, язык Python, 10 класс

54 of 126

Задачи

54

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

Пример:

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

5 5 5

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

Пример:

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

5 7 5

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

Пример:

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

5 7 8

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

Алгоритмизация и программирование, язык Python, 10 класс

55 of 126

Задачи

55

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

Пример:

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

5

Весна.

Пример:

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

15

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

Алгоритмизация и программирование, язык Python, 10 класс

56 of 126

Задачи

56

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

Пример:

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

Вам 18 лет.

Пример:

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

Вам 21 год.

Пример:

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

Вам 22 года.

Алгоритмизация и программирование, язык Python, 10 класс

57 of 126

Задачи

57

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

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

Алгоритмизация и программирование, язык Python, 10 класс

58 of 126

Задачи

58

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

Алгоритмизация и программирование, язык Python, 10 класс

59 of 126

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

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

59

60 of 126

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

60

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

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

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

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

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

?

Алгоритмизация и программирование, язык Python, 10 класс

61 of 126

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

61

print("Привет“)

print("Привет")

...

print("Привет")

Что плохо?

?

Алгоритмизация и программирование, язык Python, 10 класс

62 of 126

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

62

начало

конец

да

нет

тело цикла

Алгоритмизация и программирование, язык Python, 10 класс

63 of 126

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

63

счётчик = 0

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

print("Привет“)

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

счётчик = 10

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

print("Привет")

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

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

?

✔

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

Алгоритмизация и программирование, язык Python, 10 класс

64 of 126

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

64

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

счётчик = 0

пока n > 0:

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

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

n	счётчик
1234	0
123	1
12	2
1	3
0	4

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

?

n = n // 10

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

?

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

счётчик += 1

Алгоритмизация и программирование, язык Python, 10 класс

65 of 126

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

65

count = 0

while :

n = n // 10

count += 1

тело цикла

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

n > 0

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

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

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

!

Алгоритмизация и программирование, язык Python, 10 класс

66 of 126

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

66

k = 0

while k < 10:

print ( "привет" )

k += 1

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

k = 0

while k < 10:

print ( "привет" )

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

Алгоритмизация и программирование, язык Python, 10 класс

67 of 126

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

67

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

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

Алгоритмизация и программирование, язык Python, 10 класс

68 of 126

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

68

while True:

if n > 0: break

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

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

n = int ( input() )

тело цикла

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

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс

69 of 126

Задачи

69

«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

Алгоритмизация и программирование, язык Python, 10 класс

70 of 126

Задачи

70

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

Пример:

Введите число N:

10000

Сумма 17709

Алгоритмизация и программирование, язык Python, 10 класс

71 of 126

Задачи-2

71

«A»: Ввести натуральное число и найти сумму его цифр.

Пример:

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

12345

Сумма цифр 15.

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

Пример:

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

12342

Нет.

Пример:

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

12245

Да.

Алгоритмизация и программирование, язык Python, 10 класс

72 of 126

Задачи-2

72

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

Пример:

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

12342

Да.

Пример:

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

12345

Нет.

Алгоритмизация и программирование, язык Python, 10 класс

73 of 126

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

73

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

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

?

while :

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

i = 0

i < 10

i += 1

for :

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

i in range(10)

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

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

Не включая 10!

!

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

Алгоритмизация и программирование, язык Python, 10 класс

74 of 126

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

74

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

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

?

while :

print ( 2**k )

k = 0

k < 10

k += 1

for :

print ( 2**k )

k in range(1,11)

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

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

Не включая 11!

!

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

Алгоритмизация и программирование, язык Python, 10 класс

75 of 126

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

75

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

Алгоритмизация и программирование, язык Python, 10 класс

76 of 126

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

76

a = 1

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

a = 4

a = 1

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

a = 1

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

a = 1

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

a = 3

Алгоритмизация и программирование, язык Python, 10 класс

77 of 126

Задачи

77

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

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

Алгоритмизация и программирование, язык Python, 10 класс

78 of 126

Задачи

78

«С»: Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 25² = 625. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N.

Пример:

Введите N:

1000

1*1=1

5*5=25

6*6=36

25*25=625

76*76=5776

Алгоритмизация и программирование, язык Python, 10 класс

79 of 126

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

79

Задача. Вывести все простые числа в диапазоне�от 2 до 1000.

сделать для n от 2 до 1000

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

вывод n

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

нет делителей [2.. n-1]: проверка в цикле!

Что значит «простое число»?

?

for n in range(2, 1001):

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

print( n )

Алгоритмизация и программирование, язык Python, 10 класс

80 of 126

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

80

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

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

Алгоритмизация и программирование, язык Python, 10 класс

81 of 126

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

81

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

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

!

Алгоритмизация и программирование, язык Python, 10 класс

82 of 126

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

82

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

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

!

Алгоритмизация и программирование, язык Python, 10 класс

83 of 126

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

83

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

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

?

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

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

Алгоритмизация и программирование, язык Python, 10 класс

84 of 126

Задачи

84

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

Пример:

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

10 20

11 13 17 19

«B»: В магазине продается мастика в ящиках по 15 кг, �17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?

Алгоритмизация и программирование, язык Python, 10 класс

85 of 126

Задачи

85

«C»: Ввести натуральное число N и вывести все натуральные числа, не превосходящие N и делящиеся на каждую из своих цифр.

Пример:

Введите N:

15

1 2 3 4 5 6 7 8 9 11 12 15

Алгоритмизация и программирование, язык Python, 10 класс

86 of 126

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

§ 59. Процедуры

86

87 of 126

Зачем нужны процедуры?

87

print ( "Ошибка программы" )

много раз!

def Error():

print( "Ошибка программы" )

n = int ( input() )

if n < 0:

Error()

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

Процедура:

define определить

Алгоритмизация и программирование, язык Python, 10 класс

88 of 126

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

88

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

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

Алгоритмизация и программирование, язык Python, 10 класс

89 of 126

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

89

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

много раз!

Алгоритм:

178

⇒

10110010₂

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

?

7 6 5 4 3 2 1 0

1 0 1 1 0 0 1 0₂

разряды

n:=

n // 128

n % 128

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

?

n1 // 64

Алгоритмизация и программирование, язык Python, 10 класс

90 of 126

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

90

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

Решение:

k = 128

while k > 0:

print ( n // k,

end = "" )

n = n % k

k = k // 2

n	k	вывод
178	128	1
50	64	0
50	32	1
18	16	1
2	8	0
2	4	0
2	2	1
0	1	0
0	0

178

⇒

10110010

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

!

Алгоритмизация и программирование, язык Python, 10 класс

91 of 126

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

91

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 )

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

Алгоритмизация и программирование, язык Python, 10 класс

92 of 126

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

92

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

работаем с

глобальной переменной

Алгоритмизация и программирование, язык Python, 10 класс

93 of 126

Задачи

93

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

Пример:

Введите N:

10

----------

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

Пример:

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

1234

1

2

3

4

Алгоритмизация и программирование, язык Python, 10 класс

94 of 126

Задачи

94

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

Пример:

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

2013

MMXIII

Алгоритмизация и программирование, язык Python, 10 класс

95 of 126

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

§ 60. Функции

95

96 of 126

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

96

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

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

Алгоритм:

сумма = 0

пока n != 0:

сумма += n % 10

n = n // 10

Алгоритмизация и программирование, язык Python, 10 класс

97 of 126

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

97

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

print ( sumDigits(12345) )

def sumDigits( n ):

sum = 0

while n!= 0:

sum += n % 10

n = n // 10

return sum

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

Алгоритмизация и программирование, язык Python, 10 класс

98 of 126

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

98

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

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

?

Алгоритмизация и программирование, язык Python, 10 класс

99 of 126

Задачи

99

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

Пример:

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

7006652 112307574

НОД(7006652,112307574) = 1234.

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

Пример:

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

123

Сумма цифр числа 123 равна 6.

Алгоритмизация и программирование, язык Python, 10 класс

100 of 126

Задачи

100

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

Пример:

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

1234

После переворота: 4321.

Алгоритмизация и программирование, язык Python, 10 класс

101 of 126

Как вернуть несколько значений?

101

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)

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

Алгоритмизация и программирование, язык Python, 10 класс

102 of 126

Задачи

102

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

Пример:

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

10 15 5

5 10 15

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

Пример:

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

25 15

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

Алгоритмизация и программирование, язык Python, 10 класс

103 of 126

Задачи

103

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

Пример:

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

10 15

НОД(10,15)=5

НОК(10,15)=30

Алгоритмизация и программирование, язык Python, 10 класс

104 of 126

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

104

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

for i in range(2,1001):

if i - простое :

print ( i )

i - простое

isPrime(i)

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

Алгоритмизация и программирование, язык Python, 10 класс

105 of 126

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

105

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

?

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

Алгоритмизация и программирование, язык Python, 10 класс

106 of 126

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

106

n = int ( input() )

while isPrime(n):

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

n = int ( input() )

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

!

Алгоритмизация и программирование, язык Python, 10 класс

107 of 126

Задачи

107

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

Пример:

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

28

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

Пример:

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

29

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

Алгоритмизация и программирование, язык Python, 10 класс

108 of 126

Задачи

108

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

Пример:

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

28 15

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

Пример:

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

28 16

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

Алгоритмизация и программирование, язык Python, 10 класс

109 of 126

Задачи

109

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

Пример:

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

733

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

Пример:

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

19

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

Алгоритмизация и программирование, язык Python, 10 класс

110 of 126

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

§ 61. Рекурсия

110

111 of 126

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

111

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

…

Алгоритмизация и программирование, язык Python, 10 класс

112 of 126

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

112

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

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

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

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

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

при

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

Алгоритмизация и программирование, язык Python, 10 класс

113 of 126

Фракталы

113

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

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

Алгоритмизация и программирование, язык Python, 10 класс

114 of 126

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

114

1

2

3

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

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

1 -> 3

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

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

Алгоритмизация и программирование, язык Python, 10 класс

115 of 126

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

115

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

сколько

откуда

куда

Что плохо?

?

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

!

рекурсия

Алгоритмизация и программирование, язык Python, 10 класс

116 of 126

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

116

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

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 )

Алгоритмизация и программирование, язык Python, 10 класс

117 of 126

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

117

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 )

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

?

Алгоритмизация и программирование, язык Python, 10 класс

118 of 126

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

118

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

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

Алгоритмизация и программирование, язык Python, 10 класс

119 of 126

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

119

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

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;

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

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

Алгоритмизация и программирование, язык Python, 10 класс

120 of 126

Задачи

120

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

Пример:

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

7006652 112307574

НОД(7006652,112307574)=1234.

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

Пример:

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

378

378 = 2*3*3*3*7

Алгоритмизация и программирование, язык Python, 10 класс

121 of 126

Задачи

121

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

Пример:

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

4

Количество разложений: 4.

Алгоритмизация и программирование, язык Python, 10 класс

122 of 126

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

122

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

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

?

Факториал:

Алгоритмизация и программирование, язык Python, 10 класс

123 of 126

Стек

123

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

SP

SP

		3	A	F

SP

		3	A	F	2	A_F	F

		3	A	F	2	A_F	F	1	A_F	F

SP

Fact(3)

Fact(2)

Fact(1)

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

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

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

Алгоритмизация и программирование, язык Python, 10 класс

124 of 126

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

124

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

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

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

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

!

def Fact ( n ):

f = 1

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

f *= i

return f

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

Алгоритмизация и программирование, язык Python, 10 класс

125 of 126

Конец фильма

125

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

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

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

kpolyakov@mail.ru

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

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

eremin@pspu.ac.ru

Алгоритмизация и программирование, язык Python, 10 класс

126 of 126

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

126

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

Алгоритмизация и программирование, язык Python, 10 класс