programmingSimilar presentations:
Python (6)
1. Программирование (Python)
1Программирование
(Python)
Введение
2. Что такое программирование?
Программирование (Python)Что такое программирование?
Программирование — это создание программ для
компьютеров. Этим занимаются программисты.
Чем занимаются программисты:
анализ задачи (выделение
исходных данных, связей
между ними, этапов решения
задачи)
системные аналитики
разработка алгоритмов
алгоритмисты
написание и отладка программ
кодировщики
тестирование программ
тестировщики
написание документации
технические писатели
3. Направления в программировании
Программирование (Python)3
Направления в программировании
системный программист
операционные системы,
утилиты, драйверы
прикладной программист
прикладные программы, в
т.ч. для мобильных
устройств
веб-программист
веб-сайты
программист баз данных
системы управления
базами данных
4. Программирование (Python)
4Программирование
(Python)
. Как разрабатывают
программы
5. Этапы разработки программ
Программирование (Python)5
Этапы разработки программ
I. Постановка задачи
Документ: техническое задание.
II. Построение модели
исходные данные
модель
результаты
Формализация: запись модели в виде формул (на
формальном языке).
III. Разработка алгоритма и способа
хранения данных
«Алгоритмы + структуры данных = программы»
(Н. Вирт)
6. Этапы разработки программ
Программирование (Python)6
Этапы разработки программ
IV. Кодирование
Запись алгоритма на языке программирования.
алгоритм
кодирование
программный
код
V. Отладка
Поиск и исправление ошибок в программах:
• синтаксические – нарушение правил языка
программирования
• логические – ошибки в алгоритме
могут приводить к отказам – аварийным ситуациям
во время выполнения (run-time error)
7. Этапы разработки программ
Программирование (Python)Этапы разработки программ
VI. Тестирование
Тщательная проверка программы во всех режимах:
• альфа-тестирование – внутри компании
(тестировщики)
• бета-тестирование – (доверенные) пользователи
VII. Документирование
Технические писатели
VIII. Внедрение и сопровождение
• обучение пользователей
• исправление найденных ошибок
• техподдержка
7
8. Методы проектирования программ
Программирование (Python)8
Методы проектирования программ
«Сверху вниз» (последовательное уточнение)
Задача
Подзадача 1
1.1
1.2
Подзадача 2
2.1
2.2
Подзадача 3
2.3
30-40 строк каждая
3.1
3.2
9. Методы проектирования программ
Программирование (Python)Методы проектирования программ
«Сверху вниз» (последовательное уточнение)
сначала задача решается «в целом»
легко распределить работу
легче отлаживать программу (всегда есть
полный работающий вариант)
в нескольких подзадачах может потребоваться
решение одинаковых подзадач нижнего уровня
быстродействие не известно до последнего
этапа (определяется нижним уровнем)
9
10. Методы проектирования программ
Программирование (Python)10
Методы проектирования программ
«Снизу вверх» (восходящее)
Задача
Подзадача 1
1.1
1.2
Подзадача 2
2.1
2.2
Подзадача 3
2.3
библиотека функций
3.1
3.2
11. Методы проектирования программ
Программирование (Python)Методы проектирования программ
«Снизу вверх» (восходящее)
нет дублирования
сразу видно быстродействие
сложно распределять работу
сложнее отлаживать (увеличение числа связей)
плохо видна задача «в целом», может быть
нестыковка на последнем этапе
!
Почти всегда используют оба подхода!
11
12. Простейшая программа
Программирование (Python)12
Простейшая программа
# Это пустая программа
? Что делает эта программа?
комментарии после #
не обрабатываются
кодировка utf-8
по умолчанию)
# coding: utf-8
# Это пустая программа
"""
Это тоже комментарий
"""
13. Вывод на экран
Программирование (Python)13
Вывод на экран
оператор
вывода
Оператор — это команда
языка программирования.
print( "Привет!" )
print( "Привет", Вася! )
print( "Привет, Вася!" )
вся строка в
кавычках
? Что плохо?
14. Переход на новую строку
Программирование (Python)14
Переход на новую строку
print( "Привет, Вася!" )
print( "Привет, Петя!" )
Результат:
Привет, Вася!
Привет, Петя!
переход на новую
строку автоматически
Нужно в одной строке:
Привет, Вася!Привет, Петя!
Решение:
print( "Привет, Вася!", end="" )
print( "Привет, Петя!" )
после вывода данных
ничего не выводить
15. Системы программирования
Программирование (Python)15
Системы программирования
Системы программирования — это средства для
создания новых программ.
Транслятор — это программа, которая переводит
тексты программ, написанных программистом, в
машинные коды (команды процессора).
• компилятор — переводит всю программу в
машинные коды, строит исполняемый файл (.exe)
program Hello;
begin
write('Привет!')
end.
1010010100
privet.exe
• интерпретатор — сам выполняет программу по
частям (по одному оператору).
! Python – интерпретатор!
16. Системы программирования
Программирование (Python)Системы программирования
Отладчик — это программа для поиска ошибок в других
программах.
• пошаговый режим — выполнение программы по
шагам (по одному оператору)
• просмотр значений переменных во время
выполнения программы
• точки останова – операторы в программе, перед
выполнением которых нужно остановиться.
Среда программирования (IDE):
• редактор текста программ
• транслятор
• отладчик
16
17. Задачи
Программирование (Python)Задачи
«B»: Вывести на экран текст «лесенкой»
Вася
пошел
гулять
«C»: Вывести на экран рисунок из букв
Ж
ЖЖЖ
ЖЖЖЖЖ
ЖЖЖЖЖЖЖ
HH HH
ZZZZZ
17
18. Программирование (Python)
18Программирование
(Python)
§ 18. Линейные программы
19. Пример задачи
Программирование (Python)19
Пример задачи
Задача. Ввести два числа и вычислить их сумму.
# ввести два числа
# вычислить их сумму
# вывести сумму на экран
? Выполнится?
Псевдокод – алгоритм на
русском языке с элементами
языка программирования.
! Компьютер не может исполнить псевдокод!
20. Зачем нужны переменные?
Программирование (Python)20
Зачем нужны переменные?
# ввести два числа
Где запомнить?
# вычислить их сумму
# вывести сумму на экран
Переменная — это величина, которая имеет имя, тип и
значение. Значение переменной может изменяться во
время выполнения программы.
a
b
c
ячейки памяти
21. Имена переменных
Программирование (Python)21
Имена переменных
Идентификатор — это имя программы или переменной.
a
b
c
заглавные и строчные
буквы различаются
МОЖНО использовать
• латинские буквы (A-Z, a-z)
• цифры
!
Имя не может начинаться с цифры!
• знак подчеркивания _
НЕЛЬЗЯ использовать скобки, знаки ", &, |, *, +, =, !, ? и др.
Какие имена правильные?
AXby R&B 4Wheel Вася “PesBarbos”
TU154 [QuQu] _ABBA A+B
22. Работа с переменными
Программирование (Python)22
Работа с переменными
Присваивание (запись значения)
a = 5
a = 5
a = 18
оператор
присваивания
a ←5
? Что будет храниться в a?
Вывод на экран
print(a) ? В чём разница?
с = 14
print(c)
с = 14
print("с")
14
c
23. Работа с переменными
Программирование (Python)23
Работа с переменными
Изменение значения
i = i + 1
a = 4
b = 7
a = a + 1
b = b + 1
a = a + b
b = b + a
a = a + 2
b = b + a
увеличить на 1
a
4
b
i ← i + 1
Python:
a, b = 4, 7
7
5
8
13
21
15
36
a += 1
b += 1
a += b
b += a
a += 2
b += a
24. Ввод с клавиатуры
Программирование (Python)24
Ввод с клавиатуры
Цель – изменить исходные данные, не меняя программу.
5
a = input()
! 1. Программа ждет, пока пользователь введет
значение и нажмет Enter.
2. Введенное значение записывается в
переменную a.
25. Ввод с клавиатуры
Программирование (Python)25
Ввод с клавиатуры
a = input()
b = input()
ввести строку с клавиатуры
и связать с переменной a
Протокол:
21
33
2133
с = a + b
print ( c )
? Почему?
! Результат функции input – строка символов!
преобразовать в
целое число
a = int( input() )
b = int( input() )
26. Ввод с подсказкой
Программирование (Python)26
Ввод с подсказкой
Введите число: 26
a = input( "Введите число: " )
?
подсказка
Что не так?
a = int( input("Введите число: ") )
? Что будет?
преобразовать
в целое число
Введите число: Qu-Qu
ValueError: invalid literal for int() with base 10: 'Qu-Qu'
27. Ввод вещественных чисел
Программирование (Python)Ввод вещественных чисел
print( "Введите число:" )
x = float (input())
или так:
x = float (input("Введите число:"))
27
28. Программа сложения чисел
Программирование (Python)28
Программа сложения чисел
? Что плохо?
a = int ( input() )
b = int ( input() )
c=a+b
print ( c )
ожидание:
реальность:
Введите два числа:
5
7
5+7=12
5
7
12
? Как улучшить диалог?
29. Вывод данных с текстом
Программирование (Python)29
Вывод данных с текстом
значение a
значение b
значение с
5+7=12
текст
print(a, "+", b, "=", c)
ожидание:
реальность:
5+7=12
5 + 7 = 12
это пробелы не заказывали!
print(a, "+", b, "=", c, sep="" )
separator
пустой
30. Программа сложения чисел
Программирование (Python)Программа сложения чисел
print ( "Введите два числа: " )
a = int ( input() )
b = int ( input() )
c=a+b
print ( a, "+", b, "=", c, sep="" )
? Как переделать для 3-х чисел?
30
31. Ввод двух чисел в одной строке
Программирование (Python)31
Ввод двух чисел в одной строке
a, b = map ( int, input().split() )
21 33 input()
ввести строку с клавиатуры
21 33 input().split()
целые
применить
разделить строку на
части по пробелам
21 33 map ( int, input().split() )
эту
операцию
к каждой части
a, b = map ( int, input().split() )
32. Задачи
Программирование (Python)Задачи
«A»: Ввести три числа, найти их сумму.
Пример:
Введите три числа:
4
5
7
4+5+7=16
«B»: Ввести три числа, найти их сумму и
произведение.
Пример:
Введите три числа:
4
5
7
4+5+7=16
4*5*7=140
32
33. Задачи
Программирование (Python)Задачи
«C»: Ввести три числа, найти их сумму, произведение
и среднее арифметическое.
Пример:
Введите три числа:
4
5
7
4+5+7=16
4*5*7=140
(4+5+7)/3=5.333333
33
34. Арифметические выражения
Программирование (Python)Арифметические выражения
c b 1
a
d
2
Линейная запись (в одну строку):
a = (c + b - 1) / 2 * d
Операции: + –
* – умножение
/ – деление
** – возведение в степень (x2 x**2)
34
35. Порядок выполнения операций
Программирование (Python)35
Порядок выполнения операций
3
1
2
4
5
6
a = (c + b**5*3 - 1) / 2 * d
Приоритет (старшинство):
1) скобки
2) возведение в степень **
3) умножение и деление
4) сложение и вычитание
a = (c + b**5*3 - 1) \
/2*d
a = (c + b**5*3
- 1) / 2 * d
c b5 3 1
a
d
2
перенос на
следующую строку
перенос внутри
скобок разрешён
36. Деление
Программирование (Python)Деление
Классическое деление:
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
36
37. Частное и остаток
Программирование (Python)Частное и остаток
// – деление нацело (остаток отбрасывается)
% – остаток от деления
175 сек = 2 мин 55 сек ? Как получить 2 и 55?
t = 175
m = t // 60 # 2
s = t % 60 # 55
37
38. Частное и остаток
Программирование (Python)Частное и остаток
? Что получится?
n = 123
d = n // 10 # 12
k = n % 10 # 3
При делении на 10 нацело отбрасывается последняя
цифра числа.
Остаток от деления на 10 – это последняя цифра числа.
38
39. Операторы // и %
Программирование (Python)39
Операторы // и %
a = 1234
d = a % 10; print( d )
a = a // 10 # 123
d = a % 10; print( d )
a = a // 10 # 12
d = a % 10; print( d )
a = a // 10 # 1
d = a % 10; print( d )
a = a // 10 # 0
4
3
2
1
40. Сокращенная запись операций
Программирование (Python)40
Сокращенная запись операций
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
41. Форматный вывод
Программирование (Python)41
Форматный вывод
a = 1; b = 2; c = 3
print( a, b, c )
1 2 3
форматная строка
123
print("{}{}{}".format(a,b,c))
тут нужно что-то
вывести
print("{}{:3}{:5}".format(a,b,c))
количество знаков
на вывод числа
? Сколько знаков для вывода a?
1
2
3
3
5
42. Форматный вывод
Программирование (Python)Форматный вывод
a = 1; b = 2
print("{}+{}={}".format(a,b,c))
1+2=3
42
43. Задачи
Программирование (Python)Задачи
«A»: Ввести число, обозначающее количество секунд.
Вывести то же самое время в минутах и секундах.
Пример:
Введите число секунд: 175
2 мин. 55 с.
«B»: Ввести число, обозначающее количество секунд.
Вывести то же самое время в часах, минутах и
секундах.
Пример:
Введите число секунд: 8325
2 ч. 18 мин. 45 с
43
44. Задачи
Программирование (Python)Задачи
«С»: Занятия в школе начинаются в 8-30. Урок длится 45
минут, перерывы между уроками – 10 минут. Ввести
номер урока и вывести время его окончания.
Пример:
Введите номер урока: 6
13-50
44
45. Форматный вывод
Программирование (Python)45
Форматный вывод
x=12.345678
print("x={}".format(x))
всего на
число
x=12.345678
в дробной
части
print("x={:10.3f}".format(x))
12.346
3
10
print("x={:8.2f}".format(x))
12.34
46. Форматный вывод
Программирование (Python)Форматный вывод
print("x={:2.2f}".format(x))
12.34
print("x={:.2f}".format(x))
12.34
минимально
возможное
print("x={:0.1f}".format(x))
12.3
46
47. Научный формат чисел
Программирование (Python)Научный формат чисел
x=123456789
print("x={:e}".format(x))
1.234568e+008
1,234568 108
x=0.0000123456789
print("x={:e}".format(x))
1.234568e-005
1,234568 10–5
47
48. Операции с вещественными числами
Программирование (Python)48
Операции с вещественными числами
int – целая часть числа
x=1.6
print(int(x))
1
round – ближайшее целое число
x=-1.2
-1
print(round(x))
49. Типы переменных
Программирование (Python)49
Типы переменных
• int
• float
• bool
• str
# целое
# вещественное
# логические значения
# символьная строка
a=5
print ( type(a) )
a = 4.5
print ( type(a) )
a = True
print ( type(a) )
a = "Вася"
print ( type(a) )
<class 'int'>
<class 'float'>
<class 'bool'>
<class 'str'>
50. Зачем нужен тип переменной?
Программирование (Python)Зачем нужен тип переменной?
Тип определяет:
• область допустимых значений
• допустимые операции
• объём памяти
• формат хранения данных
50
51. Стандартные функции
Программирование (Python)51
Стандартные функции
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 )
x = oct( 29 )
x = hex( 29 )
# '0b11101'
# '0o35'
# '0x1d'
52. Математические функции
Программирование (Python)52
Математические функции
подключить
математический модуль
import math
math.pi
— число «пи»
math.sqrt(x) — квадратный корень
math.sin(x) — синус угла, заданного в радианах
math.cos(x) — косинус угла, заданного в радианах
math.exp(x) — экспонента ех
math.ln(x)
— натуральный логарифм
math.floor(x) — округление «вниз»
math.ceil(x) — округление «вверх»
x = math.floor(1.6) # 1
x = math.ceil(1.6) # 2
x = math.floor(-1.6) #-2
x = math.ceil(-1.6) #-1
53. Документирование программы
Программирование (Python)Документирование программы
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))
? Что делает?
53
54. Документирование программы
Программирование (Python)54
Документирование программы
Руководство пользователя:
• назначение программы
• формат входных данных
• формат выходных данных
• примеры использования программы
Назначение:
программа для решения уравнения
ax bx c 0
2
Формат входных данных:
значения коэффициентов a, b и c вводятся с
клавиатуры через пробел в одной строке
55. Документирование программы
Программирование (Python)Документирование программы
Формат выходных данных:
значения вещественных корней уравнения;
если вещественных корней нет, выводится
слово «нет»
Примеры использования программы:
2
1. Решение уравнения x 5 x 1 0
Введите a, b, c: 1 -5 1
x1=4.791 x2=0.209
2
2. Решение уравнения x x 6 0
Введите a, b, c: 1 1 6
Нет.
55
56. Операции с вещественными числами
Программирование (Python)Операции с вещественными числами
1/3 = 0,33333…
бесконечно много знаков
! Большинство вещественных чисел хранятся в
памяти компьютера с ошибкой!
x = 1/2
y = 1/3
z = 5/6 # 5/6=1/2+1/3
print(x+y-z)
-1.110223e-016
56
57. Задачи
Программирование (Python)Задачи
«A»: Ввести число, обозначающее размер одной
фотографии в Мбайтах. Определить, сколько
фотографий поместится на флэш-карту объёмом
2 Гбайта.
Пример:
Размер фотографии в Мбайтах: 6.3
Поместится фотографий: 325.
«A1»: Получить случайное трехзначное число и вывести
через запятую его отдельные цифры.
Пример:
Получено число 123.
Его цифры 1, 2, 3.
57
58. Задачи
Программирование (Python)Задачи
«B»: Оцифровка звука выполняется в режиме стерео с
частотой дискретизации 44,1 кГц и глубиной
кодирования 24 бита. Ввести время записи в
минутах и определить, сколько Мбайт нужно
выделить для хранения полученного файла
(округлить результат в большую сторону).
Пример:
Введите время записи в минутах: 10
Размер файла 152 Мбайт
58
59. Задачи
Программирование (Python)Задачи
«С»: Разведчики-математики для того, чтобы опознать
своих, используют числовые пароли. Услышав
число-пароль, разведчик должен возвести его в
квадрат и сказать в ответ первую цифры дробной
части полученного числа. Напишите программу,
которая по полученному паролю (вещественному
числу) вычисляет число-ответ.
Пример:
Введите пароль: 1.92
Ответ: 6
потому что 1,922 = 3,6864…, первая цифра
дробной части – 6
59
60. Случайные и псевдослучайные числа
Программирование (Python)Случайные и псевдослучайные числа
Случайные явления
• встретил слона – не встретил слона
• жеребьёвка на соревнованиях
• лотерея
• случайная скорость (направление выстрела ) в игре
• …
Случайные числа — это последовательность чисел, в
которой невозможно предсказать следующее число,
даже зная все предыдущие.
60
61. Случайные и псевдослучайные числа
Программирование (Python)61
Случайные и псевдослучайные числа
! Компьютер неслучаен!
Псевдослучайные числа — похожи на случайные, но
строятся по формуле.
следующее
предыдущее
Xn+1= (a*Xn+b) % c # от 0 до c-1
Xn+1= (Xn+3) % 10
#
от 0 до 9
X = 0 3 6 9 2 5 8
зерно
8 1 4 7 0
зацикливание
62. Датчик случайных чисел
Программирование (Python)62
Датчик случайных чисел
Целые числа на отрезке:
подключить функцию randint
из модуля random
from random import randint
K = randint(1, 6) # отрезок [1,6]
L = randint(1, 6) # это уже другое число!
англ. integer – целый
random – случайный
или так:
import random
K = random.randint(1, 6)
можно использовать
все функции модуля
63. Датчик случайных чисел
Программирование (Python)Датчик случайных чисел
Вещественные числа в полуинтервале:
from random import random
x = random()
# полуинтервал [0,1)
y = 7*random()
# полуинтервал [0,7)
z = 7*random()+5 # полуинтервал [5,12)
Вещественные числа на отрезке [a, b]:
from random import uniform
x = uniform(1.5, 2.8)
# [1,5; 2,8]
y = uniform(5.25, 12.75) # [5,25; 12,75]
63
64. Задачи
Программирование (Python)Задачи
«A»: В игре «Русское лото» из мешка случайным
образом выбираются бочонки, на каждом из которых
написано число от 1 до 90. Напишите программу,
которая выводит наугад первые 5 выигрышных
номеров.
«B»: + Доработайте программу «Русское лото» так,
чтобы все 5 значений гарантированно были бы
разными (используйте разные диапазоны).
64
65. Задачи
Программирование (Python)Задачи
«С»: + Игральный кубик бросается три раза (выпадает
три случайных значения). Из этих чисел
составляется целое число, программа должна найти
его квадрат.
Пример:
Выпало очков:
1 2 3
Число 123
Его квадрат 15129
65
66. Задачи
Программирование (Python)Задачи
«D»: + Получить случайное трёхзначное число и вывести
в столбик его отдельные цифры.
Пример:
Получено число 123
сотни: 1
десятки: 2
единицы: 3
66
67. Программирование (Python)
67Программирование
(Python)
§ 19. Ветвления
68. Выбор наибольшего из двух чисел
Программирование (Python)68
Выбор наибольшего из двух чисел
Задача: изменить порядок действий в зависимости от
выполнения некоторого условия.
полная
форма
да
нет
ветвления
a > b?
M=a
M=b
вывод M
отступы
? Если a = b?
if a > b:
M = a
else:
M = b
69. Вариант 1. Программа
Программирование (Python)69
Вариант 1. Программа
print("Введите два целых числа")
a = int(input())
b = int(input())
if a > b:
полная форма
условного
M = a
оператора
else:
M = b
print("Наибольшее число", M)
Решение в стиле Python:
M = max(a, b)
M = a if a > b else b
70. Выбор наибольшего из двух чисел-2
Программирование (Python)70
Выбор наибольшего из двух чисел-2
начало
ввод a,b
M =a
да
b > a?
M =b
вывод M
конец
нет
неполная
форма
ветвления
71. Вариант 2. Программа
Программирование (Python)Вариант 2. Программа
print("Введите два целых числа")
a = int(input())
b = int(input())
M = a
неполная форма
условного
if b > a:
оператора
M = b
print("Наибольшее число", M)
71
72. Примеры
Программирование (Python)72
Примеры
Поиск минимального:
if a < b:
M = a
if b < a:
M = b
? Что плохо?
? Когда работает неверно?
73. Примеры
Программирование (Python)73
Примеры
? Что делает эта программа?
? В чём отличие?
if a < b:
c = a
a = b
b = c
b
a
4
6
2
?
4
c
6
4
if a < b:
c = a
a = b
b = c
Решение в стиле Python:
a, b = b, a
74. В других языках программирования
Программирование (Python)74
В других языках программирования
Паскаль:
С:
if a < b then begin
c:= a;
a:= b;
b:= c;
end;
if (a < b) {
c = a;
a = b;
b = c;
}
75. Знаки отношений
Программирование (Python)Знаки отношений
> <
больше, меньше
>=
больше или равно
<=
меньше или равно
==
равно
!=
не равно
75
76. Вложенные условные операторы
Программирование (Python)76
Вложенные условные операторы
Задача: в переменных a и b записаны возрасты Андрея и
Бориса. Кто из них старше?
Сколько вариантов?
if a == b:
print("Одного возраста")
else:
if a > b:
print("Андрей старше")
else:
print("Борис старше")
?
? Зачем нужен?
вложенный
условный оператор
77. Каскадное ветвление
Программирование (Python)Каскадное ветвление
if a == b:
print("Одного возраста")
elif a > b:
print("Андрей старше")
else:
print("Борис старше")
! elif = else if
77
78. Каскадное ветвление
Программирование (Python)78
Каскадное ветвление
cost = 1500
if cost < 1000:
print ( "Скидок нет." )
elif cost < 2000:
первое сработавшее
условие
print ( "Скидка 2%." )
elif cost < 5000:
print ( "Скидка 5%." )
else:
print ( "Скидка 10%." )
? Что выведет?
Скидка 2%.
79. Задачи (без функций min и max!)
Программирование (Python)Задачи (без функций min и max!)
«A»: Ввести два целых числа, найти наибольшее и
наименьшее из них.
Пример:
Введите два целых числа:
1 5
Наибольшее число 5
Наименьшее число 1
«B»: Ввести четыре целых числа, найти наибольшее из
них.
Пример:
Введите четыре целых числа:
1 5 4 3
Наибольшее число 5
79
80. Задачи
Программирование (Python)Задачи
«C»: Ввести последовательно возраст Антона, Бориса и
Виктора. Определить, кто из них старше.
Пример:
Возраст Антона: 15
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Борис старше всех.
Пример:
Возраст Антона: 17
Возраст Бориса: 17
Возраст Виктора: 16
Ответ: Антон и Борис старше Виктора.
80
81. Сложные условия
Программирование (Python)Сложные условия
Задача. Фирма набирает сотрудников от 25 до 40 лет
включительно. Ввести возраст человека и определить,
подходит ли он фирме (вывести ответ "подходит" или
"не подходит").
Особенность: надо проверить, выполняются ли два
условия одновременно:
возраст 25
возраст 40
? Можно ли решить известными методами?
81
82. Плохое решение
Программирование (Python)Плохое решение
print("Введите ваш возраст")
x = int(input())
if x >= 25:
вложенный
условный
if x <= 40:
оператор
print("Подходит!")
else:
print("Не подходит.")
else:
print("Не подходит.")
82
83. Хорошее решение (операция «И»)
Программирование (Python)83
Хорошее решение (операция «И»)
Задача: набор сотрудников в возрасте 25-40 лет
(включительно).
сложное условие
if v >= 25 and v <= 40 :
print("подходит")
else:
print("не подходит")
and «И»: одновременное выполнение
всех условий!
84. Примеры
Программирование (Python)Примеры
Задача. Вывести "Да", если число в переменной a –
двузначное.
if 10 <= a and a <= 99:
print("Да")
Задача. Вывести "Да", если число в переменной a –
двузначное и делится на 7.
if 10 <= a and a <= 99 and (a % 7)==0:
print("Да")
84
85. Сложные условия: «ИЛИ»
Программирование (Python)85
Сложные условия: «ИЛИ»
Задача. Самолёт летает по понедельникам и четвергам.
Ввести номер дня недели и определить, летает ли в
этот день самолёт.
Особенность: надо проверить, выполняется ли одно из
двух условий:
день = 1
день = 4
if d == 1 or d == 4 :
print("Летает")
else:
print("Не летает")
сложное
условие
or «ИЛИ»: выполнение хотя бы одного
из двух условий!
86. Ещё пример
Программирование (Python)Ещё пример
Задача. Фирма набирает сотрудников от 25 до 40 лет
включительно. Ввести возраст человека и определить,
подходит ли он фирме (вывести ответ "подходит" или
"не подходит"). Использовать «ИЛИ».
if v < 25 or v > 40 :
print("не подходит")
else:
print("подходит")
86
87. Сложные условия: «НЕ»
Программирование (Python)87
Сложные условия: «НЕ»
if not(a < b):
print("Cтарт!")
? Как без «НЕ»?
not «НЕ»: если выполняется обратное условие
if a >= b:
print("Cтарт!")
88. Простые и сложные условия
Программирование (Python)88
Простые и сложные условия
Простые условия (отношения)
<
<=
>
>=
==
равно
<>
не равно
Сложное условие – это условие, состоящее из
нескольких простых условий (отношений),
связанных с помощью логических операций:
• and – одновременное выполнение условий
x >= 25 and x <= 40
• or – выполнение хотя бы одного из условий
x <= 25 or x >= 40
• not – отрицание, обратное условие
x <=
not (x > 25)
???25
89. Порядок выполнения операций
Программирование (Python)Порядок выполнения операций
• выражения в скобках
• <, <=, >, >=, =, <>
• not
• and
• or
4
1
6
2
5
3
if not a > 2 or c != 5 and b < a:
...
89
90. Сложные условия
Программирование (Python)90
Сложные условия
Истинно или ложно при a = 2; b = 3; c = 4
Да
not (a > b)
a < b and b < c
Да
Нет
a > c or b > c
a < b and b > c
Нет
a > c and b > d
Нет
Да
not (a >= b) or c = d
a >= b or not (c < b)
a > c or b > c or b > a
Да
Да
91. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая получает три числа и
выводит количество одинаковых чисел в этой
цепочке.
Пример:
Введите три числа:
5 5 5
Все числа одинаковые.
Пример:
Введите три числа:
5 7 5
Два числа одинаковые.
Пример:
Введите три числа:
5 7 8
Нет одинаковых чисел.
91
92. Задачи
Программирование (Python)Задачи
«A1»: Напишите программу, которая получает три числа
- рост трёх спортсменов, и выводит сообщение «По
росту.», если они стоят по возрастанию роста, или
сообщение «Не по росту!», если они стоят не по
росту.
Пример:
Введите рост трёх спортсменов:
165 170 172
По росту.
Пример:
Введите рост трёх спортсменов:
175 170 172
Не по росту!
92
93. Задачи
Программирование (Python)Задачи
«B»: Напишите программу, которая получает номер
месяца и выводит соответствующее ему время года
или сообщение об ошибке.
Пример:
Введите номер месяца:
5
Весна.
Пример:
Введите номер месяца:
15
Неверный номер месяца.
93
94. Задачи
Программирование (Python)Задачи
«C»: Напишите программу, которая получает возраст
человека (целое число, не превышающее 120) и
выводит этот возраст со словом «год», «года» или
«лет». Например, «21 год», «22 года», «25 лет».
Пример:
Введите возраст: 18
Вам 18 лет.
Пример:
Введите возраст: 21
Вам 21 год.
Пример:
Введите возраст: 22
Вам 22 года.
94
95. Задачи
Программирование (Python)95
Задачи
«A»: Напишите условие, которое определяет
заштрихованную область.
а)
а
б) б
y
) x2 y 2 4
y
)
в
y sin( x)
)
y 0,5
x
y x
x
x 2
«B»: Напишите условие, которое определяет
заштрихованную область.
а)
б)
y
в)
y x
y
y 1
y
x2 y 2 1
y x 1
x
y x2
0
y 2 x
x
x
x2 y2 1
96. Задачи
Программирование (Python)Задачи
«C»: Напишите условие, которое определяет
заштрихованную область.
96
97. Логические переменные
Программирование (Python)97
Логические переменные
b = True
b = False
type(b)
только два
возможных
значения
<class 'bool'>
логическая (булевская)
переменная
Пример:
freeDay = (d==6 or d==7)
...
if not freeDay:
print("Рабочий день.")
else:
print("Выходной!")
Джордж Буль
98. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая получает с
клавиатуры целое число и записывает в логическую
переменную значение «да» (True), если это число
трёхзначное. После этого на экран выводится ответ
на вопрос: «Верно ли, что было получено
трёхзначное число?».
Пример:
Введите число: 165
Ответ: да.
Пример:
Введите число: 1651
Ответ: нет.
98
99. Задачи
Программирование (Python)Задачи
«B»: Напишите программу, которая получает с
клавиатуры трёхзначное число и записывает в
логическую переменную значение «да» (True), если
это число – палиндром, то есть читается одинаково
слева направо и справа налево. После этого на
экран выводится ответ на вопрос: «Верно ли, что
введённое число – палиндром?».
Пример:
Введите число: 165
Ответ: нет.
Пример:
Введите число: 656
Ответ: да.
99
100. Задачи
Программирование (Python)Задачи
«С»: Напишите программу, которая получает с
клавиатуры трёхзначное число и записывает в
логическую переменную значение «да» (True), если
это все его цифры одинаковы. После этого на экран
выводится ответ на вопрос: «Верно ли, что все
цифры введённого числа одинаковы?»
Пример:
Введите число: 161
Ответ: нет.
Пример:
Введите число: 555
Ответ: да.
100
101. Экспертная система
Программирование (Python)Экспертная система
Экспертная система — это компьютерная программа,
задача которой — заменить человека-эксперта при
принятии решений в сложной ситуации.
База знаний = факты + правила вывода:
• если у животного есть перья, то это птица;
• если животное кормит детенышей молоком, то это —
млекопитающее;
• если животное — млекопитающее и ест мясо, то
это — хищник.
Диалог:
Это животное кормит детей молоком? Нет
Это животное имеет перья? Да
Это птица.
101
102. Дерево решений
Программирование (Python)102
Дерево решений
Кормит детей молоком?
да
нет
Имеет перья?
млекопитающее
Ест мясо?
нет
да
нет
да
?
птица
?
хищник
103. Программирование экспертной системы
Программирование (Python)Программирование экспертной системы
Ответы пользователя: да и нет – символьные строки.
ans = input("Кормит детей молоком? ")
if ans == "да":
... # вариант 1
else:
# вариант
... # вариант
2 1
print("Млекопитающее.")
ans = input("Ест мясо? ")
if ans == "да":
print("Хищник.")
else:
print("Не знаю.")
103
104. Заглавные и строчные буквы
Программирование (Python)104
Заглавные и строчные буквы
if ans == "да":
...
не сработает
на "Да"
? Как исправить?
if ans == "да" or ans == "Да":
...
Ещё лучше:
if ans.lower() == "да":
...
преобразовать все
заглавные в строчные
if ans.upper() == "ДА":
...
105. Программирование (Python)
105Программирование
(Python)
§ 23. Отладка программ
106. Виды ошибок
Программирование (Python)Виды ошибок
Синтаксические ошибки – нарушение правил записи
операторов языка программирования.
Обнаруживаются транслятором.
Логические ошибки – неверно составленный алгоритм.
Отказ (ошибка времени выполнения) – аварийная
ситуация во время выполнения программы.
Отладка – поиск и исправление ошибок в программе.
106
107. Пример отладки программы
Программирование (Python)Пример отладки программы
Программа решения квадратного уравнения
ax bx c 0
2
from math import sqrt
print("Введите a, b, c: ")
a = float(input())
float – преобразовать в
b = float(input())
вещественное число
c = float(input())
D = b*b - 4*a*a
x1 = (-b+sqrt(D))/2*a
x2 = (-b-sqrt(D))/2*a
print("x1=", x1, " x2=", x2, sep="")
107
108. Тестирование
Программирование (Python)108
Тестирование
Тест 1. a = 1, b = 2, c = 1.
Ожидание:
x1=-1.0 x2=-1.0
Реальность:
x1=-1.0 x2=-1.0
Тест 2. a = 1, b = – 5, c = 6.
x1=3.0 x2=2.0
x1=4.791 x2=0.209
Найден вариант, когда программа работает неверно.
Ошибка воспроизводится!
Возможные причины:
• неверный ввод данных
• неверное вычисление дискриминанта
• неверное вычисление корней
• неверный вывод результатов
D b 2 4ac
b D
x1, 2
2a
109. Отладочная печать
Программирование (Python)Отладочная печать
Идея: выводить все промежуточные результаты.
a = float(input())
b = float(input())
c = float(input())
print(a, b, c)
D = b*b - 4*a*a
print("D=", D)
...
109
110. Отладочная печать
Программирование (Python)110
Отладочная печать
Идея: выводить все промежуточные результаты.
Результат:
Введите a, b, c:
1
-5
6
1.0 -5.0 6.0
D= 21.0
D b 2 4ac 25 4 1 6 1
D = b*b - 4*a* с ;
! Одна ошибка найдена!
111. Отладка программы
Программирование (Python)111
Отладка программы
Тест 1. a = 1, b = 2, c = 1.
Ожидание:
x1=-1.0 x2=-1.0
Реальность:
x1=-1.0 x2=-1.0
Тест 2. a = 1, b = – 5, c = 6.
x1=3.0 x2=2.0
x1=3.0 x2=2.0
? Программа работает верно?
Тест 3. a = 8, b = – 6, c = 1.
x1=0.5 x2=0.25
x1=32.0 x2=16.0
x1 = (-b+sqrt(D))/2*a
(2*a)
x2 = (-b-sqrt(D))/2*a
(2*a)
? Что неверно?
112. Задачи
Программирование (Python)Задачи
«A»: Загрузите программу, которая должна вычислять
сумму цифр трёхзначного числа:
N = input(int("N = "))
d0 = N % 10
d1 = N % 100
d2 = N // 100
d0 + d2 = s
print(s)
Выполните отладку программы:
• исправьте синтаксические ошибки
• определите ситуации, когда она работает неверно
• исправьте логические ошибки.
112
113. Задачи
Программирование (Python)Задачи
«B»: Доработайте программу из п. А так, чтобы она
правильно работала с отрицательными
трёхзначными числами: при вводе числа «–123»
программа должна выдавать ответ 6.
113
114. Задачи
Программирование (Python)Задачи
«С»: Загрузите программу, которая должна вычислять
наибольшее из трёх чисел:
a = input("a = ")
b = int("b = ")
c = input("c = ")
if a > b: M = a
else
M = b
if c > b
M = b
else:
M = c
input(M)
Выполните отладку программы:
• исправьте синтаксические ошибки
• определите ситуации, когда она работает неверно
• исправьте логические ошибки.
114
115. Программирование (Python)
115Программирование
(Python)
§ 20. Программирование
циклических алгоритмов
116. Зачем нужен цикл?
Программирование (Python)116
Зачем нужен цикл?
Задача. Вывести 5 раз «Привет!».
print("Привет")
print("Привет")
print("Привет")
print("Привет")
print("Привет")
Цикл «N раз»:
сделай 5 раз
print("Привет")
? А если 5000?
такого оператора нет
в Python!
117. Как работает цикл?
Программирование (Python)117
Как работает цикл?
! Нужно запоминать, сколько раз цикл уже выполнен!
переменная-счётчик
ещё не делали
счётчик = 0
пока счётчик < 5
print("Привет")
счётчик +=
= счётчик
+ 1
счётчик
1
c = 0
while c < 5:
print("Привет")
c += 1
сделали ещё раз
118. Ещё один вариант
Программирование (Python)118
Ещё один вариант
Идея: запоминать, сколько шагов осталось.
счётчик = 5
пока счётчик > ???
0
print("Привет")
счётчик -=
= счётчик
???
1
1
c = 5
while c > 0:
print("Привет")
c -= 1
? Как записать иначе
последнюю строку?
119. Цикл с предусловием
Программирование (Python)119
Цикл с предусловием
• условие проверяется при входе в цикл
• как только условие становится ложным, работа цикла
заканчивается
• если условие ложно в самом начале, цикл не
выполняется ни разу
while условие:
...
тело цикла
? Если условие никогда не станет ложно?
while True:
...
бесконечный цикл
(зацикливание)
120. Сколько раз выполняется цикл?
Программирование (Python)120
Сколько раз выполняется цикл?
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
зацикливание
121. Сумма цифр числа
Программирование (Python)121
Сумма цифр числа
Задача. Вычислить сумму цифр введённого числа.
123 1 + 2 + 3 = 6
Выделить последнюю цифру числа в переменной N:
d = N % 10
123 3
Отбросить последнюю цифру числа в переменной N:
N = N // 10
123 12
Добавить к переменной sum значение переменной d:
sum +=
= sum
d + d
sum = 6 6 + 4 = 10
d=4
122. Сумма цифр числа
Программирование (Python)122
Сумма цифр числа
• выделяем последнюю цифру числа (%)
• увеличиваем сумму на значение цифры (sum+=d)
• отсекаем последнюю цифру числа (//)
N
d
123
sum
0
12
3
3
1
2
5
0
1
6
начальные значения
123. Сумма цифр числа
Программирование (Python)123
Сумма цифр числа
начало
обнулить
сумму
ввод N
sum= 0
N != 0?
да
d = N % 10
sum += d
N = N // 10
выполнять
"пока N != 0"
нет
вывод sum
конец
124. Сумма цифр числа
Программирование (Python)124
Сумма цифр числа
N = int(input("Введите целое число")); N1= N
sum = 0
while N != 0:
d = N % 10
sum += d
N = N // 10
print("Сумма цифр числа", N1,
N, " равна", sum)
? Что плохо?
125. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая получает с
клавиатуры количество повторений и выводит
столько же раз какое-нибудь сообщение.
Пример:
Сколько раз повторить? 3
Привет!
Привет!
Привет!
«B»: Напишите программу, которая получает с
клавиатуры натуральное число и определяет,
сколько раз в его десятичной записи встречается
цифра 1.
Пример:
Введите число? 311
Единиц: 2
125
126. Задачи
Программирование (Python)Задачи
«C»: Напишите программу, которая получает с
клавиатуры натуральное число и находит
наибольшую цифру в его десятичной записи.
Пример:
Введите число: 311
Наибольшая цифра: 3
«D»: Напишите программу, которая получает с
клавиатуры натуральное число и определяет, есть
ли в его десятичной записи одинаковые цифры,
стоящие рядом.
Пример:
Введите число: 553
Введите число: 535
Ответ: да.
Ответ: нет.
126
127. Задачи
Программирование (Python)127
Задачи
«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
128. Задачи
Программирование (Python)Задачи
«C»: Ввести натуральное число N и вычислить сумму
всех чисел Фибоначчи, меньших N. Предусмотрите
защиту от ввода отрицательного числа N.
Пример:
Введите число N:
10000
Сумма 17709
128
129. Задачи-2
Программирование (Python)Задачи-2
«A»: Ввести натуральное число и найти сумму его цифр.
Пример:
Введите натуральное число:
12345
Сумма цифр 15.
«B»: Ввести натуральное число и определить, верно ли, что в
его записи есть две одинаковые цифры, стоящие рядом.
Пример:
Введите натуральное число:
12342
Нет.
Пример:
Введите натуральное число:
12245
Да.
129
130. Задачи-2
Программирование (Python)Задачи-2
«C»: Ввести натуральное число и определить, верно ли,
что в его записи есть две одинаковые цифры (не
обязательно стоящие рядом).
Пример:
Введите натуральное число:
12342
Да.
Пример:
Введите натуральное число:
12345
Нет.
130
131. Алгоритм Евклида
Программирование (Python)131
Алгоритм Евклида
Задача. Найти наибольший общий делитель (НОД) двух
натуральных чисел.
Заменяем большее из двух чисел разностью
большего и меньшего до тех пор, пока они не
станут равны. Это и есть НОД.
НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)
Евклид
(365-300 до. н. э.)
Пример:
НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)
= НОД (7, 7) = 7
много шагов при большой разнице чисел:
НОД (1998, 2) = НОД (1996, 2) = … = 2
132. Алгоритм Евклида
Программирование (Python)132
Алгоритм Евклида
начало
a = b?
да
конец
нет
нет
b=b-a
a > b?
да
a=a-b
133. Алгоритм Евклида
Программирование (Python)133
Алгоритм Евклида
while a != b:
if a > b:
a -=
= ab- b
else:
b -=
= ba- a
как заменить?
? Где будет НОД? Как его вывести?
? Как вывести НОД в формате НОД(14,21) = 7?
? А без дополнительных переменных?
134. Модифицированный алгоритм Евклида
Программирование (Python)Модифицированный алгоритм Евклида
Заменяем большее из двух чисел остатком от деления
большего на меньшее до тех пор, пока меньшее не
станет равно нулю. Тогда большее — это НОД.
НОД(a,b)= НОД(a % b, b)
= НОД(a, b % a)
Пример:
НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7
134
135. Модифицированный алгоритм
Программирование (Python)135
Модифицированный алгоритм
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % a
? Где будет НОД? Как его вывести?
if a != 0:
print(a)
else:
print(b)
print( a+b
??? )
136. В стиле Python
Программирование (Python)136
В стиле Python
while b!=0:
a, b = b, a % b
Почему работает?
print(a)
заменить a на b и b на
(a % b)
?
a
b
a
b
21
14
14
21
14
7
21
14
7
0
14
7
! a > b!
7
0
137. В других языках программирования
Программирование (Python)137
В других языках программирования
Паскаль:
while (a<>0) and
(b<>0) do
if a>b then
a:= a mod b
else
b:= b mod a;
С:
while (a!=0 && b!=0)
{
if (a > b)
a = a % b;
else
b = b % a;
}
138. Задачи
Программирование (Python)138
Задачи
«A»: Ввести с клавиатуры два натуральных числа и найти их
НОД с помощью алгоритма Евклида.
Пример:
Введите два числа:
21 14
НОД(21,14)=7
«B»: Ввести с клавиатуры два натуральных числа и найти их
НОД с помощью модифицированного алгоритма
Евклида. Заполните таблицу:
a
64168
358853
6365133
17905514
549868978
b
82678
691042
11494962
23108855
298294835
НОД(a,b)
139. Обработка потока данных
Программирование (Python)Обработка потока данных
Задача. На вход программы поступает поток данных —
последовательность целых чисел, которая
заканчивается нулём. Требуется найти сумму
элементов этой последовательности.
while x!=0:
# добавить x к сумме
# x = следующее число
? Откуда возьмётся x в первый раз?
139
140. Задачи
Программирование (Python)Задачи
«C»: Ввести с клавиатуры два натуральных числа и сравнить
количество шагов цикла для вычисления их НОД с
помощью обычного и модифицированного алгоритмов
Евклида.
Пример:
Введите два числа:
1998 2
НОД(1998,2)=2
Обычный алгоритм: 998
Модифицированный: 1
140
141. Обработка потока данных
Программирование (Python)Обработка потока данных
Sum = 0
x = int(input()) # первое число
while x!=0:
Sum += x
x = int(input()) # ввести следующее
print("Сумма ", sum)
? Как найти сумму положительных?
141
142. Задачи
Программирование (Python)Задачи
«A»: На вход программы поступает неизвестное
количество чисел целых, ввод заканчивается нулём.
Определить, сколько получено чисел, которые
делятся на 3.
«B»: На вход программы поступает неизвестное
количество чисел целых, ввод заканчивается нулём.
Определить, сколько получено двузначных чисел,
которые заканчиваются на 3.
«C»: На вход программы поступает неизвестное
количество чисел целых, ввод заканчивается нулём.
Найти максимальное из введённых чётных чисел.
142
143. Задачи на циклы
Программирование (Python)Задачи на циклы
«A»: Напишите программу, которая предлагает ввести
пароль и не переходит к выполнению основной
части, пока не введён правильный пароль. Основная
часть – вывод на экран «секретных сведений».
«B»: Напишите программу, которая получает с
клавиатуры натуральное число, которое больше 1, и
определяет, простое оно или нет. Для этого нужно
делить число на все натуральные числа, начиная с
2, пока не получится деление без остатка.
«C»: Напишите программу, которая получает с
клавиатуры два целых числа и вычисляет их
произведение, используя только операции
сложения.
143
144. Задачи
Программирование (Python)Задачи
«D»: Напишите программу, которая получает с
клавиатуры натуральное число и вычисляет целый
квадратный корень из него – наибольшее число,
квадрат которого не больше данного числа.
144
145. Цикл по переменной
Программирование (Python)145
Цикл по переменной
Задача. Вывести на экран степени числа 2 от 20 до 210.
0
k = 1
! Работа с k в трёх местах!
N = 2
Идея: собрать всё вместе.
while k <= 10 :
print(N)
N = N*2
с нуля!
не включая 11!
k = k + 1
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10]
N = 2
for k in range(11)
range(11):
print(N)
N = N*2
сделать 11 раз
146. Цикл по переменной
Программирование (Python)146
Цикл по переменной
for k in range(11):
print(k)
? Что выведет?
for k in [0,1,2,3,4,5,6,7,8,10]:
print(k)
Начать на с 0, а с 1:
for k in [1,2,3,4,5,6,7,8,10]:
print(k)
начальное
значение
for k in range( 1 ,11):
print(k)
0
1
2
…
10
147. Цикл по переменной
Программирование (Python)147
Цикл по переменной
Задача. Найти сумму чисел от 1 до 1000.
S = 0
for i in range(1,1001):
S += i
Задача. Вывести квадраты чисел от 10 до 1 по убыванию.
for k in [10,9,8,7,6,5,4,3,2,1]:
print(k*k)
не включая 0
шаг
for k in range(10,0,–1):
print(k*k)
148. Цикл по переменной
Программирование (Python)148
Цикл по переменной
Задача. Найти сумму чётных чисел от 2 до 1000.
sum = 0
for i in range(1,1001):
if i % 2 == 0:
sum += i
? Что плохо?
шаг
sum = 0
for i in range(1,1001, 2 ):
sum += i
149. В других языках программирования
Программирование (Python)149
В других языках программирования
Паскаль:
С:
sum:= 0;
for i=1 to 1000 do
sum:= sum + i;
int sum, i;
sum = 0;
for (i=1; i<=1000; i++)
sum += i;
i=i+1;
шаг только 1 или
–1 (downto)
sum=sum+i;
150. Сколько раз выполняется цикл?
Программирование (Python)150
Сколько раз выполняется цикл?
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
151. Задачи
Программирование (Python)Задачи
«A»: Найдите все пятизначные числа, которые при
делении на 133 дают в остатке 125, а при делении
на 134 дают в остатке 111.
«B»: Натуральное число называется числом
Армстронга, если сумма цифр числа, возведенных
в N-ную степень (где N – количество цифр в числе)
равна самому числу. Например, 153 = 13 + 53 + 33.
Найдите все трёхзначные Армстронга.
151
152. Задачи
Программирование (Python)Задачи
«С»: Натуральное число называется автоморфным, если
оно равно последним цифрам своего квадрата.
Например, 252 = 625. Напишите программу, которая
получает натуральное число N и выводит на экран
все автоморфные числа, не превосходящие N.
Пример:
Введите N:
1000
1*1=1
5*5=25
6*6=36
25*25=625
76*76=5776
152
153. Задачи
Программирование (Python)Задачи
«A»: Ипполит задумал трёхзначное число, которое при
делении на 15 даёт в остатке 11, а при делении на
11 даёт в остатке 9. Напишите программу, которая
находит все такие числа.
«B»: С клавиатуры вводится натуральное число N.
Программа должна найти факториал этого числа
(обозначается как N!) – произведение всех
натуральных чисел от 1 до N. Например,
5! = 1 • 2 • 3 • 4 • 5 = 120.
«C»: Натуральное число называется числом
Армстронга, если сумма цифр числа, возведенных
в N-ную степень (где N – количество цифр в числе)
равна самому числу. Например, 153 = 13 + 53 + 33.
Найдите все трёхзначные Армстронга.
153
154. Вложенные циклы
Программирование (Python)154
Вложенные циклы
Задача. Вывести все простые числа в диапазоне
от 2 до 1000.
сделать для n от 2 до 1000
если число n простое то
вывод n
нет делителей [2.. n-1]:
проверка в цикле!
? Что значит «простое число»?
for n in range(2, 1001):
if число n простое:
print( n )
155. Вложенные циклы
Программирование (Python)155
Вложенные циклы
for n in range(2, 1001):
count = 0
for k in range(2,n):
if n % k == 0:
count += 1
if count == 0:
print( n )
вложенный цикл
156. Вложенные циклы
Программирование (Python)156
Вложенные циклы
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
157. Вложенные циклы
Программирование (Python)157
Вложенные циклы
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
158. Поиск простых чисел – как улучшить?
Программирование (Python)158
Поиск простых чисел – как улучшить?
n k m, k m k 2 n k n
? Что плохо?
while k <= math.sqrt(n):
…
count = 0
k=2
Как ещё улучшить?
while k*k <= n :
if n % k == 0:
выйти из цикла
count += 1
while k*k <= n:
k += 1
if n % k == 0: break
k += 1
если вышли
if k*k > n:
по условию
print ( n )
?
159. Задачи
Программирование (Python)159
Задачи
«A»: Напишите программу, которая получает натуральные
числа A и B (A<B) и выводит все простые числа в
интервале от A до B.
Пример:
Введите границы диапазона:
10 20
11 13 17 19
«B»: В магазине продается мастика в ящиках по 15 кг,
17 кг, 21 кг. Как купить ровно 185 кг мастики, не
вскрывая ящики? Сколькими способами можно это
сделать?
160. Задачи
Программирование (Python)Задачи
«C»: Ввести натуральное число N и вывести все
натуральные числа, не превосходящие N и
делящиеся на каждую из своих цифр.
Пример:
Введите N:
15
1 2 3 4 5 6 7 8 9 11 12 15
160
161. Программирование на языке Python
161Программирование
на языке Python
Процедуры
162. Два типа подпрограмм
Программирование (Python)162
Два типа подпрограмм
Подпрограммы
Процедуры
выполняют действия
? Процедура или функция?
Функции
+ возвращают некоторый
результат
а) рисует окружность на экране
б) определяет площадь круга
в) вычисляет значение синуса угла
г) изменяет режим работы программы
д) возводит число x в степень y
е) включает двигатель автомобиля
ж) проверяет оставшееся количество бензина в баке
з) измеряет высоту полёта самолёта
163. Простая процедура
Программирование (Python)163
Простая процедура
define – определить
def printLine():
print("----------")
? Что делает?
...
вызов
printLine()
процедуры
...
какие-то
операторы
можно вызывать сколько угодно раз
нет дублирования кода
изменять – в одном месте
164. Зачем нужны процедуры?
Программирование (Python)164
Зачем нужны процедуры?
print ( "Ошибка программы" )
много раз!
Процедура:
define
определить
def Error():
print( "Ошибка программы" )
n = int ( input() )
if n < 0:
вызов
Error()
процедуры
165. Что такое процедура?
Программирование (Python)Что такое процедура?
Процедура – вспомогательный алгоритм, который
выполняет некоторые действия.
• текст (расшифровка) процедуры записывается
до её вызова в основной программе
• в программе может быть много процедур
• чтобы процедура заработала, нужно вызвать её по
имени из основной программы или из другой
процедуры
165
166. Процедура с параметрами
Программирование (Python)166
Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в
8-битном двоичном коде.
много раз!
Алгоритм:
178 101100102
? Как вывести первую цифру?
7
6 5 4
3 2 1
0
n:= 1 0 1 1 0 0 1 02
n // 128
разряды
n % 128
? Как вывести вторую цифру?
n1 // 64
167. Процедура с параметрами
Программирование (Python)167
Процедура с параметрами
Задача. Вывести на экран запись целого числа (0..255) в
8-битном двоичном коде.
Решение:
n
k
вывод
k = 128
178
128
1
while k > 0:
print ( n // k,
end = "" )
n=n%k
k = k // 2
178 10110010
зависит
! Результат
от n!
50
50
18
64
32
16
0
1
1
2
2
2
8
4
2
0
0
1
0
0
1
0
0
168. Процедура с параметрами
Программирование (Python)168
Процедура с параметрами
Параметры – данные, изменяющие
работу процедуры.
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 )
значение параметра
(аргумент)
169. Локальные и глобальные переменные
Программирование (Python)169
Локальные и глобальные переменные
глобальная
переменная
локальная
переменная
a=5
def qq():
a=1
print ( a ) 1
qq()
print ( a ) 5
a=5
5
def qq():
print ( a )
qq()
a=5
def qq():
global a
a=1
qq()
print ( a )
работаем с
глобальной
переменной
1
170. Неправильная процедура
Программирование (Python)170
Неправильная процедура
x = 5; y = 10
def xSum():
print ( x+y )
xSum()
? Что плохо?
def xSum():
print ( x+y )
1) процедура связана с глобальными переменными,
нельзя перенести в другую программу
2) печатает только сумму x и y, нельзя напечатать
сумму других переменных или сумму x*y и 3x
? Как исправить?
передавать
данные через
параметры
171. Правильная процедура
Программирование (Python)171
Правильная процедура
Глобальные:
x
y
5
10
z
w
17
3
def Sum2(a, b):
print ( a+b )
x = 5; y = 10
Sum2( x, y )
z=17; w=3
Sum2( z, w )
Sum2( z+x, y*w )
Локальные:
a
b
17
22
5
10
30
3
1) процедура не зависит от глобальных
переменных
2) легко перенести в другую программу
3) печатает только сумму любых выражений
15
20
52
172. Задачи
Программирование (Python)Задачи
«A»: Напишите процедуру, которая принимает параметр –
натуральное число N – и выводит на экран линию из N
символов '–'.
Пример:
Введите N:
10
---------«B»: Напишите процедуру, которая выводит на экран в
столбик все цифры переданного ей числа, начиная с
первой.
Пример:
Введите натуральное число:
1234
1
2
3
4
172
173. Задачи
Программирование (Python)Задачи
«C»: Напишите процедуру, которая выводит на экран
запись переданного ей числа в римской системе
счисления.
Пример:
Введите натуральное число:
2013
MMXIII
173
174. Линии разной длины
Программирование (Python)174
Линии разной длины
def printLine5():
print("-----")
? Как улучшить?
def printLine10():
print("----------")
def printLine10():
print("-"*10)
параметр
процедуры
def printLine( n ):
print("-"*n)
175. Процедура с параметром
Программирование (Python)175
Процедура с параметром
Параметр – величина, от
которой зависит
работа процедуры.
def printLine( n ):
...
...
printLine(10)
...
printLine(7)
printLine(5)
printLine(3)
? Что делает?
Аргумент – значение
параметра при
конкретном вызове.
176. Несколько параметров
Программирование (Python)176
Несколько параметров
символьная строка
def printLine(c, n):
print(c*n)
? Что изменилось?
? Как вызывать?
printLine( "+", 5 )
printLine( "+-+", 5 )
printLine( 5, "+" )
177. В других языках программирования
Программирование (Python)В других языках программирования
Паскаль:
procedure printLine(c: string; n: integer);
var i: integer;
begin
for i:=1 to n do
write(c);
writeln
end;
177
178. В других языках программирования
Программирование (Python)В других языках программирования
С:
void printLine(int n)
{
int i;
for (i=1; i<=n; i++)
putchar("-");
putchar("\n");
}
178
179. Как не нужно писать процедуры
Программирование (Python)179
Как не нужно писать процедуры
def summa():
print(x + y)
? Что плохо?
x = 10
y = 5
summa()
def summa( x, y ):
print(x + y)
x = 10
y = 5
только x + y
summa( x, y )
не перенести в
другую программу summa( 2*x+y, 7 )
! Процедура принимает данные только
через параметры!
180. Задачи
Программирование (Python)Задачи
«A»: Напишите процедуру, которая принимает параметр –
натуральное число N – и выводит на экран две линии из
N символов "–".
Пример:
Длина цепочки: 7
------------«B»: Напишите процедуру, которая принимает один
параметр – натуральное число N, – и выводит на
экран прямоугольник длиной N и высотой 3
символа.
Пример:
Длина прямоугольника: 7
ooooooo
o
o
ooooooo
180
181. Задачи
Программирование (Python)Задачи
«C»: Напишите процедуру, которая выводит на экран
квадрат со стороной N символов. При запуске
программы N нужно ввести с клавиатуры.
Пример:
Сторона квадрата: 5
ooooo
o
o
o
o
o
o
ooooo
181
182. Задачи
Программирование (Python)Задачи
«D»: Напишите процедуру, которая выводит на экран
треугольник со стороной N символов. При запуске
программы N нужно ввести с клавиатуры.
Пример:
Сторона: 5
o
oo
ooo
oooo
ooooo
182
183. Рекурсия
Программирование (Python)183
Рекурсия
Задача. Вывести на экран двоичный код натурального
числа.
def printBin( n ):
...
Алгоритм перевода через остатки:
while n!=0:
print(n % 2, end="")
n = n // 2
011
в обратном порядке!
? Что получится
при n = 6?
184. Рекурсия
Программирование (Python)184
Рекурсия
Чтобы вывести двоичную запись числа n, нужно сначала
вывести двоичную запись числа (n // 2), а затем — его последнюю двоичную цифру, равную
(n % 2).
двоичная запись числа 6
110
6 % 2
двоичная запись числа 3
! Чтобы решить задачу,
нужно решить ту же
задачу
для меньшего числа!
Это и есть рекурсия!
! Чтобы понять рекурсию, нужно понять рекурсию!
185. Рекурсивная процедура
Программирование (Python)185
Рекурсивная процедура
def printBin( n ):
printBin(n % 2)
print(n % 2, end = "")
вызывает сама себя!
Рекурсивная процедура — это процедура, которая
вызывает сама себя.
printBin(6)
printBin(3)
? Что получится? printBin(6)
printBin(1)
printBin(0)
printBin(0)
бесконечные вызовы
? Как исправить?
186. Рекурсивная процедура
Программирование (Python)186
Рекурсивная процедура
def printBin( n ):
if n = 0: return
printBin(n // 2)
print(n % 2)
получится?
? Что
printBin(6)
printBin(6)
printBin(3)
printBin(1)
printBin(0)
print(1 % 2)
print(3 % 2)
print(6 % 2)
рекурсия
заканчивается!
110
187. Задачи
Программирование (Python)Задачи
«A»: Напишите рекурсивную процедуру, которая
переводит число в восьмеричную систему.
Пример:
Введите число: 66
В восьмеричной: 102
«B»: Напишите рекурсивную процедуру, которая
переводит число в любую систему счисления с
основанием от 2 до 9.
Пример:
Введите число: 75
Основание: 6
В системе с основанием 6: 203
187
188. Задачи
Программирование (Python)Задачи
«С»: Напишите рекурсивную процедуру, которая
переводит число в шестнадцатеричную систему.
Пример:
Введите число: 123
В шестнадцатеричной: 7B
«D»: Напишите рекурсивную процедуру, которая
переводит число в любую систему счисления с
основанием от 2 до 36.
Пример:
Введите число: 350
Основание: 20
В системе с основанием 20: HA
188
189. Программирование (Python)
189Программирование
(Python)
§ 25. Функции
190. Что такое функция?
Программирование (Python)190
Что такое функция?
Функция — это вспомогательный алгоритм, который
возвращает результат (число, строку символов и др.).
Задача. Написать функцию, которая вычисляет среднее
арифметическое двух целых чисел.
цел a, b
исходные данные
целые
def Avg(a, b):
return (a+b)/2
return – вернуть
Avg
вещ r
результат
? Тип результата?
результат
функции
191. Как вызывать функцию?
Программирование (Python)191
Как вызывать функцию?
Запись результата в переменную:
sr = Avg(5, 8)
6.5
x = 2; y = 5
sr = Avg(x, 2*y+8)
Вывод на экран:
x = 2; y = 5
sr = Avg(x, y+3)
print( Avg(12,7) )
print( sr + Avg(x,12) )
? Чему равно?
10
5
9.5
12
192. Как вызывать функцию?
Программирование (Python)192
Как вызывать функцию?
Использование в условных операторах:
a = int(input())
b = int(input())
if Avg(a,b) > 5:
print("Да!")
Когда печатает «Да»?
else:
print("Нет!");
?
193. Как вызывать функцию?
Программирование (Python)193
Как вызывать функцию?
Использование в циклах:
a = int(input())
b = int(input())
ввод двух чисел в
while Avg(a,b) > 0:
одной строчке
print("Нет!")
a,b = map(int, input().split())
print("Угадал!");
? Когда напечатает «Угадал»?
194. В других языках программирования
Программирование (Python)В других языках программирования
Паскаль:
function Avg(a, b: integer): real;
begin
Avg:=(a+b)/2
Avg
end.
специальная переменная для
записи результата функции
С:
float Avg(int a, int b)
{
return (a+b)/2.0;
}
194
195. Максимум из двух (трёх) чисел
Программирование (Python)195
Максимум из двух (трёх) чисел
Задача. Составить функцию, которая определяет
наибольшее из двух целых чисел.
цел a, b
исходные данные
цел r
результат
Max
?
def Max(a, b):
Как с её помощью найти
if a > b then
максимум из трёх?
return a
else:
return b
def Max3(a, b, c):
return Max( Max(a,b), c )
196. Сумма цифр числа
Программирование (Python)Сумма цифр числа
Задача. Составить функцию, которая вычисляет сумму
значений цифр натурального числа.
def sumDigits( N ):
sum = 0
# накапливаем сумму с 0
while N!=0:
d = N % 10
# выделим последнюю цифру
sum += d
# добавим к сумме
N = N // 10 # удалим последнюю цифру
return sum
196
197. Задачи
Программирование (Python)Задачи
«A»: Напишите функцию, которая вычисляет среднее
арифметическое пяти целых чисел.
Пример:
Введите 5 чисел: 1 2 3 4 6
Среднее: 3.2
«B»: Напишите функцию, которая находит количество
цифр в десятичной записи числа.
Пример:
Введите число: 751
Количество цифр: 3
197
198. Задачи
Программирование (Python)Задачи
«С»: Напишите функцию, которая находит количество
единиц в двоичной записи числа.
Пример:
Введите число: 75
Количество единиц: 4
198
199. Логические функции
Программирование (Python)Логические функции
Логическая функция — это функция, возвращающая
логическое значения (да или нет).
• можно ли применять операцию?
• успешно ли выполнена операция?
• обладают ли данные каким-то свойством?
199
200. Логические функции
Программирование (Python)Логические функции
Задача. Составить функцию, которая возвращает
«True», если она получила чётное число и «False»,
если нечётное.
def Even( N ):
if N % 2 == 0:
def Even( N ):
return True
return (N % 2 == 0)
else:
return False
200
201. Рекурсивные функции
Программирование (Python)Рекурсивные функции
Рекурсивная функция — это функция, которая
вызывает сама себя.
Задача. Составить рекурсивную функцию, которая
вычисляет сумму цифр числа.
? Как сформулировать решение рекурсивно?
Сумму цифр числа N нужно выразить через сумму
цифр другого (меньшего) числа.
Сумма цифр числа N равна значению последней цифры
плюс сумма цифр числа, полученного отбрасыванием
последней цифры.
sumDig(12345) = 5 + sumDig(1234)
201
202. Рекурсивная функция
Программирование (Python)202
Рекурсивная функция
Сумма цифр числа N
последняя цифра
Вход: натуральное число N.
Шаг 1: d = N % 10
число без
Шаг 2: M = N // 10
последней цифры
Шаг 3: s = сумма цифр числа M
Шаг 4: sum = s + d
Результат: sum.
? Что забыли?
? Когда остановить?
203. Сумма цифр числа (рекурсия)
Программирование (Python)203
Сумма цифр числа (рекурсия)
def sumDigRec( N ):
if N == 0: return 0
else:
d = N % 10
sum = sumDigRec(N // 10)
return sum + d
? Где рекурсивный вызов?
? Зачем это?
204. Задачи
Программирование (Python)Задачи
«A»: Напишите логическую функцию, которая
возвращает значение «истина», если десятичная
запись числа заканчивается на цифру 0 или 1.
Пример:
Введите число: 1230
Ответ: Да
«B»: Напишите логическую функцию, которая
возвращает значение «истина», если переданное ей
число помещается в 8-битную ячейку памяти.
Пример:
Введите число: 751
Ответ: Нет
204
205. Задачи
Программирование (Python)Задачи
«C»: Напишите логическую функцию, которая
возвращает значение «истина», если переданное ей
число простое (делится только на само себя и на
единицу).
Пример:
Введите число: 17
Число простое!
Пример:
Введите число: 18
Число составное!
205
206. Задачи
Программирование (Python)Задачи
«A»: Напишите функцию, которая находит наибольший
общий делитель двух натуральных чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) = 1234.
«B»: Напишите функцию, которая определяет сумму
цифр переданного ей числа.
Пример:
Введите натуральное число:
123
Сумма цифр числа 123 равна 6.
206
207. Задачи
Программирование (Python)Задачи
«C»: Напишите функцию, которая «переворачивает»
число, то есть возвращает число, в котором цифры
стоят в обратном порядке.
Пример:
Введите натуральное число:
1234
После переворота: 4321.
207
208. Как вернуть несколько значений?
Программирование (Python)208
Как вернуть несколько значений?
def divmod ( x, y ):
d = x // y
d – частное,
m=x%y
m – остаток
return d, m
a, b = divmod ( 7, 3 )
print ( a, b )
# 2 1
q = divmod ( 7, 3 )
print ( q )
# (2, 1)
кортеж – набор
элементов
209. Задачи
Программирование (Python)Задачи
«A»: Напишите функцию, которая переставляет три
переданные ей числа в порядке возрастания.
Пример:
Введите три натуральных числа:
10 15 5
5 10 15
«B»: Напишите функцию, которая сокращает дробь вида
M/N.
Пример:
Введите числитель и знаменатель дроби:
25 15
После сокращения: 5/3
209
210. Задачи
Программирование (Python)Задачи
«C»: Напишите функцию, которая вычисляет
наибольший общий делитель и наименьшее общее
кратное двух натуральных чисел.
Пример:
Введите два натуральных числа:
10 15
НОД(10,15)=5
НОК(10,15)=30
210
211. Логические функции
Программирование (Python)211
Логические функции
Логическая функция – это функция, возвращающая
логическое значение (True/False).
def even(n):
if n % 2 == 0:
return True
else:
return False
def even(n):
return (n % 2 == 0)
k = int( input() )
if even( k ):
print( "Число", k, "чётное." )
else:
print( "Число", k, "нечётное." )
212. Логические функции
Программирование (Python)212
Логические функции
Задача. Найти все простые числа в диапазоне
от 2 до 100.
for i in range(2,1001):
if i
isPrime(i)
- простое :
print ( i )
функция,
возвращающая
логическое значение
(True/False)
213. Функция: простое число или нет?
Программирование (Python)Функция: простое число или нет?
? Какой алгоритм?
def isPrime ( n ):
k=2
while k*k <= n and n % k != 0:
k += 1
if k*k > n:
return (k*k > n)
return True
else:
return False
213
214. Логические функции: использование
Программирование (Python)Логические функции: использование
! Функция, возвращающая логическое значение,
может использоваться везде, где и логическая
величина!
n = int ( input() )
while isPrime(n):
print ( n, "– простое число" )
n = int ( input() )
214
215. Задачи
Программирование (Python)Задачи
«A»: Напишите логическую функцию, которая
определяет, является ли переданное ей число
совершенным, то есть, равно ли оно сумме своих
делителей, меньших его самого.
Пример:
Введите натуральное число:
28
Число 28 совершенное.
Пример:
Введите натуральное число:
29
Число 29 не совершенное.
215
216. Задачи
Программирование (Python)Задачи
«B»: Напишите логическую функцию, которая
определяет, являются ли два переданные ей числа
взаимно простыми, то есть, не имеющими общих
делителей, кроме 1.
Пример:
Введите два натуральных числа:
28 15
Числа 28 и 15 взаимно простые.
Пример:
Введите два натуральных числа:
28 16
Числа 28 и 16 не взаимно простые.
216
217. Задачи
Программирование (Python)Задачи
«С»: Простое число называется гиперпростым, если любое
число, получающееся из него откидыванием нескольких
цифр, тоже является простым. Например, число 733 –
гиперпростое, так как и оно само, и числа 73 и 7 –
простые. Напишите логическую функцию, которая
определяет, верно ли, что переданное ей число –
гиперпростое. Используйте уже готовую функцию
isPrime, которая приведена в учебнике.
Пример:
Введите натуральное число:
733
Число 733 гиперпростое.
Пример:
Введите натуральное число:
19
Число 19 не гиперпростое.
217
218. Программирование на языке Python
218Программирование
на языке Python
§ 61. Рекурсия
219. Что такое рекурсия?
Программирование (Python)Что такое рекурсия?
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
…
219
220. Что такое рекурсия?
Программирование (Python)220
Что такое рекурсия?
Натуральные числа:
• 1 – натуральное число
• если n – натуральное число,
то n 1 – натуральное число
индуктивное
определение
Рекурсия — это способ определения множества
объектов через само это множество на основе
заданных простых базовых случаев.
Числа Фибоначчи:
• F1 F2 1
• Fn Fn 1 Fn 2 при n 2
1, 1, 2, 3, 5, 8, 13, 21, 34, …
221. Фракталы
Программирование (Python)Фракталы
Фракталы – геометрические фигуры, обладающие
самоподобием.
Треугольник Серпинского:
221
222. Ханойские башни
Программирование (Python)222
Ханойские башни
1
2
3
• за один раз переносится один диск
• класть только меньший диск на больший
• третий стержень вспомогательный
перенести (n, 1, 3)
перенести (n-1, 1, 2)
1 -> 3
перенести (n-1, 2, 3)
223. Ханойские башни – процедура
Программирование (Python)223
Ханойские башни – процедура
сколько
откуда
куда
номер
def Hanoi ( n, k, m ): вспомогательного
рекурсия p = 6 - k - m
стержня (1+2+3=6!)
Hanoi ( n-1, k, p )
print ( k, "->", m )
Hanoi ( n-1, p, m )
рекурсия
? Что плохо?
! Рекурсия никогда не остановится!
224. Ханойские башни – процедура
Программирование (Python)224
Ханойские башни – процедура
Рекурсивная процедура (функция) — это процедура
(функция), которая вызывает сама себя напрямую или
через другие процедуры и функции.
def Hanoi ( n, k, m ):
if n == 0: return
p=6-k-m
Hanoi ( n-1, k, p )
print ( k, "->", m )
Hanoi ( n-1, p, m )
# основная программа
Hanoi( 4, 1, 3 )
условие выхода из
рекурсии
225. Вычисление суммы цифр числа
Программирование (Python)225
Вычисление суммы цифр числа
Задача. Написать рекурсивную функцию, которая
вычисляет сумму цифр числа.
s = sumDigits( 1234 )
1
2
3
4
n
sumDigits( 123 ) + 4
n // 10
n % 10
sumDigits( n )= sumDigits( n // 10 )+(n % 10)
sumDigits( n )= n для n < 10
? Это всё?
226. Вычисление суммы цифр числа
Программирование (Python)226
Вычисление суммы цифр числа
последняя
цифра
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
227. Вычисление суммы цифр числа
Программирование (Python)227
Вычисление суммы цифр числа
sumDigits ( 123 )
d=3
sum = 3 + sumDigits ( 12 )
sumDigits ( 12 )
d=2
sum = 2 + sumDigits ( 1 )
sumDigits ( 1 )
return 1
return 6
return 3
228. Вывод двоичного кода числа
Программирование (Python)228
Вывод двоичного кода числа
Задача. Написать рекурсивную процедуру, которая
выводит двоичную запись числа. условие выхода из
рекурсии
def printBin ( n ):
if n == 0: return
printBin ( n // 2 )
print ( n % 2, end = "" )
напечатать все
цифры, кроме
последней
вывести
последнюю цифру
printBin(
01))
printBin(
printBin(
24))
printBin(
printBin(
))
printBin(919
10011
? Как без рекурсии?
229. Алгоритм Евклида
Программирование (Python)229
Алгоритм Евклида
Алгоритм Евклида. Чтобы найти НОД двух натуральных
чисел, нужно вычитать из большего числа меньшее до
тех пор, пока меньшее не станет равно нулю. Тогда
второе число и есть НОД исходных чисел.
def NOD ( a, b ):
if a == 0 or b == 0:
условие окончания
рекурсии
return a + b;
if a > b:
return NOD( a - b, b )
else:
return NOD( a, b – a )
рекурсивные вызовы
230. Задачи
Программирование (Python)Задачи
«A»: Напишите рекурсивную функцию, которая
вычисляет НОД двух натуральных чисел, используя
модифицированный алгоритм Евклида.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574)=1234.
«B»: Напишите рекурсивную функцию, которая
раскладывает число на простые сомножители.
Пример:
Введите натуральное число:
378
378 = 2*3*3*3*7
230
231. Задачи
Программирование (Python)Задачи
«C»: Дано натуральное число N. Требуется получить и
вывести на экран количество всех возможных
различных способов представления этого числа в
виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1
– это один и тот же способ разложения числа 3).
Решите задачу с помощью рекурсивной процедуры.
Пример:
Введите натуральное число:
4
Количество разложений: 4.
231
232. Как работает рекурсия?
Программирование (Python)232
Как работает рекурсия?
Факториал:
1, N 1
N !
N ( N 1)!, N 1
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
? Как сохранить состояние функции перед
рекурсивным вызовом?
233. Стек
Программирование (Python)233
Стек
Стек – область памяти, в которой хранятся локальные
переменные и адреса возврата.
SP
значение
параметра
адрес
возврата
SP
Fact(3)
3
A
локальная
переменная
F
SP
Fact(2)
3
A
F
2
AF
F
SP
Fact(1)
3
A
F
2
AF
F
1
AF
F
234. Рекурсия – «за» и «против»
Программирование (Python)Рекурсия – «за» и «против»
• с каждым новым вызовом расходуется память в стеке
(возможно переполнение стека)
• затраты на выполнение служебных операций при
рекурсивном вызове
программа становится более короткой и понятной
возможно переполнение стека
замедление работы
! Любой рекурсивный алгоритм можно заменить
нерекурсивным!
def Fact ( n ):
f=1
for i in range(2,n+1):
итерационный
f *= i
алгоритм
return f
234
235. Анализ рекурсивных функций
Программирование (Python)235
Анализ рекурсивных функций
Задача. Что выведет эта программа?
def f( x ):
1, x 3
if x < 3:
f ( x)
return 1
f ( x 1) 2,
else:
return f( x-1 ) + 2
x 3
print( f( 5 ) )
Метод подстановки:
f(5) = f(4) + 2 = 5 + 2 = 7
f(4) = f(3) + 2 = 3 + 2 = 5
f(3) = f(2) + 2 = 1 + 2 = 3
f(2) = 1
f (5)
f (4)
f (3)
линейная
структура
f (2)
236. Анализ рекурсивных функций
Программирование (Python)236
Анализ рекурсивных функций
Задача. Что выведет эта программа?
def f( x ):
1
,
x
3
if x < 3: f ( x)
return 1
f ( x 1) 2 f ( x 2),
else:
return f(x-1) + 2* f(x-2)
print( f( 5 ) )
дерево
f (5) 11
f (3) 3
f (4) 5
3 f (3)
1 f (2)
f (2)
1
f (1) 1
f (2)
1
f (1)
1
x 3
237. Анализ рекурсивных функций
Программирование (Python)237
Анализ рекурсивных функций
Чему равно f (5)?
1, x 3
f ( x)
f ( x 1) 2 f ( x 2), x 3
Табличный метод :
x
f (x)
1
1
2
1
3
3
*2
начальные
значения
4
5
*2
5
11
*2
f(3) = f(2) + 2*f(1) = 3
f(4) = f(3) + 2*f(2) = 5
f(5) = f(4) + 2*f(3) = 11
238. Анализ рекурсивных функций
Программирование (Python)238
Анализ рекурсивных функций
Задача. Сколько звёздочек выведет эта программа?
def f( x ):
if x > 0: g(x-1)
def g( x ):
print( "*" )
if x > 1: f(x-3)
f( 11 )
f (11)
g(10)
*
Ответ: 3
f (7)
g(6)
*
f (3)
g(2)
*
f (-1)
239. Анализ рекурсивных функций
Программирование (Python)239
Анализ рекурсивных функций
Задача. Сколько звёздочек выведет эта программа?
def f( x ):
1, x 0
if x > 0:
f ( x)
g( x-1 )
g ( x 1) f ( x 2) 1, x 0
f( x-2 )
print( "*" )
def g( x ):
print( "*" )
if x > 1: f(x-3)
f( 9 )
1, x 1
g ( x)
1 f ( x 3), x 1
240. Анализ рекурсивных функций
Программирование (Python)240
Анализ рекурсивных функций
1, x 0
f ( x)
g ( x 1) f ( x 2) 1, x 0
1, x 1
g ( x)
1 f ( x 3), x 1
x
f (x)
g(x)
–1
1
1
0
1
1
1
3
1
2
3
2
3
6
2
4
6
4
5 6 7 8 9
11 11 19 19 32
4 7 7 12 12
f (1) = g(0) + f (–1) + 1 = 3
f (2) = g(1) + f (0) + 1 = 3
g (2) = 1 + f (–1) = 2
Ответ: 32
241. Программирование (Python)
241Программирование
(Python)
§ 21. Списки
242. Что такое массив?
Программирование (Python)Что такое массив?
? Как ввести 10000 переменных?
Массив – это группа переменных одного типа,
расположенных в памяти рядом (в соседних ячейках) и
имеющих общее имя.
Надо:
• выделять память
• записывать данные в нужную ячейку
• читать данные из ячейки
242
243. Обращение к элементу массива
Программирование (Python)243
Обращение к элементу массива
НОМЕР
A
элемента массива
(ИНДЕКС)
массив
0
1
5
10
A[0]
A[1]
22
15
15
3
4
20
25
ЗНАЧЕНИЕ
A[2]
A[3]
A[4]
элемента массива
Индекс элемента — это значение, которое указывает на
конкретный элемент массива.
! Нумерация с нуля!
244. Обращение к элементу массива
Программирование (Python)244
Обращение к элементу массива
ИНДЕКС элемента массива: 2
A[2]
ЗНАЧЕНИЕ элемента массива
0
1
2
3
4
23
12
7
43
51
i = 1
A[2] = A[i] + 2*A[i-1] + A[2*i+1]
print( A[2]+A[4] )
? Что получится?
A[2] = A[1] + 2*A[0] + A[3]
print( A[2]+A[4] )
101
152
245. Создание массива
Программирование (Python)245
Создание массива
A = [11, 22, 35, 41, 53]
11
22
35
41
53
A = [11, 22] + [35, 41] + [53]
A = [11]*5
11
11
11
11
11
246. Что неверно?
Программирование (Python)246
Что неверно?
A = [1, 2, 3, 4, 5]
x = 1
? Что плохо?
print( A[x-3] )
A[x+4] = A[x-1] + A[2*x]
print( A[-2] )
A[5] = A[0] + A[2]
Выход за границы массива — это обращение к
элементу с индексом, который не существует в
массиве.
247. Перебор элементов массива
Программирование (Python)247
Перебор элементов массива
N = 10
A = [0]*N
# память уже выделена
Перебор элементов: просматриваем все элементы
массива и, если нужно, выполняем с каждым из них
некоторую операцию.
for i in range(N):
# здесь работаем с A[i]
248. Заполнение массива
Программирование (Python)248
Заполнение массива
[0, 2, 3, …, N-1]
for i in range(N):
A[i] = i
? Что произойдёт?
В развёрнутом виде
A[0] = 0
A[1] = 1
A[2] = 2
...
A[N-1] = N-1
0
1
2
...
В стиле Python:
A = [ i for i in range(N) ]
N-1
249. Заполнение массива в обратном порядке
Программирование (Python)249
Заполнение массива в обратном порядке
N
…
3
2
A[0] = N
A[1] = N-1
A[2] = N-2
...
A[N-1] = 1
1
X=N
for i in range(N):
A[i] = X
X=X-1
? Как меняется X?
X = N, N-1, …, 2, 1
начальное
значение
уменьшение
на 1
250. Заполнение массива в обратном порядке
Программирование (Python)250
Заполнение массива в обратном порядке
N
…
3
2
A[i] = X
1
? Как связаны i и X?
+1
i
0
1
2
...
N-1
X
N
N-1
N-2
...
1
–1
for i in range(N):
A[i] = N – i
В стиле Python:
A = [ N-i
for i in range(N) ]
! Сумма i и X не меняется!
i + X = N
X = N - i
251. Вывод массива на экран
Программирование (Python)251
Вывод массива на экран
Весь массив сразу:
print( A )
[1,2,3,4,5]
По одному элементу:
for i in range(N):
print( A[i] )
или так:
for x in A:
print( x )
? Как вывести
в строчку?
в столбик
для всех элементов в
массиве A
for x in A:
print( x, end=" " )
пробел между
элементами
252. Вывод массива на экран (Python)
Программирование (Python)252
Вывод массива на экран (Python)
[1,2,3,4,5]
print ( *A )
print (1, 2, 3, 4, 5)
разбить список
на элементы
1 2 3 4 5
253. Ввод с клавиатуры
Программирование (Python)253
Ввод с клавиатуры
for i in range(N):
A[i] = int(input())
? Что плохо?
или так:
A = [int(input())
for i in range(N)]
С подсказкой для ввода:
for i in range(N):
s = "A[" + str(i) + "]="
A[i] = int(input(s))
A[0] = 5
A[1] = 12
A[2] = 34
A[3] = 56
A[4] = 13
254. Ввод с клавиатуры (Python)
Программирование (Python)Ввод с клавиатуры (Python)
Ввод всех чисел в одной строке:
data = input()
# "1 2 3 4 5"
s = data.split() #["1","2","3","4","5"]
A = [ int(x) for x in s ]
# [1,2,3,4,5]
или так:
A = [int(x) for x in input().split()]
254
255. Заполнение случайными числами
Программирование (Python)255
Заполнение случайными числами
из библиотеки
(модуля) random
взять функцию randint
from random import randint
N = 10
# размер массива
A = [0]*N # выделить память
for i in range(N):
A[i] = randint(20,100)
В краткой форме:
from random import randint
N = 10
A = [ randint(20,100)
for i in range(N) ]
256. В других языках программирования
Программирование (Python)256
В других языках программирования
Паскаль:
объявление массива
const N = 10;
var A: array[0..N-1] of integer;
...
for i:=0 to N-1 do
A[i] = i;
for i:=0 to N-1 do
write(A[i], ' ');
257. В других языках программирования
Программирование (Python)257
В других языках программирования
С++:
int A[N], i;
for (i = 0; i < N; i++)
A[i] = i;
for (i = 0; i < N; i++)
cout << A[i] << " ";
! Нумерация элементов
всегда с нуля!
258. Задачи
Программирование (Python)Задачи
«A»: Заполните массив случайными числами в интервале
[0,100] и найдите среднее арифметическое его значений.
Пример:
Массив:
1 2 3 4 5
Среднее арифметическое 3.000
«B»: Заполните массив случайными числами в интервале
[0,100] и подсчитайте отдельно среднее значение всех
элементов, которые <50, и среднее значение всех
элементов, которые ≥50.
Пример:
Массив:
3 2 52 4 60
Ср. арифм. элементов [0,50): 3.000
Ср. арифм. элементов [50,100]: 56.000
258
259. Задачи
Программирование (Python)Задачи
«C»: Заполните массив из N элементов случайными числами
в интервале [1,N] так, чтобы в массив обязательно вошли
все числа от 1 до N (постройте случайную перестановку).
Пример:
Массив:
3 2 1 4 5
259
260. Задачи
Программирование (Python)Задачи
«A»: а) Заполните все элементы массива значением X ,
введённым с клавиатуры.
б) Заполните массив первыми N натуральными
числами, начиная с X (значение X введите с
клавиатуры).
«B»: а) Заполните массив натуральными числами в
обратном порядке, начиная со значения X,
введённого с клавиатуры. Последний элемент
должен быть равен X, предпоследний равен X–1 и
т.д.
б) Заполните массив степенями числа 2 (от 21 до 2N),
так чтобы элемент с индексом i был равен 2i.
260
261. Задачи
Программирование (Python)Задачи
«C»: а) Заполните массив степенями числа 2, начиная с
конца, так чтобы последний элемент массива был
равен 1, а каждый предыдущий был в 2 раза больше
следующего.
б) С клавиатуры вводится целое число X. Заполните
массив, состоящий из нечётного числа элементов,
целыми числами, так чтобы средний элемент
массива был равен X, слева от него элементы
стояли по возрастанию, а справа – по убыванию.
Соседние элементы отличаются на единицу.
Например, при X = 3 массив из 5 элементов
заполняется так: 1 2 3 2 1.
261
262. Задачи-2
Программирование (Python)262
Задачи-2
«A»: Напишите программу, которая заполняет массив из
N = 8 элементов случайными числами в диапазоне
[0,10], выводит его на экран, а затем выводит на
экран квадраты всех элементов массива.
Пример:
Массив: 5 6 2 3 1 4 8 7
Квадраты: 25 36 4 9 1 16 64 49
«B»: Напишите программу, которая заполняет массив из N
= 10 случайными числами в диапазоне [100,300] и
выводит его на экран. После этого на экран выводятся
средние цифры (число десятков) всех чисел,
записанных в массив.
Пример:
Массив: 142 324 135 257 167 295 126 223 138 270
Число десятков: 4 2 3 5 6 9 2 2 3 7
263. Задачи-2
Программирование (Python)263
Задачи-2
«C»: Напишите программу, которая заполняет массив из
N = 10 случайными числами в диапазоне [100,500] и
выводит его на экран. После этого на экран выводятся
суммы цифр всех чисел, записанных в массив.
Пример:
Массив: 162 425 340 128 278 195 326 414 312 177
Суммы цифр: 9 11 7 11 17 15 11 9 6 15
264. Программирование (Python)
264Программирование
(Python)
§ 21. Алгоритмы обработки
массивов
265. Сумма элементов массива
Программирование (Python)265
Сумма элементов массива
Задача. Найти сумму элементов массива из N
элементов.
? Какие переменные
нужны?
5
2
8
3
i
Sum = 0
for i in range(N):
Sum =
+ A[i]
+=Sum
A[i]
print( Sum )
Sum
0
0
1
2
5
7
15
В стиле Python:
3
4
18
19
print( sum(A) )
1
266. Сумма элементов массива (Python)
Программирование (Python)266
Сумма элементов массива (Python)
Задача. Найти сумму элементов массива A.
Sum = 0
for x in A:
Sum += x
print( Sum )
или так:
print( sum(A) )
встроенная
функция
для всех
элементов из A
! Не нужно знать размер!
267. Сумма не всех элементов массива
Программирование (Python)Сумма не всех элементов массива
Задача. Найти сумму чётных элементов массива.
? Что делаем с нечётными?
Sum = 0
for i in range(N):
sumA[i]
+= A[i]
if
% 2 == 0:
print(
)
Sumsum
+= A[i]
print( Sum )
267
268. Сумма не всех элементов массива
Программирование (Python)268
Сумма не всех элементов массива
Задача. Найти сумму чётных элементов массива.
Sum = 0
for x in A:
if
% 2
sumx+=
x == 0:
Sumsum
+= x
print(
)
print( Sum )
A
4
x
1
8
6
3
4
Sum
18
10
4
0
3
6
8
отбираем
в новый
1
массив все нужные
значения
В стиле Python:
B = [x for x in A
if x % 2 == 0]
print ( sum(B) )
269. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая заполняет массив из
10 элементов случайными числами на отрезке [–5; 5]
и находит сумму чётных элементов.
«B»: Напишите программу, которая заполняет массив из
10 элементов случайными числами на отрезке [–2; 2]
и находит произведение ненулевых элементов.
«C»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке
[100; 1000] и находит отдельно сумму элементов в
первой и во второй половинах массива.
269
270. Подсчёт элементов по условию
Программирование (Python)270
Подсчёт элементов по условию
Задача. Найти количество чётных элементов массива.
? Какие переменные нужны?
count = 0
for i in range(N):
if A[i] % 2 == 0:
count += 1
print( count )
переменнаясчётчик
? Что тут делаем?
271. Подсчёт элементов по условию (Python)
Программирование (Python)271
Подсчёт элементов по условию (Python)
Задача. Найти количество чётных элементов массива.
count = 0
for x in A:
if x % 2 == 0:
count += 1
print( count )
В стиле Python:
B = [x for x in A
if x % 2 == 0]
print ( len(B) )
размер массива
272. Среднее арифметическое
Программирование (Python)272
Среднее арифметическое
Задача. Найти среднее арифметическое элементов
массива, которые больше 180 (рост в см).
Sum = 0
for x in A:
if x > 180:
Sum += x
print( Sum/N )
? Что плохо?
273. Среднее арифметическое
Программирование (Python)Среднее арифметическое
Задача. Найти среднее арифметическое элементов
массива, которые больше 180 (рост в см).
? Какие переменные нужны?
Sum = 0
count = 0
for x in A:
if x > 180:
count += 1
Что тут делаем?
?
Sum += x
print( Sum/count )
273
274. Среднее арифметическое (Python)
Программирование (Python)274
Среднее арифметическое (Python)
Задача. Найти среднее арифметическое элементов
массива, которые больше 180 (рост в см).
B = [ x for x in A
if x > 180]
print ( sum(B)/len(B) )
отбираем нужные
275. Задачи
Программирование (Python)275
Задачи
«A»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [0;
200] и считает число элементов, которые делятся на
10.
«B»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [0; 200]
и считает число двузначных чисел в массиве.
«C»: Напишите программу, которая заполняет массив из
20 элементов случайными числами на отрезке [10;
100] и считает число пар соседних элементов, сумма
которых делится на 3.
276. Обработка потока данных
Программирование (Python)276
Обработка потока данных
Задача. С клавиатуры вводятся числа, ввод завершается
числом 0. Определить, сколько было введено
положительных чисел.
1) нужен счётчик
2) счётчик увеличивается еслиКогда
числоувеличивать
>0
счётчик?
3) нужен цикл
4) это цикл с условием (число шагов неизвестно)
Какой цикл?
?
?
счётчик = 0
пока не введён 0:
если введено число > 0 то
счётчик:= счётчик + 1
277. Обработка потока данных
Программирование (Python)277
Обработка потока данных
count = 0
x = int(input())
while x != 0:
if x > 0:
count += 1
x = int(input())
print( count )
откуда взять x?
? Что плохо?
278. Найди ошибку!
Программирование (Python)Найди ошибку!
count = 0
x = int(input())
while x != 0:
if x > 0:
count += 1
print(
count )
x = int(input())
278
279. Найди ошибку!
Программирование (Python)Найди ошибку!
xcount
= int(input())
count
== 00
while x == 0:
if x >!=
0:
count += 1
x = int(input())
print( count )
279
280. Обработка потока данных
Программирование (Python)Обработка потока данных
Задача. С клавиатуры вводятся числа, ввод завершается
числом 0. Найти сумму введённых чисел,
оканчивающихся на цифру "5".
1) нужна переменная для суммы
2) число добавляется к сумме, если оно
заканчивается на "5"
3) нужен цикл с условием
сумма = 0
? Как это записать?
пока не введён 0:
если число оканчивается на "5" то
сумма:= сумма + число
if x % 10 == 5:
280
281. Обработка потока данных
Программирование (Python)281
Обработка потока данных
Задача. С клавиатуры вводятся числа, ввод завершается
числом 0. Найти сумму введённых чисел,
оканчивающихся на цифру "5".
sum = 0
x = int(input())
while x != 0:
if x % 10 == 5:
sum += x
x = int(input())
print( sum )
? Чего не хватает?
282. Найди ошибку!
Программирование (Python)Найди ошибку!
sum = 0
x
= int(input())
while
x != 0:
if x % 10 == 5:
sum += x
x = int(input())
print( sum )
282
283. Задачи
Программирование (Python)Задачи
«A»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Определить, сколько получено чисел, которые
делятся на 3.
«B»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Определить, сколько получено двузначных чисел,
которые заканчиваются на 3.
283
284. Задачи
Программирование (Python)Задачи
«C»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Найти среднее арифметическое всех двузначных
чисел, которые делятся на 7.
«D»: На вход программы поступает неизвестное
количество целых чисел, ввод заканчивается нулём.
Найти максимальное из введённых чётных чисел.
284
285. Поиск в массиве
Программирование (Python)285
Поиск в массиве
Найти элемент, равный X:
i=0
while A[i] != X:
Что плохо?
i += 1
print ( "A[", i, "]=", X, sep = "" )
?
i=0
while i < N and A[i] != X:
i += 1
Что если такого нет?
if i < N:
print ( "A[", i, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
?
286. Поиск в массиве
Программирование (Python)Поиск в массиве
Вариант с досрочным выходом:
номер найденного
элемента
nX = -1
for i in range ( N ):
if A[i] == X:
nX = i
досрочный
break
выход из цикла
if nX >= 0:
print ( "A[", nX, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
286
287. Поиск в массиве
Программирование (Python)Поиск в массиве
Варианты в стиле Python:
for i in range ( N ):
if A[i] == X:
print ( "A[", i, "]=", X, sep = "" )
break
else:
print ( "Не нашли!" )
если не было досрочного выхода из цикла
if X in A:
nX = A.index(X)
print ( "A[", nX, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
287
288. Задачи
Программирование (Python)Задачи
«A»: Заполните массив случайными числами в интервале
[0,5]. Введите число X и найдите все значения, равные X.
Пример:
Массив:
1 2 3 1 2
Что ищем:
2
Нашли: A[2]=2, A[5]=2
Пример:
Массив:
1 2 3 1 2
Что ищем:
6
Ничего не нашли.
288
289. Задачи
Программирование (Python)Задачи
«B»: Заполните массив случайными числами в интервале
[0,5]. Определить, есть ли в нем элементы с
одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1 2 3 3 2 1
Есть: 3
Пример:
Массив:
1 2 3 4 2 1
Нет
289
290. Задачи
Программирование (Python)Задачи
«C»: Заполните массив случайными числами. Определить,
есть ли в нем элементы с одинаковыми значениями, не
обязательно стоящие рядом.
Пример:
Массив:
3 2 1 3 2 5
Есть: 3, 2
Пример:
Массив:
3 2 1 4 0 5
Нет
290
291. Максимальный элемент
Программирование (Python)291
Максимальный элемент
M = A[0]
for i in range(1,N):
if A[i] > M:
Если range(N)?
M = A[i]
print ( M )
?
Варианты в стиле Python:
M = A[0]
for x in A:
if x > M:
M=x
M = max ( A )
? Как найти его номер?
292. Максимальный элемент и его номер
Программирование (Python)292
Максимальный элемент и его номер
M = A[0]; nMax = 0
for i in range(1,N):
if A[i] > M:
Что можно улучшить?
M = A[i]
nMax = ii
print ( "A[", nMax, "]=", M, sep = "" )
?
! По номеру элемента можно найти значение!
nMax = 0
for i in range(1,N):
if A[i] > A[nMax]
A[nMax]:
nMax = i
print ( "A[", nMax, "]=", A[nMax]
A[nMax], sep = "" )
293. Максимальный элемент и его номер
Программирование (Python)293
Максимальный элемент и его номер
Вариант в стиле Python:
M = max(A)
nMax = A.index(M)
print ( "A[", nMax, "]=", M, sep = "" )
номер заданного
элемента (первого из…)
294. Задачи
Программирование (Python)Задачи
«A»: Заполнить массив случайными числами и найти
минимальный и максимальный элементы массива и их
номера.
Пример:
Массив:
1 2 3 4 5
Минимальный элемент: A[1]=1
Максимальный элемент: A[5]=5
«B»: Заполнить массив случайными числами и найти два
максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5
294
295. Задачи
Программирование (Python)Задачи
«C»: Введите массив с клавиатуры и найдите (за один проход)
количество элементов, имеющих максимальное
значение.
Пример:
Массив:
3 4 5 5 3 4 5
Максимальное значение 5
Количество элементов 3
295
296. Перестановка элементов массива
Программирование (Python)296
Перестановка элементов массива
? Как поменять местами значения двух
переменных a и b?
вспомогательная
переменная
элементы массива:
с = a
a = b
b = c
с = A[i]
A[i] = A[k]
A[k] = c
297. Перестановка пар соседних элементов
Программирование (Python)297
Перестановка пар соседних элементов
Задача. Массив A содержит чётное количество
элементов N. Нужно поменять местами пары соседних
элементов: 0-й с 1-м, 2-й — с 3-м и т. д.
0
1
2
3
7
12
38
5
0
1
2
3
12
7
5
38
…
…
N-2
N-1
40
23
N-2
N-1
23
40
298. Перестановка пар соседних элементов
Программирование (Python)298
Перестановка пар соседних элементов
for i in range(N):
поменять местами A[i] и A[i+1]
0
1
2
3
Что плохо?
?
4
5
7
12
38
5
40
23
12
7
38
5
40
23
12
38
7
5
40
выход
23 за границы
массива
12
38
5
7
40
23
12
38
5
40
7
23
12
38
5
40
23
7
?
299. Перестановка пар соседних элементов
Программирование (Python)Перестановка пар соседних элементов
for i in range(0,N,2):
# переставляем A[i] и A[i+1]
с = A[i]
A[i] = A[i+1]
A[i+1] = c
A[1] A[2], A[3] A[4], …, A[N-1] A[N]
299
300. Реверс массива
Программирование (Python)300
Реверс массива
Задача. Переставить элементы массива в обратном
порядке (выполнить реверс).
0
1
2
7
12
5
0
1
2
23
40
38
A[0] A[N-1]
A[1] A[N-2]
A[i] A[N-1-i]
A[N-1] A[0]
…
…
N-3
N-2
N-1
38
40
23
N-3
N-2
N-1
5
12
7
0+N-1 = N-1
1+N-2 = N-1
i+??? = N-1
N-1+0 = N-1
301. Реверс массива
Программирование (Python)301
Реверс массива
(N % 2):
for i in range(N):
поменять местами A[i] и A[N+1-i]
? Что плохо?
0
1
2
3
7
12
40
23
i=0
23
12
40
7
i=1
23
40
12
7
i=2
23
12
40
7
i=3
7
12
40
23
? Как исправить?
302. Срезы в Python
Программирование (Python)302
Срезы в Python
0
разрезы
0
1
2
3
N-4
N-3
N-2
N-1
7
12
5
8
18
34
40
23
1
A[1:3]
A[2:3]
A[:3]
2
3
N-4
N-3
N-2
N-1
N
[12, 5]
[5]
A[0:3]
[7, 12, 5]
с начала
A[3:N-2]
A[3:]
[8,…,18,34]
A[3:N]
до конца
A[:]
[8,…,18,34,40,23]
копия массива
[7,12,5,8,…,18,34,40,23]
303. Срезы в Python – отрицательные индексы
Программирование (Python)303
Срезы в Python – отрицательные индексы
разрезы
0
0
1
2
3
N-4
N-3
N-2
N-1
7
12
5
8
18
34
40
23
1
A[1:-1]
A[1:N-1]
A[-4:-2]
A[N-4:N-2]
2
3
N-4
N-3
N-2
[12,5,8,…,18,34,40]
[18, 34]
N-1
N
304. Срезы в Python – шаг
Программирование (Python)304
Срезы в Python – шаг
разрезы
0
1
2
3
4
5
6
7
8
7
12
5
8
76
18
34
40
23
0
1
2
3
4
5
6
7
8
9
шаг
A[1:6:2]
A[::3]
A[8:2:-2]
A[::-1]
[12, 8, 18]
[7, 8, 34]
[23, 34, 76]
[23,40,34,18,76,8,5,12,7]
реверс!
A.reverse()
305. Задачи
Программирование (Python)Задачи
«A»: Заполнить массив случайными числами и выполнить
циклический сдвиг элементов массива вправо на 1
элемент.
Пример:
Массив:
1 2 3 4 5 6
Результат:
6 1 2 3 4 5
«B»: Массив имеет четное число элементов. Заполнить
массив случайными числами и выполнить реверс
отдельно в первой половине и второй половине.
Пример:
Массив:
1 2 3 4 5 6
Результат:
3 2 1 6 5 4
305
306. Задачи
Программирование (Python)Задачи
«C»: Заполнить массив случайными числами в интервале [100,100] и переставить элементы так, чтобы все
положительные элементы стояли в начала массива, а
все отрицательные и нули – в конце. Вычислите
количество положительных элементов.
Пример:
Массив:
20 -90 15 -34 10 0
Результат:
20 15 10 -90 -34 0
Количество положительных элементов: 3
306
307. Отбор нужных элементов
Программирование (Python)307
Отбор нужных элементов
Задача. Отобрать элементы массива A,
удовлетворяющие некоторому условию, в массив B.
Простое решение:
B = []
сделать для i от 0 до N-1
если условие выполняется для A[i] то
добавить A[i] к массиву B
B = []
for x in A:
if x % 2 == 0:
B.append(x)
? Какие элементы выбираем?
добавить x в конец
массива B
308. Отбор нужных элементов
Программирование (Python)308
Отбор нужных элементов
Задача. Отобрать элементы массива A,
удовлетворяющие некоторому условию, в массив B.
Решение в стиле Python:
перебрать все
элементы A
B = [ x for x in A ]
if x % 2 == 0 ]
если x – чётное
число
309. Задачи
Программирование (Python)Задачи
«A»: Заполнить массив случайными числами в интервале
[-10,10] и отобрать в другой массив все чётные
отрицательные числа.
Пример:
Массив А:
-5 6 7 -4 -6 8 -8
Массив B:
-4 -6 -8
«B»: Заполнить массив случайными числами в интервале
[0,100] и отобрать в другой массив все простые числа.
Используйте логическую функцию, которая определяет,
является ли переданное ей число простым.
Пример:
Массив А:
12 13 85 96 47
Массив B:
13 47
309
310. Задачи
Программирование (Python)Задачи
«C»: Заполнить массив случайными числами и отобрать в
другой массив все числа Фибоначчи. Используйте
логическую функцию, которая определяет, является ли
переданное ей число числом Фибоначчи.
Пример:
Массив А:
12 13 85 34 47
Массив B:
13 34
310
311. Особенности работы со списками
Программирование (Python)311
Особенности работы со списками
A = [1, 2, 3]
B=A
A
B
[1, 2, 3]
A[0] = 0
A = [1, 2, 3]
B = A[:]
A
B
[0, 2, 3]
A
[0, 2, 3]
B
[1, 2, 3]
копия массива A
A
[1, 2, 3]
B
[1, 2, 3]
A[0] = 0
312. Копирование списков
Программирование (Python)312
Копирование списков
«Поверхностное» копирование:
import copy
A = [1, 2, 3]
B = copy.copy(A)
A = [1, 2, 3]
B = [4, 5, 6]
C = [A, B]
D = copy.copy(C)
C[0][0] = 0
A
«Глубокое» копирование:
D = copy.deepcopy(C)
A
[1,2,3]
B
[4,5,6]
C
[A,B]
D
[A,B]
A
B
0
[1,2,3]
[4,5,6]
! Влияет на C и D!
C
[A,B] A
B
D
[ , ]
[1,2,3]
[4,5,6]
[1,2,3]
[4,5,6]
313. Программирование на языке Python
313Программирование
на языке Python
§ 64. Сортировка
314. Что такое сортировка?
Программирование (Python)314
Что такое сортировка?
Сортировка – это расстановка элементов массива в
заданном порядке.
…по возрастанию, убыванию, последней цифре, сумме
делителей, по алфавиту, …
Алгоритмы:
• простые и понятные, но неэффективные для больших
массивов
время
работы
▫ метод пузырька
▫ метод выбора
• сложные, но эффективные
▫ «быстрая сортировка» (QuickSort)
N
▫ сортировка «кучей» (HeapSort)
▫ сортировка слиянием (MergeSort)
▫ пирамидальная сортировка
315. Метод пузырька (сортировка обменами)
Программирование (Python)315
Метод пузырька (сортировка обменами)
Идея: пузырек воздуха в стакане воды поднимается со
дна вверх.
Для массивов – самый маленький («легкий» элемент
перемещается вверх («всплывает»).
1-й проход:
4
4
4
4
1
5
5
5
1
4
2
2
1
5
5
1
1
2
2
2
3
3
3
3
3
• сравниваем два соседних
элемента; если они стоят
«неправильно», меняем
их местами
• за 1 проход по массиву
один элемент (самый
маленький) становится на
свое место
316. Метод пузырька
Программирование (Python)316
Метод пузырька
2-й проход:
3-й проход:
4-й проход:
1
1
1
1
1
1
1
1
1
4
4
4
2
2
2
2
2
2
5
5
2
4
4
4
3
3
3
2
2
5
5
5
3
4
4
4
3
3
3
3
3
5
5
5
5
сортировки массива из N элементов нужен
! Для
N-1 проход (достаточно поставить на свои места
N-1 элементов).
317. Метод пузырька
Программирование (Python)317
Метод пузырька
1-й проход:
сделать для j от N-2 до 0 шаг -1
если A[j+1]< A[j] то
# поменять местами A[j] и A[j+1]
единственное
отличие!
2-й проход:
сделать для j от N-2 до 1 шаг -1
если A[j+1]< A[j] то
# поменять местами A[j] и A[j+1]
318. Метод пузырька
Программирование (Python)Метод пузырька
318
от N-2 до 0 шаг -1
1-й проход:
for j in range(N-2, -1 ,-1):
if A[j+1]< A[j]:
# поменять местами A[j] и A[j+1]
единственное
отличие!
2-й проход:
for j in range(N-2, 0 ,-1):
if A[j+1]< A[j]:
# поменять местами A[j] и A[j+1]
319. Метод пузырька
Программирование (Python)Метод пузырька
for i in range(N-1):
for j in range(N-2, i-1 ,-1):
if A[j+1] < A[j]:
A[j], A[j+1] = A[j+1], A[j]
? Как написать метод «камня»?
? Как сделать рекурсивный вариант?
319
320. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, в которой сортировка выполняется
«методом камня» – самый «тяжёлый» элемент
опускается в конец массива.
«B»: Напишите вариант метода пузырька, который
заканчивает работу, если на очередном шаге внешнего
цикла не было перестановок.
«С»: Напишите программу, которая сортирует массив по
убыванию суммы цифр числа. Используйте функцию,
которая определяет сумму цифр числа.
320
321. Метод выбора (минимального элемента)
Программирование (Python)Метод выбора (минимального элемента)
Идея: найти минимальный элемент и поставить его на
первое место.
for i in range(N-1):
найти номер nMin минимального
элемента из A[i]..A[N]
if i != nMin:
поменять местами A[i] и A[nMin]
321
322. Метод выбора (минимального элемента)
Программирование (Python)Метод выбора (минимального элемента)
for i in range(N-1):
nMin = i
for j in range(i+1,N):
if A[j] < A[nMin]:
nMin = j
if i!= nMin:
A[i], A[nMin] = A[nMin], A[i]
322
323. Задачи
Программирование (Python)Задачи
«A»: Массив содержит четное количество элементов.
Напишите программу, которая сортирует первую
половину массива по возрастанию, а вторую – по
убыванию. Каждый элемент должен остаться в «своей»
половине.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
323
324. Задачи
Программирование (Python)Задачи
«B»: Напишите программу, которая сортирует массив и
находит количество различных чисел в нем.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5
«C»: Напишите программу, которая сравнивает число
перестановок элементов при использовании сортировки
«пузырьком» и методом выбора. Проверьте ее на разных
массивах, содержащих 1000 случайных элементов,
вычислите среднее число перестановок для каждого
метода.
324
325. Быстрая сортировка (QuickSort)
Программирование (Python)325
Быстрая сортировка (QuickSort)
Идея: выгоднее переставлять элементы,
который находятся дальше друг от друга.
Ч.Э.Хоар
6
5
4
3
2
1
1
5
4
3
2
6
1
2
4
3
5
6
1
2
3
4
5
6
массива из N элементов нужно всего
! Для
N/2 обменов!
326. Быстрая сортировка
Программирование (Python)326
Быстрая сортировка
Шаг 1: выбрать некоторый элемент массива X
Шаг 2: переставить элементы так:
A[i] <= X
A[i] >= X
при сортировке элементы не покидают « свою область»!
Шаг 3: так же отсортировать две получившиеся области
Разделяй и властвуй (англ. divide and conquer)
78
6
82
67
?
55
44
34
Как лучше выбрать X?
Медиана – такое значение X, что слева и справа от него в
отсортированном массиве стоит одинаковое число
элементов (для этого надо отсортировать массив…).
327. Быстрая сортировка
Программирование (Python)327
Быстрая сортировка
Разделение:
1) выбрать любой элемент массива (X=67)
78
6
82
67
55
44
34
2) установить L = 1, R = N
3) увеличивая L, найти первый элемент A[L],
который >= X (должен стоять справа)
4) уменьшая R, найти первый элемент A[R],
который <= X (должен стоять слева)
5) если L<=R то поменять местами A[L] и A[R]
и перейти к п. 3
иначе стоп.
328. Быстрая сортировка
Программирование (Python)328
Быстрая сортировка
78
L
6
82
67
55
44
34
R
34
6
82
L
67
55
44
R
78
34
6
44
67
L
55
R
82
78
34
6
44
55
R
67
L
82
78
! L > R : разделение закончено!
329. Быстрая сортировка
Программирование (Python)Быстрая сортировка
Основная программа:
N=7
A = [0]*N
# заполнить массив
qSort( A, 0, N-1 ) # сортировка
# вывести результат
329
330. Быстрая сортировка
Программирование (Python)330
Быстрая сортировка
массив
начало
конец
def qSort ( A, nStart, nEnd ):
if nStart >= nEnd: return
L = nStart; R = nEnd
X = A[(L+R)//2]
while L <= R:
разделение
while A[L] < X: L += 1
на 2 части
while A[R] > X: R -= 1
if L <= R:
A[L], A[R] = A[R], A[L]
L += 1; R -= 1
рекурсивные
qSort ( A, nStart, R )
вызовы
qSort ( A, L, nEnd )
331. Быстрая сортировка
Программирование (Python)Быстрая сортировка
Случайный выбор элемента-разделителя:
from random import randint
def qSort ( A, nStart, nEnd ):
...
X = A[randint(L,R)]
...
или так:
from random import choice
def qSort ( A, nStart, nEnd ):
...
X = choice ( A[L:R+1] )
...
331
332. Быстрая сортировка
Программирование (Python)332
Быстрая сортировка
В стиле Python:
from random import choice
окончание
def qSort ( A ):
рекурсии
if len(A) <= 1: return A
X = random.choice(A)
B1 = [ b for b in A if b < X ]
BX = [ b for b in A if b == X ]
B2 = [ b for b in A if b > X ]
return qSort(B1) + BX + qSort(B2)
рекурсивные вызовы
Asort = qSort( A )
? Что плохо?
333. Быстрая сортировка
Программирование (Python)333
Быстрая сортировка
Сортировка массива случайных значений:
N
метод
пузырька
метод
выбора
быстрая
сортировка
1000
0,09 с
0,05 с
0,002 с
5000
2,4 с
1,2 с
0,014 с
15000
22 с
11 с
0,046 с
334. Сортировка в Python
Программирование (Python)334
Сортировка в Python
По возрастанию:
B = sorted( A )
алгоритм
Timsort
По убыванию:
B = sorted( A, reverse = True )
По последней цифре:
def lastDigit ( n ):
return n % 10
B = sorted( A, key = lastDigit )
или так:
B = sorted( A, key = lambda x: x % 10 )
«лямбда»-функция
(функция без имени)
335. Сортировка в Python – на месте
Программирование (Python)Сортировка в Python – на месте
По возрастанию:
A.sort()
По убыванию:
A.sort ( reverse = True )
По последней цифре:
def lastDigit ( n ):
return n % 10
A.sort ( key = lastDigit )
или так:
lambda x:
x: xx %% 10
10 )
A.sort( key = lambda
335
336. Задачи
Программирование (Python)Задачи
«A»: Массив содержит четное количество элементов.
Напишите программу, которая сортирует по возрастанию
отдельно элементы первой и второй половин массива.
Каждый элемент должен остаться в «своей» половине.
Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
336
337. Задачи
Программирование (Python)Задачи
«B»: Напишите программу, которая сортирует массив и
находит количество различных чисел в нем. Используйте
алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5
337
338. Задачи
Программирование (Python)Задачи
«C»: Напишите программу, которая сравнивает число
перестановок элементов при использовании сортировки
«пузырьком», методом выбора и алгоритма быстрой
сортировки. Проверьте ее на разных массивах,
содержащих 1000 случайных элементов, вычислите
среднее число перестановок для каждого метода.
«D»: Попробуйте построить массив из 10 элементов, на
котором алгоритм быстрой сортировки c с выбором
среднего элемента показывает худшую эффективность
(наибольшее число перестановок). Сравните это
количество перестановок с эффективностью метода
пузырька (для того же массива).
338
339. Программирование на языке Python
339Программирование
на языке Python
§ 65. Двоичный поиск
340. Двоичный поиск
Программирование (Python)340
Двоичный поиск
X=7
1
1
1
2
2
2
3
3
3
4
4
5
5
5
6
6
7
7
7
8
8
8
9
9
9
10
10
10
11
11
11
12
12
12
13
13
13
14
14
14
15
15
15
16
16
16
4
X<8
1. Выбрать средний элемент A[c] и
сравнить с X.
2. Если X == A[c], то нашли (стоп).
3. Если X < A[c], искать дальше в
первой половине.
4. Если X > A[c], искать дальше во
второй половине.
X>4
X>6
6
341. Двоичный поиск
Программирование (Python)341
Двоичный поиск
X = 44
A[0]
6
34
44
L
67
78
82
с
6
34
L
с
6
34
L
6
55
A[N-1] A[N]
34
L
44
55
R
67
78
82
R
44
55
с
R
44
55
67
78
82
67
78
82
R
! L = R-1 : поиск завершен!
342. Двоичный поиск
Программирование (Python)Двоичный поиск
L = 0; R = N
# начальный отрезок
while L < R-1:
c = (L+R) // 2
# нашли середину
if X < A[c]:
# сжатие отрезка
R=c
else: L = c
if A[L] == X:
print ( "A[", L, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
342
343. Двоичный поиск
Программирование (Python)343
Двоичный поиск
Число сравнений:
N
линейный
поиск
двоичный
поиск
2
2
2
16
16
5
1024
1024
11
1048576
1048576
21
скорость выше, чем при линейном поиске
нужна предварительная сортировка
? Когда нужно применять?
344. Задачи
Программирование (Python)Задачи
«A»: Заполнить массив случайными числами и отсортировать
его. Ввести число X. Используя двоичный поиск,
определить, есть ли в массиве число, равное X.
Подсчитать количество сравнений.
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
2
Число 2 найдено.
Количество сравнений: 2
344
345. Задачи
Программирование (Python)Задачи
«B»: Заполнить массив случайными числами и отсортировать
его. Ввести число X. Используя двоичный поиск,
определить, сколько чисел, равных X, находится в
массиве.
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
4
Число 4 встречается 2 раз(а).
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
14
Число 14 не встречается.
345
346. Задачи
Программирование (Python)Задачи
«C»: Заполнить массив случайными числами и ввести число и
отсортировать его. Ввести число X. Используя двоичный
поиск, определить, есть ли в массиве число, равное X.
Если такого числа нет, вывести число, ближайшее к X.
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 12 19
Введите число X:
12
Число 12 найдено.
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 12 19
Введите число X:
11
Число 11 не найдено. Ближайшее число 12.
346
347. Программирование на языке Python
347Программирование
на языке Python
§ 66. Символьные строки
348. Что такое символьная строка?
Программирование (Python)Что такое символьная строка?
Символьная строка – это последовательность
символов.
• строка – единый объект
• длина строки может меняться во время работы
программы
348
349. Символьные строки
Программирование (Python)Символьные строки
Присваивание:
s = "Вася пошёл гулять"
Ввод с клавиатуры:
s = input()
Вывод на экран:
print(s)
Длина строки:
n = len(s)
length – длина
349
350. Сравнение строк
Программирование (Python)350
Сравнение строк
?
print("Введите пароль: ")
Какой правильный
s = input()
пароль?
if s == "sEzAm":
print("Слушаюсь и повинуюсь!")
else:
print("Пароль неправильный")
? Как одна строка может быть меньше другой?
стоит раньше в отсортированном списке
351. Сравнение строк
Программирование (Python)351
Сравнение строк
s1 = "паровоз"
s2 = "пароход"
if s1 < s2:
print(s1, "<", s2)
elif s1 == s2:
print(s1, "=", s2)
else:
print(s1, ">", s2)
? Что выведет?
паровоз < пароход
первые отличающиеся
буквы
Сравниваем с начала: паровоз
пароход
«в»: код 1074
«х»: код 1093
! в < х!
352. Обращение к символу по номеру
Программирование (Python)352
Обращение к символу по номеру
print ( s[5] )
print ( s[-2] )
0
1
2
3
4
5
6
П
р
и
в
е
т
!
s[len(s)-2]
s[0] s[1] s[2] s[3] s[4] s[5] s[6]
! Символы нумеруются с нуля!
составить «кот»
s = "информатика"
kot = s[-2]+s[3]+s[-4]
353. Посимвольная обработка строк
Программирование (Python)353
Посимвольная обработка строк
! Строка неизменна!
s[4] = "a"
Задача. Ввести строку и заменить в ней все буквы «э» на
буквы «е».
строим новую
строку!
sNew = ""
for i in range(len(s)
) :
range(len(s))
if s[i] == "э":
sNew += "е"
для каждого
символа строки
else:
sNew += s[i]
0
1
2
3
4
5
6
П
р
и
в
э
т
!
len(s)-1
354. Цикл перебора символов
Программирование (Python)354
Цикл перебора символов
sNew = ""
for c in s:
if c == "э":
sNew += "е"
else:
sNew += c
перебрать
все символы
строки
c
П
р
и
в
э
т
!
355. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая вводит строку,
состоящую только из точек и букв Х, и заменяет в
ней все точки на нули и все буквы X на единицы.
Пример:
Введите строку: ..X.XX.
Двоичный код: 0010110
«B»: Напишите программу, которая в символьной строке
заменяет все нули на единицы и наоборот.
Остальные символы не должны измениться.
Пример:
Введите строку: 10а01Bx1010c
Инверсия: 01a10Bx0101c
355
356. Символьные строки
Программирование (Python)356
Символьные строки
Начальное значение:
! Строка – это
s = "Привет!"
последовательность
символов!
Вывод на экран:
print ( s )
print ( s[5] )
print ( s[-2] )
0
1
2
3
4
5
6
П
р
и
в
е
т
!
s[0] s[1] s[2] s[3] s[4] s[5] s[6]
Длина строки:
n = len ( s )
s[len(s)-2]
357. Символьные строки
Программирование (Python)Символьные строки
Ввод с клавиатуры:
s = input ( "Введите имя: " )
Изменение строки:
s[4] = "a"
! Строка – это неизменяемый объект!
... но можно составить новую строку:
s1 = s + "a"
357
358. Символьные строки
Программирование (Python)Символьные строки
Задача: заменить в строке все буквы "а" на буквы "б".
s = input( "Введите строку:" )
s1 = ""
# строка-результат
for c in s:
перебрать все
символы в строке
if c == "а":
c = "б"
s1 = s1 + c
добавить символ к
print ( s1 )
строке-результату
358
359. Операции со строками
Программирование (Python)359
Операции со строками
Объединение (конкатенация) :
s1 = "Привет"
"Привет, Вася!"
s2 = "Вася"
s = s1 + ", " + s2 + "!"
Умножение:
s = "АУ"
s5 = s*5
s5 = s + s + s + s + s
? Что получим?
АУАУАУАУАУ
360. Срезы строк (выделение части строки)
Программирование (Python)360
Срезы строк (выделение части строки)
s = "0123456789"
s1 = s[3:8]
# "34567"
с какого
символа
до какого
(не включая 8)
s = "0123456789"
s1 = s[:8]
# "01234567"
от начала строки
s = "0123456789"
s1 = s[3:]
# "3456789"
до конца строки
361. Срезы строк
Программирование (Python)361
Срезы строк
Срезы с отрицательными индексами:
s = "0123456789"
s1 = s[:-2]
# "01234567"
len(s)-2
s = "0123456789"
s1 = s[-6:-2]
len(s)-6
len(s)-2
# "4567"
362. Операции со строками
Программирование (Python)362
Операции со строками
Удаление:
s = "0123456789"
s1 = s[:3] + s[9:]
"012"
"9"
"0129"
Вставка:
s = "0123456789"
s1 = s[:3] + "ABC" + s[3:]
"012"
"3456789"
"012ABC3456789"
363. Поиск в строках
Программирование (Python)363
Поиск в строках
s = "Здесь был Вася."
n = s.find ( "с" )
# n = 3
if n >= 0:
print ( "Номер символа", n )
else:
print ( "Символ не найден." )
! Находит первое слева вхождение
подстроки!
Поиск с конца строки:
s = "Здесь был Вася."
n = s.rfind ( "с" )
# n = 12
364. Задачи
Программирование (Python)Задачи
«A»: Ввести с клавиатуры в одну строку фамилию и имя,
разделив их пробелом. Вывести первую букву имени с
точкой и потом фамилию.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр
П. Иванов
«B»: Ввести с клавиатуры в одну строку фамилию, имя и
отчество, разделив их пробелом. Вывести фамилию и
инициалы.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
П.С. Иванов
364
365. Задачи
Программирование (Python)Задачи
«C»: Ввести адрес файла и «разобрать» его на части,
разделенные знаком "/". Каждую часть вывести в
отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2015/Байкал/shaman.jpg
C:
Фото
2015
Байкал
shaman.jpg
365
366. Преобразования «строка» «число»
Программирование (Python)366
Преобразования «строка» «число»
Из строки в число:
s = "123"
N = int ( s )
s = "123.456"
X = float ( s )
# N = 123
# X = 123.456
Из числа в строку:
N = 123
s = str ( N )
s = "{:5d}".format(N)
# s = "123"
# s = " 123"
X = 123.456
s = str ( X )
# s = "123.456"
s = "{:7.2f}".format(X) # s = " 123.46"
s = "{:10.2e}".format(X) # s = " 1.23e+02"
367. Задачи
Программирование (Python)Задачи
«A»: Ввести с клавиатуры символьную строку и заменить в
ней все буквы «а» на «б» и все буквы «б» на «а»
(заглавные на заглавные, строчные на строчные).
Пример:
Введите строку:
ааббААББссСС
Результат:
ббааББААссСС
367
368. Задачи
Программирование (Python)Задачи
«B»: Ввести с клавиатуры символьную строку и определить,
сколько в ней слов. Словом считается
последовательности непробельных символов,
отделенная с двух сторон пробелами (или стоящая с
краю строки). Слова могут быть разделены несколькими
пробелами, в начале и в конце строки тоже могут быть
пробелы.
Пример:
Введите строку:
Вася пошел
гулять
Найдено слов: 3
368
369. Задачи
Программирование (Python)Задачи
«C»: Ввести с клавиатуры символьную строку и найдите
самое длинное слово и его длину. Словом считается
последовательности непробельных символов,
отделенная с двух сторон пробелами (или стоящая с
краю строки). Слова могут быть разделены несколькими
пробелами, в начале и в конце строки тоже могут быть
пробелы.
Пример:
Введите строку:
Вася
пошел гулять
Самое длинное слово: гулять, длина 6
369
370. Операции со строками
Программирование (Python)370
Операции со строками
Объединение (конкатенация) :
s1 = "Привет"
"Привет, Вася!"
s2 = "Вася"
s = s1 + ", " + s2 + "!"
Срезы:
s = "0123456789"
s1 = s[3:8]
разрезы
0
# "34567"
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
371. Операции со строками
Программирование (Python)371
Операции со строками
Срезы:
s = "0123456789"
s1 = s[:8]
# "01234567"
от начала строки
s = "0123456789"
s1 = s[3:]
# "3456789"
до конца строки
s1 = s[::-1]
реверс строки
# "9876543210"
372. Операции со строками
Программирование (Python)372
Операции со строками
Срезы с отрицательными индексами:
s = "0123456789"
s1 = s[:-2]
# "01234567"
N-2
s = "0123456789"
s1 = s[-6:-2]
N-6
N-2
# "4567"
373. Операции со строками
Программирование (Python)373
Операции со строками
Удаление:
s = "0123456789"
s1 = s[:3] + s[9:]
"012"
"9"
# "0129"
Вставка:
s = "0123456789"
s1 = s[:3] + "ABC" + s[3:]
"012ABC3456789"
374. Стандартные функции
Программирование (Python)374
Стандартные функции
Верхний/нижний регистр:
s = "aAbBcC"
s1 = s.upper()
s2 = s.lower()
# "AABBCC"
# "aabbcc"
Проверка на цифры:
s = "abc"
print ( s.isdigit() )
s1 = "123"
print ( s1.isdigit() )
… и много других.
# False
# True
375. Поиск в строках
Программирование (Python)375
Поиск в строках
s = "Здесь был Вася."
n = s.find ( "с" )
# n = 3
if n >= 0:
print ( "Номер символа", n )
else:
print ( "Символ не найден." )
! Находит первое слева вхождение
подстроки!
Поиск с конца строки:
s = "Здесь был Вася."
n = s.rfind ( "с" )
# n = 12
376. Пример обработки строк
Программирование (Python)Пример обработки строк
Задача: Ввести имя, отчество и фамилию. Преобразовать их к
формату «фамилия-инициалы».
Пример:
Введите имя, отчество и фамилию:
Василий Алибабаевич Хрюндиков
Результат:
Хрюндиков В.А.
Алибабаевич Хрюндиков
Алгоритм:
• найти первый пробел и выделить имя
Хрюндиков
• удалить имя с пробелом из основной строки
• найти первый пробел и выделить отчество
• удалить отчество с пробелом из основной строки
• «сцепить» фамилию, первые буквы имени и фамилии,
точки, пробелы…
Хрюндиков В.А.
376
377. Пример обработки строк
Программирование (Python)Пример обработки строк
print ( "Введите имя, отчество и фамилию:" )
s = input()
n = s.find ( " " )
name = s[:n]
# вырезать имя
s = s[n+1:]
n = s.find ( " " )
name2 = s[:n]
# вырезать отчество
s = s[n+1:]
# осталась фамилия
s = s + " " + name[0] + "." + name2[0] + "."
print ( s )
377
378. Пример обработки строк
Программирование (Python)378
Пример обработки строк
Решение в стиле Python:
print ( "Введите имя, отчество и фамилию:" )
s = input()
fio = s.split()
s = fio[2] + " " + fio[0][0] + "." + fio[1][0] + "."
print ( s )
Василий Алибабаевич Хрюндиков
fio[0]
fio[1]
fio[2]
379. Задачи
Программирование (Python)Задачи
«A»: Ввести с клавиатуры в одну строку фамилию, имя и
отчество, разделив их пробелом. Вывести фамилию и
инициалы.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
П.С. Иванов
379
380. Задачи
Программирование (Python)Задачи
«B»: Ввести адрес файла и «разобрать» его на части,
разделенные знаком "/". Каждую часть вывести в
отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2013/Поход/vasya.jpg
C:
Фото
2013
Поход
vasya.jpg
380
381. Задачи
Программирование (Python)Задачи
«C»: Напишите программу, которая заменяет во всей строке
одну последовательность символов на другую.
Пример:
Введите строку:
(X > 0) and (Y < X) and (Z > Y) and (Z <> 5)
Что меняем: and
Чем заменить: &
Результат
(X > 0) & (Y < X) & (Z > Y) & (Z <> 5)
381
382. Преобразования «строка» – «число»
Программирование (Python)382
Преобразования «строка» – «число»
Из строки в число:
s = "123"
N = int ( s )
s = "123.456"
X = float ( s )
# N = 123
# X = 123.456
Из числа в строку:
N = 123
s = str ( N )
s = "{:5d}".format(N)
# s = "123"
# s = " 123"
X = 123.456
s = str ( X )
# s = "123.456"
s = "{:7.2f}".format(X) # s = " 123.46"
s = "{:10.2e}".format(X) # s = " 1.23e+02"
383. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая вычисляет сумму трех
чисел, введенную в форме символьной строки. Все числа
целые.
Пример:
Введите выражение:
12+3+45
Ответ: 60
«B»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
только знаки «+» или «–»). Выражение вводится как
символьная строка, все числа целые.
Пример:
Введите выражение:
12-3+45
Ответ: 54
383
384. Задачи
Программирование (Python)Задачи
«C»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
знаки «+», «–», «*» и «/»). Выражение вводится как
символьная строка, все числа целые. Операция «/»
выполняется как целочисленное деление.
Пример:
Введите выражение:
12*3+45
Ответ: 81
384
385. Задачи
Программирование (Python)Задачи
«D»: Напишите программу, которая вычисляет выражение,
состоящее из трех чисел и двух знаков (допускаются
знаки «+», «–», «*» и «/») и круглых скобок. Выражение
вводится как символьная строка, все числа целые.
Операция «/» выполняется как целочисленное деление
(div).
Пример:
Введите выражение:
2*(3+45)+4
Ответ: 100
385
386. Строки в процедурах и функциях
Программирование (Python)386
Строки в процедурах и функциях
Задача: построить процедуру, которая заменяет в строке
s все вхождения слова-образца wOld на слово-замену
wNew.
пока слово wOld есть в строке s
удалить слово wOld из строки
вставить на это место слово wNew
? Что плохо?
wOld: "12"
wNew: "A12B"
зацикливание
387. Замена всех экземпляров подстроки
Программирование (Python)387
Замена всех экземпляров подстроки
wNew
wOld
а) res
s
s
б) res
wNew
в) res
s
г) res
s
388. Замена всех экземпляров подстроки
Программирование (Python)388
Замена всех экземпляров подстроки
s = "12.12.12"
s = replaceAll ( s, "12", "A12B" )
print( s )
рабочая строка s
"12.12.12"
".12.12"
".12"
""
результат res
""
"A12B"
"A12B.A12B"
"A12B.A12B.A12B"
389. Замена всех экземпляров подстроки
Программирование (Python)Замена всех экземпляров подстроки
def replaceAll ( s, wOld, wNew ):
lenOld = len(wOld)
res = ""
искать образец
while len(s) > 0:
p = s.find ( wOld )
if p < 0:
если не нашли
res = res + s
взять начало
return
перед образцом
if p > 0: res = res + s[:p]
res = res + wNew
добавить
слово-замену
if p+lenOld >= len(s):
s = ""
строка кончилась
else:
s = s[p+lenOld:]
взять «хвост»
return res
389
390. Замена всех экземпляров подстроки
Программирование (Python)Замена всех экземпляров подстроки
Встроенная функция:
s = "12.12.12"
s = s.replace( "12", "A12B" )
print ( s )
390
391. Задачи
Программирование (Python)391
Задачи
«A»: Напишите функцию, которая отсекает всю часть строки
после первого слова.
Пример:
Введите строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды
392. Задачи
Программирование (Python)Задачи
«B»: Напишите функцию, которая заменяет расширение
файла на заданное новое расширение.
Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.exe
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.work.xml
Введите новое расширение: tmp
Результат: qq.work.tmp
392
393. Задачи
Программирование (Python)Задачи
«C»: Напишите функцию, которая заменяет во всей строке все
римские числа на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в школе CXXIII состоялся
очередной выпуск XI классов.
Результат:
В 2013 году в школе 123 состоялся очередной
выпуск 11 классов.
393
394. Рекурсивный перебор
Программирование (Python)394
Рекурсивный перебор
Задача. В алфавите языка племени «тумба-юмба»
четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести
на экран все слова, состоящие из L букв, которые
можно построить из букв этого алфавита.
перебор L-1
символов
Ы
?
?
?
Ш
?
?
?
Ч
?
?
?
0
?
?
?
задача для слов длины
К сведена к задаче для
слов длины L-1!
395. Рекурсивный перебор
Программирование (Python)Рекурсивный перебор
перебор L символов
w[0]="Ы"
# перебор последних L-1 символов
w[0]="Ш"
# перебор последних L-1 символов
w[0]="Ч"
# перебор последних L-1 символов
w[0]="О"
# перебор последних L-1 символов
395
396. Рекурсивный перебор
Программирование (Python)396
Рекурсивный перебор
алфавит
слово
нужная
длина слова
def TumbaWords ( A, w, L ):
if len(w) == L:
слово полной длины
print ( w )
return
по всем символам
алфавита
for c in A:
TumbaWords ( A, w + c, L )
# основная программа
TumbaWords ( "ЫШЧО", "", 3 );
397. Задачи
Программирование (Python)Задачи
«A»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых вторая
буква «Ы». Подсчитайте количество таких слов.
«B»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых есть по
крайней мере две одинаковые буквы, стоящие рядом.
Подсчитайте количество таких слов.
Программа не должна строить другие слова, не
соответствующие условию.
397
398. Задачи
Программирование (Python)Задачи
«C»: В алфавите языке племени «тумба-юмба» четыре буквы:
«Ы», «Ш», «Ч» и «О». Нужно вывести на экран все
возможные слова, состоящие из K букв, в которых есть по
крайней мере две одинаковые буквы, не обязательно
стоящие рядом.
Программа не должна строить другие слова, не
соответствующие условию.
398
399. Сравнение строк
Программирование (Python)399
Сравнение строк
Пар ? пар ? парк
Сравнение по кодам символов:
CP-1251
UNCODE
CP-1251
UNCODE
CP-1251
UNCODE
0
48
48
1
49
49
...
...
...
8
56
56
9
57
57
A
65
B
66
...
...
Y
89
Z
90
65
66
...
89
90
a
b
...
y
z
97
97
98
98
...
...
121
121
122
122
400. Сравнение строк
Программирование (Python)400
Сравнение строк
А
Б
CP-1251 192 193
UNCODE 1040 1041
...
...
...
Ё
168
1025
...
...
...
Ю
Я
222 223
1070 1071
а
б
CP-1251 224 225
UNCODE 1072 1073
...
...
...
ё
184
1105
...
...
...
ю
я
254 255
1102 1103
5STEAM < STEAM < Steam < steam
steam < ПАР < Пар < пАр < пар < парк
401. Сортировка строк
Программирование (Python)401
Сортировка строк
aS = []
# пустой список строк
print ( "Введите строки для сортировки:" )
while True:
s1 = input()
if s1 == "": break
aS.append ( s1 )
aS.sort()
print ( aS )
# добавить строку в список
# сортировка
402. Задачи
Программирование (Python)Задачи
«A»: Вводится 5 строк, в которых сначала записан порядковый
номер строки с точкой, а затем – слово. Вывести слова в
алфавитном порядке.
Пример:
Введите 5 строк:
1. тепловоз
2. арбуз
3. бурундук
4. кефир
5. урядник
Список слов в алфавитном порядке:
арбуз, бурундук, кефир, тепловоз, урядник
402
403. Задачи
Программирование (Python)403
Задачи
«B»: Вводится несколько строк (не более 20), в которых сначала
записан порядковый номер строки с точкой, а затем –
слово. Ввод заканчивается пустой строкой. Вывести
введённые слова в алфавитном порядке.
Пример:
Введите слова:
1. тепловоз
2. арбуз
Список слов в алфавитном порядке:
арбуз, тепловоз
404. Задачи
Программирование (Python)404
Задачи
«C»: Вводится несколько строк (не более 20), в которых сначала
записаны инициалы и фамилии работников фирмы. Ввод
заканчивается пустой строкой. Отсортировать строки в
алфавитном порядке по фамилии.
Пример:
Введите ФИО:
А.Г. Урядников
Б.В. Тепловозов
В.Д. Арбузов
Список в алфавитном порядке:
В.Д. Арбузов
Б.В. Тепловозов
А.Г. Урядников
405. Программирование на языке Python
405Программирование
на языке Python
§ 67. Матрицы
406. Что такое матрица?
Программирование (Python)406
Что такое матрица?
нолик
нет знака
0
1
2
0
-1 0
1
крестик
1
-1 0
1
2
0
строка 1,
столбец 2
1 -1
? Как закодировать?
Матрица — это прямоугольная таблица, составленная
из элементов одного типа (чисел, строк и т.д.).
Каждый элемент матрицы имеет два индекса –
номера строки и столбца.
407. Создание матриц
Программирование (Python)407
Создание матриц
! Матрица – это список списков!
A = [[-1, 0, 1],
[-1, 0, 1],
[0, 1, -1]]
перенос на другую
строку внутри скобок
или так:
A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]]
! Нумерация элементов с нуля!
408. Создание матриц
Программирование (Python)408
Создание матриц
Нулевая матрица:
N=3
M=2
row = [0]*M
A = [row]*N
A
0
row
0
0
1
1
2
A[0][0] = 1
а правильно так:
A = []
for i in range(N):
A.append ( [0]*M )
A
0
0
1
0
1
0
0
0
0
2
A[0][0] = 1
409. Вывод матриц
Программирование (Python)409
Вывод матриц
print ( A )
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
def printMatrix ( A ):
for row in A:
for x in row:
print ( "{:4d}".format(x), end = "" )
print ()
1
4
7
2
5
8
3
6
9
? Зачем форматный вывод?
410. Простые алгоритмы
Программирование (Python)410
Простые алгоритмы
Заполнение случайными числами:
import random
Вложенный цикл!
for i in range(N):
for j in range(M):
A[i][j] = random.randint ( 20, 80 )
print ( "{:4d}".format(A[i][j]),
end = "" )
print()
!
Суммирование:
s=0
for i in range(N):
for j in range(M):
s += A[i][j]
print ( s )
s=0
for row in A:
s += sum(row)
print ( s )
411. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая заполняет квадратную
матрицу случайными числами в интервале [10,99], и
находит максимальный и минимальный элементы в
матрице и их индексы.
Пример:
Матрица А:
12 14 67 45
32 87 45 63
69 45 14 11
40 12 35 15
Максимальный элемент A[2,2]=87
Минимальный элемент A[3,4]=11
411
412. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая заполняет матрицу
случайными числами и находит максимальный
элемент на главной диагонали квадратной матрицы.
Пример:
Матрица А:
12 34 14 65
71 88 23 45
87 46 53 39
76 58 24 92
Результат: A[3][3] = 92
412
413. Задачи
Программирование (Python)Задачи
«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в
виде матрицы. Преобразовать рисунок в черно-белый по
следующему алгоритму:
1) вычислить среднюю яркость пикселей по всему рисунку
2) все пиксели, яркость которых меньше средней, сделать
черными (записать код 0), а остальные – белыми (код 255)
Пример:
Матрица А:
12 14 67 45
32 87 45 63
69 45 14 11
40 12 35 15
Средняя яркость 37.88
Результат:
0
0 255 255
0 255 255 255
255 255
0
0
255
0
0
0
413
414. Задачи
Программирование (Python)Задачи
«C»: Напишите программу, которая заполняет матрицу
случайными числами и находит минимальный из
чётных положительных элементов матрицы. Учтите,
что таких элементов в матрице может и не быть.
Пример:
Матрица А:
16 34 14 65
71 88 23 45
87 12 53 39
76 58 24 92
Результат: A[2][1] = 12
414
415. Задачи
Программирование (Python)Задачи
«С»: Заполните матрицу, содержащую N строк и M столбцов,
натуральными числами по спирали и змейкой, как на рисунках:
415
416. Перебор элементов матрицы
Программирование (Python)Перебор элементов матрицы
Главная диагональ:
for i in range(N):
# работаем с A[i][i]
Побочная диагональ:
for i in range(N):
# работаем с A[i][N-1-i]
Главная диагональ и под ней:
for i in range(N):
for j in range( i+1 ):
# работаем с A[i][j]
416
417. Перестановка строк и столбцов
Программирование (Python)Перестановка строк и столбцов
2-я и 4-я строки:
A[2], A[4] = A[4], A[2]
0
1
2
3
4
2-й и 4-й столбцы:
for i in range(N):
A[i][2], A[i][4] = A[i][4], A[i][2]
417
418. Выделение строк и столбцов
Программирование (Python)418
Выделение строк и столбцов
1-я строка:
R = A[1][:]
R = A[i]
2-й столбец:
C = []
for row in A:
C.append(row[2])
или так:
C = [ row[2] for row in A ]
главная диагональ:
D = [ A[i][i] for i in range(N) ]
419. Задачи
Программирование (Python)419
Задачи
«A»: Напишите программу, которая заполняет квадратную
матрицу случайными числами в интервале [10,99], а затем
записывает нули во все элементы выше главной
диагонали. Алгоритм не должен изменяться при изменении
размеров матрицы.
Пример:
Матрица А:
12 14 67 45
32 87 45 63
69 45 14 30
40 12 35 65
Результат:
12 0 0 0
32 87 0 0
69 45 14 0
40 12 35 65
420. Задачи
Программирование (Python)420
Задачи
«B»: Пиксели рисунка закодированы числами (обозначающими
цвет) в виде матрицы, содержащей N строк и M столбцов.
Выполните отражение рисунка сверху вниз:
1
2
3
7
8
9
4
5
6
4
5
6
7
8
9
1
2
3
«С»: Пиксели рисунка закодированы числами (обозначающими
цвет) в виде матрицы, содержащей N строк и M столбцов.
Выполните поворот рисунка вправо на 90 градусов:
1
2
3
7
4
1
4
5
6
8
5
2
7
8
9
9
6
3
421. Программирование на языке Python
421Программирование
на языке Python
§ 68. Работа с файлами
422. Как работать с файлами?
Программирование (Python)422
Как работать с файлами?
файлы
текстовые
«plain text»:
• текст, разбитый на строки;
• из специальных символов
только символы перехода
на новую строку
двоичные
• любые символы
• рисунки, звуки, видео, …
423. Принцип сэндвича
Программирование (Python)423
Принцип сэндвича
хлеб
начинка
хлеб
файловые переменныеуказатели
открыть файл
работа с файлом
закрыть файл
по умолчанию – на
чтение (режим "r")
Fin = open ( "input.txt" )
Fout = open ( "output.txt", "w" )
# здесь работаем с файлами
Fin.close()
"r" - чтение
Fout.close()
"w" – запись
"a" – добавление
424. Ввод данных
Программирование (Python)424
Ввод данных
Fin = open( "input.txt" )
Чтение строки:
s = Fin.readline()
# "1 2"
Чтение строки и разбивка по пробелам:
s = Fin.readline().split()
# ["1","2"]
Чтение целых чисел:
s = Fin.readline().split()
a, b = int(s[0]), int(s[1])
# ["1","2"]
или так:
a, b = [int(x) for x in s]
или так:
a, b = map( int, s )
425. Вывод данных в файл
Программирование (Python)Вывод данных в файл
a=1
b=2
Fout = open( "output.txt", "w" )
Fout.write ( "{:d} + {:d} = {:d}\n".format(
a, b, a+b) )
Fout.close()
! Все данные преобразовать в строку!
425
426. Чтение неизвестного количества данных
Программирование (Python)Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
пока не конец файла
прочитать число из файла
добавить его к сумме
Fin = open ( "input.txt" )
sum = 0
если конец файла,
while True:
вернёт пустую строку
s = Fin.readline()
if not s: break
sum += int(s)
Fin.close()
426
427. Чтение неизвестного количества данных
Программирование (Python)Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
sum = 0
Fin = open ( "input.txt" )
lst = Fin.readlines()
for s in lst:
прочитать все строки в
sum += int(s)
список строк
Fin.close()
427
428. Чтение неизвестного количества данных
Программирование (Python)Чтение неизвестного количества данных
Задача. В файле записано в столбик неизвестное
количество чисел. Найти их сумму.
sum = 0
with open ( "input.txt" ) as Fin:
for s in Fin:
sum += int(s)
или так:
sum = 0
for s in open ( "input.txt" ):
sum += int(s)
! Не нужно закрывать файл!
428
429. Задачи
Программирование (Python)Задачи
«A»: Напишите программу, которая находит среднее
арифметическое всех чисел, записанных в файле в
столбик, и выводит результат в другой файл.
«B»: Напишите программу, которая находит минимальное и
максимальное среди чётных положительных чисел,
записанных в файле, и выводит результат в другой файл.
Учтите, что таких чисел может вообще не быть.
«C»: В файле в столбик записаны целые числа, сколько их –
неизвестно. Напишите программу, которая определяет
длину самой длинной цепочки идущих подряд одинаковых
чисел и выводит результат в другой файл.
429
430. Обработка массивов
Программирование (Python)Обработка массивов
Задача. В файле записаны в столбик целые числа.
Вывести в другой текстовый файл те же числа,
отсортированные в порядке возрастания.
? В чем отличие от предыдущей задачи?
сортировки нужно удерживать все элементы в
! Для
памяти одновременно.
430
431. Обработка массивов
Программирование (Python)Обработка массивов
Ввод массива:
A = []
while True:
s = Fin.readline()
if not s: break
A.append ( int(s) )
Ввод в стиле Python:
s = Fin.read().split()
A = list ( map(int, s) )
Сортировка:
A.sort()
431
432. Обработка массивов
Программирование (Python)432
Обработка массивов
Вывод результата:
Fout = open ( "output.txt", "w" )
Fout.write ( str(A) )
[1, 2, 3]
Fout.close()
или так:
for x in A:
Fout.write ( str(x)+"\n" )
1
2
3
или так:
for x in A:
Fout.write ( "{:4d}".format(x) )
1
2
3
433. Задачи
Программирование (Python)433
Задачи
«A»: В файле в столбик записаны числа. Отсортировать их по
возрастанию последней цифры и записать в другой файл.
«B»: В файле в столбик записаны числа. Отсортировать их по
возрастанию суммы цифр и записать в другой файл.
Используйте функцию, которая вычисляет сумму цифр
числа.
«C»: В двух файлах записаны отсортированные по возрастанию
массивы неизвестной длины. Объединить их и записать
результат в третий файл. Полученный массив также
должен быть отсортирован по возрастанию.
434. Обработка строк
Программирование (Python)Обработка строк
Задача. В файле записано данные о собаках: в каждой
строчке кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка
Вывести в другой файл сведения о собаках, которым
меньше 5 лет.
пока не конец файла Fin
прочитать строку из файла Fin
разобрать строку – выделить возраст
если возраст < 5 то
записать строку в файл Fout
434
435. Чтение данных из файла
Программирование (Python)Чтение данных из файла
Чтение одной строки:
s = Fin.readline()
Разбивка по пробелам:
data = s.split()
Выделение возраста:
sAge = data[1]
age = int ( sAge )
Кратко всё вместе:
s = Fin.readline()
age = int ( s.split()[1] )
435
436. Обработка строк
Программирование (Python)Обработка строк
Полная программа:
Fin = open ( "input.txt" )
Fout = open ( "output.txt", "w" )
while True:
s = Fin.readline()
if not s: break
age = int ( s.split()[1] )
if age < 5:
Fout.write ( s )
Fin.close()
Fout.close()
436
437. Обработка строк
Программирование (Python)Обработка строк
или так:
lst = Fin.readlines()
for s in lst:
age = int ( s.split()[1] )
if age < 5:
Fout.write ( s )
или так:
for s in open ( "input.txt" ):
age = int ( s.split()[1] )
if age < 5:
Fout.write ( s )
437
438. Задачи
Программирование (Python)Задачи
«A»: В файле записаны данные о результатах сдачи экзамена.
Каждая строка содержит фамилию, имя и количество
баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл фамилии и имена тех учеников,
которые получили больше 80 баллов.
«B»: В предыдущей задаче добавить к полученному списку
нумерацию, сократить имя до одной буквы и поставить
перед фамилией:
П. Иванов
И. Петров
...
438
439. Задачи
Программирование (Python)Задачи
«C»: В файле записаны данные о результатах сдачи экзамена.
Каждая строка содержит фамилию, имя и количество
баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл данные учеников, которые
получили больше 80 баллов. Список должен быть
отсортирован по убыванию балла. Формат выходных
данных:
П. Иванов 98
И. Петров 96
...
439
440. Программирование (Python)
440Программирование
(Python)
§ 19. Символьные строки
441. Программирование (Python)
441Программирование
(Python)
§ 22. Сложность алгоритмов
442. Как сравнивать алгоритмы?
Программирование (Python)442
Как сравнивать алгоритмы?
• быстродействие (временна́я сложность)
• объём требуемой памяти (пространственная
сложность)
Обычно не бывает все хорошо!
• понятность
!
Время работы алгоритма – это количество
элементарных операций T, выполненных
исполнителем.
зависит от
количества данных
Функция T(N) называется
(размера массива N)
временно́й сложностью алгоритма
T(N) = 2N3
увеличится время работы
? Как
при увеличении N в 10 раз?
443. Примеры определения сложности
Программирование (Python)Примеры определения сложности
Задача 1. Вычислить сумму первых трёх элементов
массива (при N 3).
2 сложения
+ запись в
Sum = A[1] + A[2] + A[3] T(N) = 3
память
Задача 2. Вычислить сумму всех элементов массива.
T(N) = 2N + 1
Sum = 0
for i in range(N):
N сложений, N+1
Sum += A[i]
операций записи
443
444. Примеры определения сложности
Программирование (Python)Примеры определения сложности
Задача 3. Отсортировать все элементы массива по
возрастанию методом выбора.
for i in range(N-1):
nMin = i
for j in range(i+1,N):
if A[i] < A[nMin]:
nMin = j
A[i],A[nMin] = A[nMin],A[i]
Число сравнений:
N (N 1) 1 2 1
Tc (N ) (N 1) (N 2) ... 2 1
N N
2
2
2
Число перестановок: Tn(N) = N – 1
444
445. Примеры определения сложности
Программирование (Python)Примеры определения сложности
Задача 4. Найти сумму элементов квадратной матрицы
размером N N.
Sum = 0
for i in range(N):
for j in range(N):
Sum += A[i,j]
! Самостоятельно!
445
446. Сравнение алгоритмов по сложности
Программирование (Python)446
Сравнение алгоритмов по сложности
T1(N ) 10000 N
T2 (N ) 100 N
2
T3 (N ) N 3
? Какой алгоритм выбрать?
при N < 100:
T3
T
T3 (N ) T2 (N ) T1(N )
T2
при N > 100:
T1
T3 (N ) T2 (N ) T1(N )
! Нужно знать размер
0
100
N
данных!
447. Асимптотическая сложность
Программирование (Python)447
Асимптотическая сложность
Асимптотическая сложность – это оценка скорости
роста количества операций при больших значениях N.
постоянная
линейная
сложность O(N)
T(N) c N для N N0
сумма элементов массива:
T(N) = 2 N – 1 2 N для N 1
квадратичная
сложность O(N2)
O(N)
T(N) c N2 для N N0
сортировка методом выбора:
1 2 1
1 2
Tc (N ) N N N для N 0
2
2
2
O(N2)
448. Асимптотическая сложность
Программирование (Python)448
Асимптотическая сложность
кубичная
T(N) c N3 для N N0
сложность O(N3)
сложность O(2N)
задачи оптимизации,
полный перебор вариантов
сложность O(N!)
Факториал числа N: N ! = 1 2 3 … N
T(N)
N
N2
N3
2N
время выполнения
100 нс
10 мс
0,001 с
1013 лет
N = 100,
1 млрд оп/с
449. Асимптотическая сложность
Программирование (Python)449
Асимптотическая сложность
Алгоритм относится к классу
O( f(N) ), если найдется такая
постоянная c, что начиная с
некоторого N = N0 выполняется
условие
T(N) c f (N)
T
c f (N )
T (N )
0
N0
это верхняя
оценка!
O( N ) O( N2 ) O( N3 ) O( 2N )
«Алгоритм имеет сложность O(N2)».
обычно – наиболее точная
верхняя оценка!
N