1 of 194

Программирование�(Python)

§ 19. Символьные строки

§ 20. Обработка массивов

§ 21. Матрицы (двумерные массивы)

§ 22. Сложность алгоритмов

§ 23. Как разрабатывают программы?§ 23. Как разрабатывают программы?

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

§ 25. Функции

1

2 of 194

Программирование (Python)

§ 19. Символьные строки

2

3 of 194

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

3

Символьная строка – это последовательность символов.

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

Программирование (Python), 9 класс

4 of 194

Символьные строки

4

Присваивание:

s = "Вася пошёл гулять"

Ввод с клавиатуры:

s = input()

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

print(s)

Длина строки:

n = len(s)

length – длина

Программирование (Python), 9 класс

5 of 194

Сравнение строк

5

print("Введите пароль: ")

s = input()

if s == "sEzAm":

print("Слушаюсь и повинуюсь!")

else:

print("Пароль неправильный")

Какой правильный � пароль?

?

Как одна строка может быть меньше другой?

?

стоит раньше в отсортированном списке

Программирование (Python), 9 класс

6 of 194

Сравнение строк

6

s1 = "паровоз"

s2 = "пароход"

if s1 < s2:

print(s1, "<", s2)

elif s1 == s2:

print(s1, "=", s2)

else:

print(s1, ">", s2)

Что выведет?

?

паровоз < пароход

первые отличающиеся буквы

паровоз

пароход

Сравниваем с начала:

в < х!

!

«в»: код 1074

«х»: код 1093

Программирование (Python), 9 класс

7 of 194

Обращение к символу по номеру

7

print ( s[5] )

0	1	2	3	4	5	6
П	р	и	в	е	т	!
s[0]	s[1]	s[2]	s[3]	s[4]	s[5]	s[6]

print ( s[-2] )

s[len(s)-2]

Символы нумеруются с нуля!

!

s = "информатика"

kot = s[-2]+s[3]+s[-4]

составить «кот»

Программирование (Python), 9 класс

8 of 194

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

8

s[4] = "a"

Задача. Ввести строку и заменить в ней все буквы «э» на буквы «е».

sNew = ""

for i in range(len(s)) :

if s[i] == "э":

sNew += "е"

else:

sNew += s[i]

Строка неизменна!

!

строим новую строку!

0	1	2	3	4	5	6
П	р	и	в	э	т	!

range(len(s))

для каждого символа строки

len(s)-1

Программирование (Python), 9 класс

9 of 194

Цикл перебора символов

9

sNew = ""

for c in s:

if c == "э":

sNew += "е"

else:

sNew += c

перебрать все символы строки

for c in s:

П	р	и	в	э	т	!

c

Программирование (Python), 9 класс

10 of 194

Задачи

10

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

Пример:

Введите строку: ..X.XX.

Двоичный код: 0010110

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

Пример:

Введите строку: 10а01Bx1010c

Инверсия: 01a10Bx0101c

Программирование (Python), 9 класс

11 of 194

Задачи

11

«С»: Введите битовую строку и дополните её последним битом, который должен быть равен 0, если в исходной строке чётное число единиц, и равен 1, если нечётное (в получившейся строке должно всегда быть чётное число единиц).

Пример:

Введите битовую строку: 01101010110

Результат: 011010101100

Программирование (Python), 9 класс

12 of 194

Операции со строками

12

Объединение (конкатенация) :

s1 = "Привет"

s2 = "Вася"

s = s1 + ", " + s2 + "!"

"Привет, Вася!"

Умножение:

s = "АУ"

s5 = s*5

АУАУАУАУАУ

Что получим?

?

s5 = s + s + s + s + s

Программирование (Python), 9 класс

13 of 194

Срезы строк (выделение части строки)

13

s = "0123456789"

s1 = s[3:8] # "34567"

с какого символа

до какого �(не включая 8)

s = "0123456789"

s1 = s[:8] # "01234567"

от начала строки

s = "0123456789"

s1 = s[3:] # "3456789"

до конца строки

Программирование (Python), 9 класс

14 of 194

Срезы строк

14

Срезы с отрицательными индексами:

s = "0123456789"

s1 = s[:-2] # "01234567"

len(s)-2

s = "0123456789"

s1 = s[-6:-2] # "4567"

len(s)-2

len(s)-6

Программирование (Python), 9 класс

15 of 194

Операции со строками

15

Вставка:

s = "0123456789"

s1 = s[:3] + "ABC" + s[3:]

Удаление:

s = "0123456789"

s1 = s[:3] + s[9:]

"012"

"9"

"012ABC3456789"

"0129"

"012"

"3456789"

Программирование (Python), 9 класс

16 of 194

Поиск в строках

16

s = "Здесь был Вася."

n = s.find ( "с" ) # n = 3

if n >= 0:

print ( "Номер символа", n )

else:

print ( "Символ не найден." )

Находит первое слева вхождение подстроки!

!

s = "Здесь был Вася."

n = s.rfind ( "с" ) # n = 12

Поиск с конца строки:

Программирование (Python), 9 класс

17 of 194

Задачи

17

«A»: Ввести с клавиатуры в одну строку фамилию и имя, разделив их пробелом. Вывести первую букву имени с точкой и потом фамилию.

Пример:

Введите фамилию и имя:

Иванов Петр

П. Иванов

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

Пример:

Введите фамилию, имя и отчество:

Иванов Петр Семёнович

П.С. Иванов

Программирование (Python), 9 класс

18 of 194

Задачи

18

«C»: Ввести адрес файла и «разобрать» его на части, разделенные знаком "/". Каждую часть вывести в отдельной строке.

Пример:

Введите адрес файла:

C:/Фото/2015/Байкал/shaman.jpg

C:

Фото

2015

Байкал

shaman.jpg

Программирование (Python), 9 класс

19 of 194

Преобразования «строка» → «число»

19

Из строки в число:

s = "123"

N = int ( s ) # N = 123

s = "123.456"

X = float ( s ) # X = 123.456

Из числа в строку:

N = 123

s = str ( N ) # s = "123"

s = "{:5d}".format(N) # 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"

Программирование (Python), 9 класс

20 of 194

Задачи

20

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

Пример:

Введите выражение:

12+3

Ответ: 15

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

Пример:

Введите выражение:

12+3+45

Ответ: 60

Программирование (Python), 9 класс

21 of 194

Задачи

21

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

Пример:

Введите выражение:

12+134–45–17

Ответ: 84

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

Пример:

Введите выражение:

12+3+45+10

Ответ: 70

Программирование (Python), 9 класс

22 of 194

Программирование (Python)

§ 20. Обработка массивов.�Поток данных

22

23 of 194

Обработка потока данных

23

Задача. С клавиатуры вводятся числа, ввод завершается числом 0. Определить, сколько было введено положительных чисел.

счётчик = 0

пока не введён 0:

если введено число > 0 то

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

нужен счётчик
счётчик увеличивается если число > 0
нужен цикл
это цикл с условием (число шагов неизвестно)

Какой цикл?

?

Когда увеличивать � счётчик?

?

Программирование (Python), 9 класс

24 of 194

Обработка потока данных

24

count = 0

x = int(input())

while x != 0:

if x > 0:

count += 1

x = int(input())

print( count )

откуда взять x?

Что плохо?

?

Программирование (Python), 9 класс

25 of 194

Найди ошибку!

25

count = 0

x = int(input())

while x != 0:

if x > 0:

count += 1

print( count )

x = int(input())

Программирование (Python), 9 класс

26 of 194

Найди ошибку!

26

count = 0

x = int(input())

while x == 0:

if x > 0:

count += 1

x = int(input())

print( count )

count = 0

!=

Программирование (Python), 9 класс

27 of 194

Задачи

27

«A»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сколько получено чисел, которые делятся на 3.

«B»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сколько получено двузначных чисел, которые заканчиваются на 3.

Программирование (Python), 9 класс

28 of 194

Задачи

28

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

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

Программирование (Python), 9 класс

29 of 194

Обработка потока данных: сумма

29

Задача. С клавиатуры вводятся числа, ввод завершается числом 0. Найти сумму введённых чисел, оканчивающихся на цифру "5".

сумма = 0

пока не введён 0:

если число оканчивается на "5" то

сумма:= сумма + число

нужна переменная для суммы
число добавляется к сумме, если оно заканчивается на "5"
нужен цикл с условием

Как это записать?

?

if x % 10 == 5:

Программирование (Python), 9 класс

30 of 194

Обработка потока данных: сумма

30

Задача. С клавиатуры вводятся числа, ввод завершается числом 0. Найти сумму введённых чисел, оканчивающихся на цифру "5".

Sum = 0

x = int(input())

while x != 0:

if x % 10 == 5:

Sum += x

x = int(input())

print( Sum )

Чего не хватает?

?

Программирование (Python), 9 класс

31 of 194

Найди ошибку!

31

Sum = 0

x = int(input())

while x != 0:

if x % 10 == 5:

Sum += x

x = int(input())

print( Sum )

x = int(input())

Программирование (Python), 9 класс

32 of 194

Задачи

32

«A»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сумму чисел, которые делятся на 3.

«B»: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сумму двузначных чисел, которые заканчиваются на 3.

Программирование (Python), 9 класс

33 of 194

Задачи

33

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

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

Программирование (Python), 9 класс

34 of 194

"Бесконечный" цикл

34

s = 0

while True:

x = int(input())

if x == 0: break

if x % 10 == 5:

s += x

print( s )

break

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

Выход из цикла while True возможен только через� оператор break!

!

Что плохо?

?

Программирование (Python), 9 класс

35 of 194

Условия отбора

35

Положительные числа:

if x > 0: ...

Числа, делящиеся на 3:

if x % 3 == 0: ...

Числа, оканчивающиеся на 6:

if x % 10 == 6: ...

Числа, делящиеся на 3 и оканчивающиеся на 6:

if x % 3 == 0 and x % 10 == 6: ...

Двузначные числа:

if 10 <= x and x <= 99: ...

if 9 < x and x < 100: ...

Как иначе?

?

Программирование (Python), 9 класс

36 of 194

Если ни одного числа не нашли…

36

Задача: с клавиатуры вводятся числа, ввод завершается числом 0. Найти сумму введённых чисел, оканчивающихся на "5". Вывести "нет", если таких чисел нет.

сумма = 0

счётчик = 0

пока не введён 0:

если x оканчивается на "5":

сумма += x

счётчик += 1

Как определить, что таких чисел нет?

?

счётчик += 1

счётчик = 0

Как вывести результат?

?

Программирование (Python), 9 класс

37 of 194

Если ни одного числа не нашли…

37

сумма = 0

счётчик = 0

пока не введён 0:

если x оканчивается на "5":

сумма += x

счётчик += 1

if счётчик == 0:

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

else:

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

Программирование (Python), 9 класс

38 of 194

Найди ошибку!

s = 0

x = int(input())

while x != 0:

if x % 10 == 5:

k += 1

if k == 1:

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

else:

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

38

k = 0

s += x

0

s

x = int(input())

Программирование (Python), 9 класс

39 of 194

Поиск максимума (минимума)

39

Программирование (Python), 9 класс

40 of 194

Поиск максимума (минимума)

40

нужна переменная для хранения максимума
как только прочитали первое число, сохранили максимум («из одного»):

читаем следующее значение:

цикл: если новое число больше максимума, заменяем M:

выводим результат M

x = int(input())

M = x

x = int(input())

while x != 0:

if x > M: M = x

Программирование (Python), 9 класс

41 of 194

Поиск максимума (минимума)

41

x = int(input())

M = x

while x != 0:

if x > M: M = x

print(M)

x = int(input())

Что плохо?

?

Программирование (Python), 9 класс

42 of 194

Поиск максимума (минимума) – II

42

x = int(input())

M = x

while True:

x = int(input())

if x == 0: break

if x > M: M = x

print(M)

Что плохо?

?

print(M)

Программирование (Python), 9 класс

43 of 194

Максимум не из всех

43

Задача: с клавиатуры вводятся числа в диапазоне [-100;100], ввод завершается числом 0. Найти наибольшее среди чётных чисел. Вывести "нет", если таких чисел нет.

x = int(input())

M = x

while x != 0:

if x % 2 == 0 and x > M:

M = x

x = int(input())

print(M)

Что плохо?

?

???

Может быть, что �x нечётное!

Программирование (Python), 9 класс

44 of 194

Минимум не из всех

44

По условию: x ∈ [-100;100]

x = int(input())

M = -1000

while x != 0:

if x % 2 == 0 and x > M:

M = x

x = int(input())

if M == -1000:

print("Нет таких чисел")

else:

print(M)

-1000

Любое x больше этого числа!

Как определить, что � ни одного числа не � нашли?

?

Как искать минимум?

?

Программирование (Python), 9 класс

45 of 194

Если диапазон неизвестен…

45

x = int(input())

M = 1 # любое нечётное

while x != 0:

if x % 2 == 0:

if M % 2 == 1 or x > M:

M = x

x = int(input())

if M == 1 :

print("Нет таких чисел")

else:

print(M)

M == 1

новый максимум

Когда не нашли?

?

Программирование (Python), 9 класс

46 of 194

Задачи

46

«A»: с клавиатуры вводятся числа, ввод завершается числом 0. Определить минимальное и максимальное из введённых чисел.

Пример:

5

13

34

15

0

Минимум: 5

Максимум: 34

Программирование (Python), 9 класс

47 of 194

Задачи

47

«B»: с клавиатуры вводятся числа, ввод завершается числом 0. Определить минимальное и максимальное из тех введённых чисел, которые делятся на 3. Вывести "нет", если таких чисел нет.

Пример:

5

31

18

21

15

0

Минимум: 15

Максимум: 21

Пример:

5

34

17

41

11

0

Ответ: нет

Программирование (Python), 9 класс

48 of 194

Задачи

48

«C»: с клавиатуры вводятся числа, ввод завершается числом 0. Определить минимальное и максимальное из тех введённых двузначных натуральных чисел, которые оканчиваются на 6. Вывести "нет", если таких чисел нет.

Пример:

6

36

18

26

15

0

Минимум: 26

Максимум: 36

Пример:

6

32

176

41

11

0

Ответ: нет

Программирование (Python), 9 класс

49 of 194

Задачи

49

«D»: с клавиатуры вводятся числа, ввод завершается числом 0. Определить минимальное из введённых чисел Фибоначчи. Вывести "нет", если чисел Фибоначчи в последовательности нет.

Числа Фибоначчи – это последовательность чисел, которая начинается с двух единиц и каждое следующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, …

Пример:

5

36

12

26

13

0

Ответ: 5

Пример:

6

32

176

41

11

0

Ответ: нет

Программирование (Python), 9 класс

50 of 194

Обработка потока данных (N чисел)

50

Задача: с клавиатуры вводится число N, а �затем – N целых чисел. Определить, сколько было введено положительных чисел.

ввести N

счётчик = 0

сделай N раз:

ввести число

если введено число > 0:

счётчик += 1

вывести счётчик

В чём отличие?

?

задано количество!

в Python нет такого!

Есть цикл for!

!

Программирование (Python), 9 класс

51 of 194

Обработка потока данных (N чисел)

51

сделай N раз:

...

for i in range(4):

print(i)

range(N) = [0, 1, 2, …, N-2, N-1 ]

!

N-1

N раз

0

1

2

3

s = 0

for i in range(4):

s += i

print(s)

6

for i in range(N):

...

Что выведет?

?

Программирование (Python), 9 класс

52 of 194

Обработка потока данных (N чисел)

52

N = int(input())

k = 0

for i in range(N):

x = int(input())

if x > 0: k += 1

print(k)

сделай N раз!

Числа, делящиеся на 3:

if x % 3 == 0: k += 1

Числа, оканчивающиеся на 6:

if x % 10 == 6: k += 1

Числа, делящиеся на 3 и оканчивающиеся на 6:

if x % 3 == 0 and x % 10 == 6: k += 1

Программирование (Python), 9 класс

53 of 194

Задачи

53

«A»: с клавиатуры вводится число N, а затем – N целых чисел. Определить, сколько было введено положительных и сколько отрицательных чисел (нули не считать!).

Пример:

5

1

3

-34

15

0

Положительных: 3

Отрицательных: 1

Программирование (Python), 9 класс

54 of 194

Задачи

54

«B»: с клавиатуры вводится число N, а затем – N целых чисел. Определить сумму двузначных чисел (как положительных, так и отрицательных). Если двузначных чисел не было, вывести "нет".

Пример:

5

1

13

-34

5

31

Ответ: 10

Пример:

5

1

213

-134

5

3

Ответ: нет

Программирование (Python), 9 класс

55 of 194

Задачи

55

«C»: с клавиатуры вводится число N, а затем – N целых чисел. Определить минимальное и максимальное среди двузначных чисел, которые делятся на 3. Если таких чисел не было, вывести "нет".

Пример:

5

18

33

98

513

31

Минимум: 18

Максимум: 33

Пример:

5

1

-18

-6

-21

32

Минимум: -21 Максимум: -18

Пример:

5

1

23

132

6

32

Ответ: нет

Программирование (Python), 9 класс

56 of 194

Задачи

56

«D»: с клавиатуры вводится число N, а затем – N натуральных чисел. Определить минимальное и максимальное среди простых чисел (которые делятся на сами не себя и на 1). Если таких чисел не было, вывести "нет".

Пример:

5

41

15

11

163

39

Минимум: 11

Максимум: 163

Пример:

5

12

25

132

6

39

Ответ: нет

Программирование (Python), 9 класс

57 of 194

Программирование (Python)

Массивы (повторение)

57

58 of 194

Обращение к элементу массива

58

5	10	15	20	25

0	1	2	3	4

A

массив

2

15

НОМЕР �элемента массива

(ИНДЕКС)

A[0]

A[1]

A[2]

A[3]

A[4]

ЗНАЧЕНИЕ элемента массива

Нумерация с нуля!

!

Индекс элемента — это значение, которое указывает на конкретный элемент массива.

Программирование (Python), 9 класс

59 of 194

Создание массива

59

A = [11, 22, 35, 41, 53]

11	22	35	41	53

A = [11, 22] + [35, 41] + [53]

11	11	11	11	11

A = [11]*5

A = [11] + [11] + [11] + [11] +[11]

Программирование (Python), 9 класс

60 of 194

Обращение к элементу массива

60

23	12	7	43	51

0	1	2	3	4

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

A[2]

ИНДЕКС элемента массива: 2

ЗНАЧЕНИЕ элемента массива

Программирование (Python), 9 класс

61 of 194

Что неверно?

61

A = [1, 2, 3, 4, 5]

x = 1

print( A[x-8] )

A[x+4] = A[x-1] + A[2*x]

print( A[-7] )

A[5] = A[0] + A[2]

Что плохо?

?

Выход за границы массива — это обращение к элементу с индексом, который не существует в массиве.

1	2	3	4	5

0	1	2	3	4

Программирование (Python), 9 класс

62 of 194

Перебор элементов массива

62

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

N = 10

A = [0]*N # память уже выделена

for i in range(N):

# здесь работаем с A[i]

0, 1, 2, 3, …, N-1

Программирование (Python), 9 класс

63 of 194

Заполнение массива

63

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

N-1

Что произойдёт?

?

[0, 1, 2, 3, …, N-1]

В стиле Python:

A = [ i for i in range(N) ]

i

Программирование (Python), 9 класс

64 of 194

Заполнение массива в обратном порядке

X = N

64

N	…	3	2	1

A[0] = N

A[1] = N-1

A[2] = N-2

...

A[N-1] = 1

for i in range(N):

A[i] = X

X = X - 1

Как меняется X?

?

X = N, N-1, …, 2, 1

начальное значение

уменьшение на 1

Программирование (Python), 9 класс

65 of 194

Заполнение массива в обратном порядке

65

N	…	3	2	1

A[i] = X

Как связаны i и X?

?

i	X
0	N
1	N-1
2	N-2
...	...
N-1	1

–1

+1

Сумма i и X не меняется!

!

i + X = N

X = N - i

for i in range(N):

A[i] = N – i

В стиле Python:

A = [ N-i

for i in range(N) ]

Программирование (Python), 9 класс

66 of 194

Вывод массива на экран

66

for i in range(N):

print( A[i] )

Как вывести � в строчку?

?

или так:

в столбик

Весь массив сразу:

print( A )

[1,2,3,4,5]

По одному элементу:

for x in A:

print( x )

для всех элементов в массиве A

for x in A:

print( x, end=" " )

пробел между элементами

Программирование (Python), 9 класс

67 of 194

Вывод массива на экран (Python)

67

print ( *A )

разбить список на элементы

print (1, 2, 3, 4, 5)

[1,2,3,4,5]

1 2 3 4 5

Программирование (Python), 9 класс

68 of 194

Задачи

68

«A»: а) Заполните все элементы массива из 10 элементов значением X , введённым с клавиатуры.

б) Заполните массив из 10 элементов последовательными натуральными числами, начиная с X (значение X введите с клавиатуры).

«B»: а) Заполните массив из 10 элементов натуральными числами в порядке убывания. С клавиатуры вводится значение X. Последний элемент должен быть равен X, предпоследний равен X+1 и т.д.

б) Заполните массив из 10 элементов степенями числа 2 (от 2¹ до 2^N), так чтобы первый элемент был равен 2, следующий – 4, следующий – 8 и т.д.

Программирование (Python), 9 класс

69 of 194

Задачи

69

«C»: а) Заполните массив из 10 элементов степенями числа 2, начиная с конца, так чтобы последний элемент массива был равен 1, а каждый предыдущий был в 2 раза больше следующего.

б) С клавиатуры вводится целое число X. Заполните массив из 11 элементов целыми числами, так чтобы средний элемент массива был равен X, слева от него элементы стояли по возрастанию, а справа – по убыванию. Соседние элементы отличаются на единицу. Например, �при X = 3 массив из 5 элементов заполняется так: 1 2 3 2 1.

Программирование (Python), 9 класс

70 of 194

Заполнение случайными числами

70

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

из библиотеки (модуля) random

взять функцию randint

Программирование (Python), 9 класс

71 of 194

Обработка элементов массива

71

N = 10

A = [0]*N # память уже выделена

for i in range(N):

# здесь работаем с A[i]

Вывести на экран в столбик:

for i in range(N):

???

Что вместо «???»?

!

print( A[i] )

Вывести на экран в строчку:

for i in range(N):

???

print( A[i], end = " " )

print( *A )

Программирование (Python), 9 класс

72 of 194

Обработка элементов массива

for i in range(N):

???

for i in range(N):

???

72

Вывести числа, на 1 большие, чем A[i]:

Что вместо «???»?

!

print( A[i]%10 )

Вывести последние цифры:

print( A[i]+1 )

Программирование (Python), 9 класс

73 of 194

Обработка элементов массива

73

Увеличить на 1:

for i in range(N):

???

Что вместо «???»?

!

A[i] += 1

Умножить на 2:

for i in range(N):

???

A[i] *= 2

Заполнить нулями:

for i in range(N):

???

A[i] = 0

Программирование (Python), 9 класс

74 of 194

Задачи-2

74

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

Пример:

Массив: 5 6 2 3 1 4 8 7

Квадраты: 25 36 4 9 1 16 64 49

«B»: Напишите программу, которая заполняет массив из 10 элементов случайными числами в диапазоне [100,300] и выводит его на экран. После этого на экран выводятся средние цифры (число десятков) всех чисел, записанных в массив.

Пример:

Массив: 142 324 135 257 167 295 126 223 138 270

Число десятков: 4 2 3 5 6 9 2 2 3 7

Программирование (Python), 9 класс

75 of 194

Задачи-2

75

«C»: Напишите программу, которая заполняет массив из �10 элементов случайными числами в диапазоне [100,500] и выводит его на экран. После этого на экран выводятся суммы цифр всех чисел, записанных в массив.

Пример:

Массив: 162 425 340 128 278 195 326 414 312 177

Суммы цифр: 9 11 7 11 17 15 11 9 6 15

Программирование (Python), 9 класс

76 of 194

Сумма элементов массива

76

Sum = 0

for i in range(N):

Sum = Sum + A[i]

print( Sum )

Задача. Найти сумму элементов массива из N элементов.

Какие переменные � нужны?

?

i	Sum
	0

5	2	8	3	1

0

5

1

7

2

15

3

18

4

19

Sum += A[i]

В стиле Python:

print( sum(A) )

Программирование (Python), 9 класс

77 of 194

Сумма элементов массива (Python)

77

Sum = 0

for x in A:

Sum += x

print( Sum )

Задача. Найти сумму элементов массива A.

или так:

print( sum(A) )

Не нужно знать размер!

!

for x in A:

для всех элементов из A

встроенная функция

Программирование (Python), 9 класс

78 of 194

Сумма не всех элементов массива

78

Sum = 0

for i in range(N):

Sum += A[i]

print( Sum )

Задача. Найти сумму чётных элементов массива.

Что делаем с нечётными?

?

if A[i] % 2 == 0:

Sum += A[i]

print( Sum )

if A[i] % 2 == 0:

Программирование (Python), 9 класс

79 of 194

Сумма не всех элементов массива

79

Sum = 0

for x in A:

Sum += x

print( Sum )

Задача. Найти сумму чётных элементов массива.

if x % 2 == 0:

Sum += x

print( Sum )

4	3	6	8	1

A

x

Sum

4

3

6

8

1

0

4

10

18

В стиле Python:

B = [x for x in A

if x % 2 == 0]

print ( sum(B) )

отбираем в новый массив все нужные значения

Программирование (Python), 9 класс

80 of 194

Задачи

80

«A»: Напишите программу, которая заполняет массив из 10 элементов случайными числами на отрезке [–5; 5] и находит сумму положительных элементов.

«B»: Напишите программу, которая заполняет массив из 10 элементов случайными числами на отрезке [–2; 2] и находит произведение ненулевых элементов.

«C»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке �[100; 1000] и находит отдельно сумму элементов в первой и во второй половинах массива.

Программирование (Python), 9 класс

81 of 194

Подсчёт элементов по условию

81

Задача. Найти количество чётных элементов массива.

Какие переменные нужны?

?

count = 0

for i in range(N):

if A[i] % 2 == 0:

count += 1

print( count )

Что тут делаем?

?

переменная-счётчик

Программирование (Python), 9 класс

82 of 194

Подсчёт элементов по условию (Python)

82

Задача. Найти количество чётных элементов массива.

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

размер массива

Программирование (Python), 9 класс

83 of 194

Среднее арифметическое

83

Задача. Найти среднее арифметическое элементов массива, которые больше 180 (рост в см).

Sum = 0

for x in A:

if x > 180:

Sum += x

print( Sum/N )

Что плохо?

?

Программирование (Python), 9 класс

84 of 194

Среднее арифметическое

84

Задача. Найти среднее арифметическое элементов массива, которые больше 180 (рост в см).

Какие переменные нужны?

?

Sum = 0

count = 0

for x in A:

if x > 180:

count += 1

Sum += x

print( Sum/count )

Что тут делаем?

?

Программирование (Python), 9 класс

85 of 194

Среднее арифметическое (Python)

85

Задача. Найти среднее арифметическое элементов массива, которые больше 180 (рост в см).

B = [ x for x in A

if x > 180]

print ( sum(B)/len(B) )

отбираем нужные

Программирование (Python), 9 класс

86 of 194

Задачи

86

«A»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [0; 200] и считает число элементов, которые делятся на 10.

«B»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [0; 200] и считает число двузначных чисел в массиве.

«C»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [10; 100] и считает число пар соседних элементов, сумма которых делится на 3.

Программирование (Python), 9 класс

87 of 194

Перестановка элементов массива

87

Как поменять местами значения двух � переменных a и b?

?

с = a

a = b

b = c

вспомогательная переменная

элементы массива:

с = A[i]

A[i] = A[k]

A[k] = c

Программирование (Python), 9 класс

88 of 194

Перестановка пар соседних элементов

88

Задача. Массив A содержит чётное количество элементов N. Нужно поменять местами пары соседних элементов: 0-й с 1-м, 2-й — с 3-м и т. д.

0	1	2	3		N-2	N-1
7	12	38	5	…	40	23

0	1	2	3		N-2	N-1
12	7	5	38	…	23	40

Программирование (Python), 9 класс

89 of 194

Перестановка пар соседних элементов

89

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

?

выход за границы массива

Программирование (Python), 9 класс

90 of 194

Перестановка пар соседних элементов

90

for i in range(0,N-1,2):

# переставляем A[i] и A[i+1]

с = A[i]

A[i] = A[i+1]

A[i+1] = c

A[0]↔A[1]

A[2]↔A[3]

...

A[N-2]↔A[N-1]

range(0,N-1,2):

Программирование (Python), 9 класс

91 of 194

Реверс массива

91

0	1	2		N-3	N-2	N-1
7	12	5	…	38	40	23

0	1	2		N-3	N-2	N-1
23	40	38	…	5	12	7

Задача. Переставить элементы массива в обратном порядке (выполнить реверс).

A[0]↔A[N-1]

A[1]↔A[N-2]

A[i]↔A[N-1-i]

A[N-1]↔A[0]

0+N-1 = N-1

1+N-2 = N-1

i+??? = N-1

N-1+0 = N-1

Программирование (Python), 9 класс

92 of 194

Реверс массива

92

for i in range(N):

поменять местами A[i] и A[N-1-i]

Что плохо?

?

0	1	2	3
7	12	40	23

23	12	40	7

23	40	12	7

23	12	40	7

7	12	40	23

i=0

i=1

i=2

i=3

Как исправить?

?

(N // 2):

Программирование (Python), 9 класс

93 of 194

Задачи

93

«A»: Заполнить массив из 10 элементов случайными числами в диапазоне [0; 100], поменять местами пары соседних элементов, не трогая первый и последний элементы.

Массив: 53 66 88 39 26 88 35 24 38 50

Результат: 53 88 66 26 39 35 88 38 24 50

«B»: Заполнить массив из 10 элементов случайными числами в диапазоне [0; 100] и выполнить циклический сдвиг влево: каждый элемент перемещается на место предыдущего, а первый – на место последнего.

Массив: 53 66 88 39 26 88 35 24 38 50

Результат: 66 88 39 26 88 35 24 38 50 53

Программирование (Python), 9 класс

94 of 194

Задачи

94

«C»: Заполнить массив из 10 элементов случайными числами в диапазоне [0; 100], сделать реверс отдельно в первой и во второй половине массива.

Массив: 53 66 88 39 26 88 35 24 38 50

Результат: 26 39 88 66 53 50 38 24 35 88

Программирование (Python), 9 класс

95 of 194

Линейный поиск в массиве

95

Задача. Найти в массиве элемент, равный X, и его номер.

0	1	2	3	4	5
7	12	38	5	40	23

X = 5

5

i = 0

while A[i]!=X:

i += 1

print("A[", i, "]=", X)

Что плохо?

?

Нельзя выходить за границы массива!

!

Если искать 4?

?

Программирование (Python), 9 класс

96 of 194

Линейный поиск в массиве

96

i = 0

while i<=N and A[i]!=X:

i += 1

if i < N:

print( "A[",i,"]=",X )

else:

print( "Не нашли!" )

i< N

Как проверить, нашли � или нет?

?

не выходим за границу

Программирование (Python), 9 класс

97 of 194

Досрочный выход из цикла

97

Задача. Найти в массиве элемент, равный X, и его номер.

nX = -1 # номер элемента

for i in range(N):

if A[i]==X:

nX = i # запомнить номер

break

if nX >= 0:

print( "A[", nX, "]=", X )

else:

print( "Не нашли!" )

нашли!

break

сразу выйти из цикла

Программирование (Python), 9 класс

98 of 194

Поиск в массиве

for i in range ( N ):

if A[i] == X:

print ( "A[", i, "]=", X, sep = "" )

break

else:

print ( "Не нашли!" )

98

Варианты в стиле Python:

если не было досрочного выхода из цикла

if X in A:

nX = A.index(X)

print ( "A[", nX, "]=", X, sep = "" )

else:

print ( "Не нашли!" )

Программирование (Python), 9 класс

99 of 194

Задачи

99

«A»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [0,20], выводит его на экран, а затем находит индекс первого элемента, равного введённому числу X. Программа должна вывести ответ «не найден», если в массиве таких элементов нет.

Пример:

Массив: 5 16 2 13 3 14 18 13 16 9

Что ищем: 13

A[3] = 13

Программирование (Python), 9 класс

100 of 194

Задачи

100

«B»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [-5,5], выводит его на экран, а затем находит индекс последнего элемента, равного введённому числу X. Программа должна вывести ответ «не найден», если в массиве таких элементов нет.

Пример:

Массив: -5 -6 2 3 -3 0 8 -3 0 9

Что ищем: 0

A[8] = 0

Программирование (Python), 9 класс

101 of 194

Задачи

101

«C»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [10,15], выводит его на экран, а затем находит индексы всех элементов, равных введённому числу X. Программа должна вывести ответ «не найден», если в массиве таких элементов нет.

Пример:

Массив: 12 15 10 13 13 15 10 14 12 13

Что ищем: 12

A[0] = 12

A[8] = 12

Программирование (Python), 9 класс

102 of 194

Поиск максимального элемента

102

Программирование (Python), 9 класс

103 of 194

Поиск максимального элемента

103

Какие переменные нужны?

?

for i in range(N):

if A[i] > M:

M = A[i]

print( M )

Чего не хватает?

?

Какое начальное � значение взять для M?

?

M – значение, которое заведомо меньше всех элементов массива�или
M = A[0] (или любой другой элемент)

максимальный не меньше, чем A[0]

Программирование (Python), 9 класс

104 of 194

Поиск максимального элемента

104

M = A[0]

for i in range(1,N):

if A[i] > M:

M = A[i]

print( M )

начинаем с A[1], так как A[0] мы уже посмотрели

Как найти минимальный?

?

Программирование (Python), 9 класс

105 of 194

Поиск максимального элемента (Python)

105

M = A[0]

for x in A:

if x > M:

M = x

print( M )

перебрать все элементы в массиве A

for x in A:

Не нужно знать размер!

!

print( max(A) )

print( min(A) )

Программирование (Python), 9 класс

106 of 194

Номер максимального элемента

106

Задача. Найти в массиве максимальный элемент и его номер.

Какие переменные нужны?

?

M = A[0]; nMax = 0

for i in range(1,N):

if A[i] > M:

M = A[i]

nMax = i

print( "A[", nMax, "]=", M )

nMax = 0

nMax = i

Можно ли убрать одну � переменную?

?

Программирование (Python), 9 класс

107 of 194

Номер максимального элемента

107

M = A[0]; nMax = 0

for i in range(1,N):

if A[i]> M :

M = A[i]

nMax = i

print( "A[", nMax, "]=", M )

Если знаем nMax, то M=A[nMax]!

!

:

A[nMax]

)

A[nMax]

Программирование (Python), 9 класс

108 of 194

Максимальный элемент и его номер

108

M = max(A)

nMax = A.index(M)

print ( "A[", nMax, "]=", M )

Вариант в стиле Python:

номер заданного элемента (первого из…)

Программирование (Python), 9 класс

109 of 194

Максимальный не из всех

109

Задача. Найти в массиве максимальный из отрицательных элементов.

M = A[0]

for i in range(1,N):

if A[i]<0 and A[i]>M:

M = A[i]

print( M )

Что плохо?

?

0	1	2	3	4
5	–2	8	3	–1

M = 5

Как исправить?

?

Программирование (Python), 9 класс

110 of 194

Максимальный не из всех

110

Задача. Найти в массиве максимальный из отрицательных элементов.

M = A[0]

for i in range(1,N):

if A[i] < 0:

if M >= 0 or A[i]> M:

M = A[i]

print( M )

Если нет отрицательных?

?

M >= 0

сначала записали неотрицательный!

Программирование (Python), 9 класс

111 of 194

Максимальный не из всех (Python)

111

Задача. Найти в массиве максимальный из отрицательных элементов.

B = [ x for x in A

if x < 0]

print( max(B) )

отбираем нужные

if len(B):

print( max(B) )

else:

print("Нет таких!")

if len(B)!= 0:

Если нет отрицательных?

?

Программирование (Python), 9 класс

112 of 194

Задачи (без min и max)

112

«A»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [50; 150] и находит в нём минимальный и максимальный элементы и их номера.

«B»: Напишите программу, которая заполняет массив из 10 элементов в виде

A = [ 10, 2, 3, 4, 5, 10, 7, 8, 9, 10]

и выводит количество элементов, имеющих максимальное значение.

«C»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [100; 200] и находит в нём пару соседних элементов, сумма которых минимальна.

Программирование (Python), 9 класс

113 of 194

Задачи

113

«D»: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [–100; 100] и находит в каждой половине массива пару соседних элементов, сумма которых максимальна.

Программирование (Python), 9 класс

114 of 194

Задачи-2 (максимум в потоке)

114

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

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

«C»: На вход программы поступает неизвестное количество чисел целых, ввод заканчивается нулём. Напишите программу, которая находит максимальное двузначное число, заканчивающееся на 6, среди полученных чисел. Если такого числа нет, нужно вывести слово «Нет».

Программирование (Python), 9 класс

115 of 194

Задачи-2 (максимум в потоке)

115

«D»: На вход программы поступает неизвестное количество целых чисел (не менее 2), ввод заканчивается нулём. Напишите программу, которая находит среди полученных чисел пару полученных друг за другом чисел, сумма которых максимальна.

Программирование (Python), 9 класс

116 of 194

Сортировка

116

Сортировка — это расстановка элементов списка (массива) в заданном порядке.

Задача. Отсортировать элементы в порядке возрастания (неубывания – если есть одинаковые).

Алгоритмы сортировки:

простые, но медленные (при больших N)
быстрые, но сложные…

Программирование (Python), 9 класс

117 of 194

Сортировка выбором

117

Где должен стоять минимальный элемент?

?

нашли минимальный, поставили его на первое место

из оставшихся нашли минимальный, поставили его на второе место и т.д.

с = A[nMin]

A[nMin] = A[0]

A[0] = c

Как?

?

5	–2	8	3	–1

–2	5	8	3	–1

–2	–1	8	3	5

A[0],A[nMin] = A[nMin],A[0]

Что дальше?

?

Программирование (Python), 9 класс

118 of 194

Сортировка выбором

118

for i in range(N-1):

# ищем минимальный среди A[i]..A[N-1]

nMin = i

for j in range(i+1,N):

if A[j] < A[nMin]:

nMin = j

# переставляем A[i] и A[nMin]

A[i],A[nMin] = A[nMin],A[i]

не трогаем те, которые уже поставлены

Почему цикл N-1 раз?

?

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

A.sort()

Программирование (Python), 9 класс

119 of 194

Задачи

119

«A»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [0,20] и сортирует его в порядке убывания.

Пример:

Массив: 5 16 2 13 3 14 18 13 16 9

Сортировка: 18 16 16 14 13 13 9 5 3 2

«B»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [10,100] и сортирует его по возрастанию последней цифры числа (сначала идут все числа, которые заканчиваются на 0, потом все, которые заканчиваются на 1, и т.д.).

Пример:

Массив: 12 10 31 40 55 63 28 87 52 92

Сортировка: 10 40 31 12 52 92 63 55 87 28

Программирование (Python), 9 класс

120 of 194

Задачи

120

«C»: Напишите программу, которая заполняет массив из N = 10 элементов случайными числами в диапазоне [0,20] и сортирует его в порядке возрастания. На каждом шаге цикла выполняется поиск максимального (а не минимального!) элемента.

Пример:

Массив: 5 16 2 13 3 14 18 13 16 9

Сортировка: 2 3 5 9 13 13 14 16 16 18

Программирование (Python), 9 класс

121 of 194

Программирование (Python)

§ 21. Матрицы (двумерные массивы)

121

122 of 194

Что такое матрица?

122

	0	1	2
0	-1	0	1
1	-1	0	1
2	0	1	-1

Как закодировать?

?

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

нет знака

нолик

крестик

строка 2, столбец 3

Каждый элемент матрицы имеет два индекса – номера строки и столбца.

Программирование (Python), 9 класс

123 of 194

Создание матриц

123

A = [[-1, 0, 1],

[-1, 0, 1],

[0, 1, -1]]

Матрица – это массив масивов!

!

перенос на другую строку внутри скобок

A = [[-1, 0, 1], [-1, 0, 1], [0, 1, -1]]

или так:

Нумерация элементов с нуля!

!

Программирование (Python), 9 класс

124 of 194

Создание матриц

124

N = 3

M = 2

row = [0]*M

A = [row]*N

Нулевая матрица:

0
1
2

0	0

row

A

A[0][0] = 1

1

а правильно так:

A = []

for i in range(N):

A.append ( [0]*M )

0
1
2

0	0

A

A[0][0] = 1

0	0

0	0

1

Программирование (Python), 9 класс

125 of 194

Вывод матриц

125

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 2 3

4 5 6

7 8 9

Зачем форматный вывод?

?

Программирование (Python), 9 класс

126 of 194

Простые алгоритмы

126

Заполнение случайными числами:

from random import randint

for i in range(N):

for j in range(M):

A[i][j] = 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 )

Программирование (Python), 9 класс

127 of 194

Перебор элементов матрицы

127

Главная диагональ:

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]

Программирование (Python), 9 класс

128 of 194

Перестановка строк

128

2-я и 4-я строки:

for j in range(M):

c = A[2][j]

A[2][j] = A[4][j]

A[4][j] = c

	0	1	2	3	4	5
0
1
2
3
4
5

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

A[2], A[4] = A[4], A[2]

0
1
2
3
4
5

A[2][j],A[4][j] = A[4][j],A[2][j]

Программирование (Python), 9 класс

129 of 194

Перестановка столбцов

129

2-й и 4-й столбцы:

for i in range(N):

c = A[i][2]

A[i][2] = A[i][4]

A[i][4] = c

	0	1	2	3	4	5
0
1
2
3
4
5

A[i][2],A[i][4] = A[i][4],A[i][2]

Программирование (Python), 9 класс

130 of 194

Задачи

130

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

Пример:

Матрица А:

12 34 14 65

71 88 23 45

87 46 53 39

76 58 24 92

Результат: A[3][3] = 92

Программирование (Python), 9 класс

131 of 194

Задачи

131

«B»: Напишите программу, которая заполняет матрицу случайными числами в диапазоне [10; 100] и находит максимальный элемент матрицы и его индексы (номера строки и столбца).

Пример:

Матрица А:

12 34 14 65

71 88 23 98

87 46 53 39

76 58 24 92

Максимум: A[1][3] = 98

Программирование (Python), 9 класс

132 of 194

Задачи

132

«C»: Напишите программу, которая заполняет матрицу случайными числами в диапазоне [-50; 50] и находит минимальный из чётных положительных элементов матрицы. Учтите, что таких элементов в матрице может и не быть.

Пример:

Матрица А:

16 34 14 65

71 88 23 45

87 12 53 39

76 58 24 92

Результат: A[2][1] = 12

Программирование (Python), 9 класс

133 of 194

Программирование (Python)

§ 22. Сложность алгоритмов

133

134 of 194

Как сравнивать алгоритмы?

134

быстродействие (временна́я сложность)
объём требуемой памяти (пространственная сложность)
понятность

Обычно не бывает все хорошо!

!

Время работы алгоритма – это количество элементарных операций T, выполненных исполнителем.

зависит от количества данных (размера массива N)

Функция T(N) называется

временно́й сложностью алгоритма

T(N) = 2N³

Как увеличится время работы � при увеличении N в 10 раз?

?

Программирование (Python), 9 класс

135 of 194

Примеры определения сложности

135

Задача 1. Вычислить сумму первых трёх элементов массива (при N ≥ 3).

Sum = A[0] + A[1] + A[2]

T(N) = 3

2 сложения + запись в память

Задача 2. Вычислить сумму всех элементов массива.

Sum = 0

for i in range(N):

Sum += A[i]

T(N) = 2N + 1

N сложений, N+1 операций записи

Программирование (Python), 9 класс

136 of 194

Примеры определения сложности

136

Задача 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]

Число сравнений:

Число перестановок: T_n(N) = N – 1

Программирование (Python), 9 класс

137 of 194

Примеры определения сложности

137

Задача 4. Найти сумму элементов квадратной матрицы размером N×N.

Sum = 0

for i in range(N):

for j in range(N):

Sum += A[i][j]

Самостоятельно! ☺

!

Программирование (Python), 9 класс

138 of 194

Сравнение алгоритмов по сложности

138

Какой алгоритм выбрать?

?

0

100

при N < 100:

при N > 100:

Нужно знать размер данных!

!

Программирование (Python), 9 класс

139 of 194

Асимптотическая сложность

139

Асимптотическая сложность – это оценка скорости роста количества операций при больших значениях N.

сложность O(N) ⇔ T(N) ≤ c⋅ N для N ≥ N₀

линейная

сумма элементов массива:

T(N) = 2⋅ N – 1 ≤ 2⋅ N для N ≥ 1 ⇒ O(N)

сложность O(1) ⇔ T(N) ≤ c для N ≥ N₀

не зависит от N

постоянная

T(N) = 100 ≤ 101 для всех N≥ 1 ⇒ O(1)

Программирование (Python), 9 класс

140 of 194

Асимптотическая сложность

140

сложность O(N²) ⇔ T(N) ≤ c⋅ N² для N ≥ N₀

квадратичная

сортировка методом выбора:

для N ≥ 0 ⇒ O(N²)

сложность O(N³) ⇔ T(N) ≤ c⋅ N³ для N ≥ N₀

кубичная

Программирование (Python), 9 класс

141 of 194

Асимптотическая сложность

141

сложность O(2^N)

сложность O(N!)

задачи оптимизации, полный перебор вариантов

Факториал числа N: N ! = 1 ⋅ 2 ⋅ 3 … ⋅ N

T(N)	время выполнения
N	100 нс
N ²	10 мс
N ³	0,001 с
2 ^N	10¹³ лет
N!	10¹⁴¹ лет

N = 100,

1 млрд оп/с

Программирование (Python), 9 класс

142 of 194

Асимптотическая сложность

142

Алгоритм относится к классу �O( f(N) ), если найдется такая постоянная c, что начиная с некоторого N = N₀ выполняется условие

T(N) ≤ c⋅ f (N)

0

это верхняя оценка!

O( N ) ⇒ O( N² ) ⇒ O( N³ ) ⇒ O( 2^N )

«Алгоритм имеет сложность O(N²)».

обычно – наиболее точная верхняя оценка!

Программирование (Python), 9 класс

143 of 194

Программирование (Python)

§ 23. Как разрабатывают программы

143

144 of 194

Этапы разработки программ

144

I. Постановка задачи

Документ: техническое задание.

II. Построение модели

Формализация: запись модели в виде формул (на формальном языке).

модель

исходные данные

результаты

III. Разработка алгоритма и способа � хранения данных

«Алгоритмы + структуры данных = программы»

(Н. Вирт)

Программирование (Python), 9 класс

145 of 194

Этапы разработки программ

145

IV. Кодирование

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

кодирование

алгоритм

программный код

V. Отладка

Поиск и исправление ошибок в программах:

синтаксические – нарушение правил языка программирования
логические – ошибки в алгоритме

могут приводить к отказам – аварийным ситуациям во время выполнения (run-time error)

Программирование (Python), 9 класс

146 of 194

Этапы разработки программ

146

VI. Тестирование

Тщательная проверка программы во всех режимах:

альфа-тестирование – внутри компании (тестировщики)
бета-тестирование – (доверенные) пользователи

VII. Документирование

Технические писатели

VIII. Внедрение и сопровождение

обучение пользователей
исправление найденных ошибок
техподдержка

Программирование (Python), 9 класс

147 of 194

Методы проектирования программ

147

«Сверху вниз» (последовательное уточнение)

Задача

30-40 строк каждая

Программирование (Python), 9 класс

148 of 194

Методы проектирования программ

148

«Сверху вниз» (последовательное уточнение)

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

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

Программирование (Python), 9 класс

149 of 194

Методы проектирования программ

149

«Снизу вверх» (восходящее)

Задача

библиотека функций

Программирование (Python), 9 класс

150 of 194

Методы проектирования программ

150

«Снизу вверх» (восходящее)

нет дублирования
сразу видно быстродействие

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

Почти всегда используют оба подхода!

!

Программирование (Python), 9 класс

151 of 194

Отладка программы

151

from math import sqrt

print("Введите a, b, c: ")

a = float(input())

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="")

Программа решения квадратного уравнения

float – преобразовать в вещественное число

Программирование (Python), 9 класс

152 of 194

Тестирование

152

Тест 1. a = 1, b = 2, c = 1.

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

Ожидание:

Найден вариант, когда программа работает неверно. Ошибка воспроизводится!

Возможные причины:

неверный ввод данных
неверное вычисление дискриминанта
неверное вычисление корней
неверный вывод результатов

Программирование (Python), 9 класс

153 of 194

Отладочная печать

153

a = float(input())

b = float(input())

c = float(input())

print(a, b, c)

D = b*b - 4*a*a

print("D=", D)

...

print(a, b, c)

print("D=", D)

Идея: выводить все промежуточные результаты.

Программирование (Python), 9 класс

154 of 194

Отладочная печать

154

Введите a, b, c:

1

-5

6

1.0 -5.0 6.0

D= 21.0

Результат:

D= 21.0

D = b*b - 4*a* с ;

с

Идея: выводить все промежуточные результаты.

Одна ошибка найдена!

!

Программирование (Python), 9 класс

155 of 194

Отладка программы

155

Тест 1. a = 1, b = 2, c = 1.

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

x2 = (-b-sqrt(D))/2*a

(2*a)

Что неверно?

?

Программирование (Python), 9 класс

156 of 194

Документирование программы

156

назначение программы
формат входных данных
формат выходных данных
примеры использования программы

Назначение: �программа для решения уравнения

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

Программирование (Python), 9 класс

157 of 194

Документирование программы

157

Формат выходных данных: �значения вещественных корней уравнения; если вещественных корней нет, выводится слово «нет»

Примеры использования программы: �1. Решение уравнения

Введите a, b, c: 1 -5 6

x1=3 x2=2

2. Решение уравнения

Введите a, b, c: 1 1 6

Нет.

Программирование (Python), 9 класс

158 of 194

Программирование (Python)

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

158

159 of 194

Два типа подпрограмм

159

Процедуры

Функции

Подпрограммы

выполняют действия

+ возвращают некоторый

результат

Процедура или функция?

?

а) рисует окружность на экране

б) определяет площадь круга

в) вычисляет значение синуса угла

г) изменяет режим работы программы

д) возводит число x в степень y

е) включает двигатель автомобиля

ж) проверяет оставшееся количество бензина в баке

з) измеряет высоту полёта самолёта

Программирование (Python), 9 класс

160 of 194

Простая процедура

160

...

printLine()

...

Что делает?

?

какие-то операторы

def printLine():

print("----------")

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

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

define – определить

Программирование (Python), 9 класс

161 of 194

Линии разной длины

161

def printLine5():

print("-----")

def printLine10():

print("----------")

Как улучшить?

?

def printLine10():

print("-"*10)

def printLine( n ):

print("-"*n)

параметр процедуры

Программирование (Python), 9 класс

162 of 194

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

162

...

printLine(10)

...

printLine(7)

printLine(5)

printLine(3)

def printLine( n ):

...

Что делает?

?

Параметр – величина, от которой зависит работа процедуры.

Программирование (Python), 9 класс

163 of 194

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

163

def printLine(c, n):

print(c*n)

Что изменилось?

?

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

Как вызывать?

?

printLine( 5, "+" )

printLine( "+", 5 )

printLine( "+-+", 5 )

Программирование (Python), 9 класс

164 of 194

В других языках программирования

164

Паскаль:

procedure printLine(c: string; n: integer);

var i: integer;

begin

for i:=1 to n do

write(c);

writeln

end;

Программирование (Python), 9 класс

165 of 194

В других языках программирования

165

С:

void printLine(int n)

{

int i;

for (i=1; i<=n; i++)

putchar("-");

putchar("\n");

}

Программирование (Python), 9 класс

166 of 194

Как не нужно писать процедуры

166

def summa():

print(x + y)

x = 10

y = 5

summa()

Что плохо?

?

только x + y
не перенести в другую программу

def summa( x, y ):

print(x + y)

x = 10

y = 5

summa( x, y )

summa( 2*x+y, 7 )

Процедура принимает данные только � через параметры!

!

Программирование (Python), 9 класс

167 of 194

Задачи

167

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

Пример:

Длина цепочки: 7

-------

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

Пример:

Длина прямоугольника: 7

ooooooo

o o

ooooooo

Программирование (Python), 9 класс

168 of 194

Задачи

168

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

Пример:

Сторона квадрата: 5

ooooo

o o

ooooo

Программирование (Python), 9 класс

169 of 194

Задачи

169

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

Пример:

Сторона: 5

o

oo

ooo

oooo

ooooo

Программирование (Python), 9 класс

170 of 194

Рекурсия

170

Задача. Вывести на экран двоичный код натурального числа.

def printBin( n ):

...

Алгоритм перевода через остатки:

while n!=0:

print(n % 2, end="")

n = n // 2

Что получится � при n = 6?

?

011

в обратном порядке!

Программирование (Python), 9 класс

171 of 194

Рекурсия

171

Чтобы вывести двоичную запись числа n, нужно сначала вывести двоичную запись числа (n // 2), а за-�тем — его последнюю двоичную цифру, равную�(n % 2).

110

двоичная запись числа 6

двоичная запись числа 3

Чтобы решить задачу, � нужно решить ту же задачу � для меньшего числа!

!

Это и есть рекурсия!

Чтобы понять рекурсию, нужно понять рекурсию! ☺

!

Программирование (Python), 9 класс

172 of 194

Рекурсивная процедура

172

Рекурсивная процедура — это процедура, которая вызывает сама себя.

def printBin( n ):

printBin(n % 2)

print(n % 2, end = "")

Что получится? printBin(6)

?

вызывает сама себя!

printBin(6)

printBin(3)

printBin(1)

printBin(0)

Как исправить?

?

бесконечные вызовы

Программирование (Python), 9 класс

173 of 194

Рекурсивная процедура

173

def printBin( n ):

if n == 0: return

printBin(n // 2)

print(n % 2, end="")

printBin(6)

printBin(3)

printBin(1)

printBin(0)

if n == 0: return

print(1 % 2)

print(3 % 2)

print(6 % 2)

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

printBin(6)

?

1

0

рекурсия заканчивается!

Программирование (Python), 9 класс

174 of 194

Задачи

174

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

Пример:

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

В восьмеричной: 102

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

Пример:

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

Основание: 6

В системе с основанием 6: 203

Программирование (Python), 9 класс

175 of 194

Задачи

175

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

Пример:

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

В шестнадцатеричной: 7B

«D»: Напишите рекурсивную процедуру, которая переводит число в любую систему счисления с основанием от 2 до 36.

Пример:

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

Основание: 20

В системе с основанием 20: HA

Программирование (Python), 9 класс

176 of 194

Программирование (Python)

§ 25. Функции

176

177 of 194

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

177

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

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

Avg

a, b

r

исходные данные

результат

целые

цел

Тип результата?

?

вещ

def Avg(a, b):

return (a+b)/2

return – вернуть

результат функции

Программирование (Python), 9 класс

178 of 194

Как вызывать функцию?

178

Запись результата в переменную:

sr = Avg(5, 8)

x = 2; y = 5

sr = Avg(x, 2*y+8)

6.5

Чему равно?

?

10

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

x = 2; y = 5

sr = Avg(x, y+3)

print( Avg(12,7) )�print( sr + Avg(x,12) )

5

9.5

12

Программирование (Python), 9 класс

179 of 194

Как вызывать функцию?

179

Использование в условных операторах:

a = int(input())

b = int(input())

if Avg(a,b) > 5:

print("Да!")

else:

print("Нет!");

Когда печатает «Да»?

?

Программирование (Python), 9 класс

180 of 194

Как вызывать функцию?

180

Использование в циклах:

a = int(input())

b = int(input())

while Avg(a,b) > 0:

print("Нет!")

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

print("Угадал!");

Когда напечатает «Угадал»?

?

ввод двух чисел в одной строчке

Программирование (Python), 9 класс

181 of 194

В других языках программирования

181

Паскаль:

С:

float Avg(int a, int b)

{

return (a+b)/2.0;

}

function Avg(a, b: integer): real;

begin

Avg:=(a+b)/2

end.

Avg

специальная переменная для записи результата функции

Программирование (Python), 9 класс

182 of 194

Максимум из двух (трёх) чисел

182

Задача. Составить функцию, которая определяет наибольшее из двух целых чисел.

def Max(a, b):

if a > b then

return a

else:

return b

Max

a, b

r

исходные данные

результат

цел

Как с её помощью найти � максимум из трёх?

?

def Max3(a, b, c):

return Max( Max(a,b), c )

Программирование (Python), 9 класс

183 of 194

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

183

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

def sumDigits( N ):

sum = 0 # накапливаем сумму с 0

while N!=0:

d = N % 10 # выделим последнюю цифру

sum += d # добавим к сумме

N = N // 10 # удалим последнюю цифру

return sum

Программирование (Python), 9 класс

184 of 194

Задачи

184

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

Пример:

Введите 5 чисел: 1 2 3 4 6

Среднее: 3.2

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

Пример:

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

Количество цифр: 3

Программирование (Python), 9 класс

185 of 194

Задачи

185

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

Пример:

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

Количество единиц: 4

Программирование (Python), 9 класс

186 of 194

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

186

Логическая функция — это функция, возвращающая логическое значения (да или нет).

можно ли применять операцию?
успешно ли выполнена операция?
обладают ли данные каким-то свойством?

Программирование (Python), 9 класс

187 of 194

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

187

def Even( N ):

if N % 2 == 0:

return True

else:

return False

Задача. Составить функцию, которая возвращает «True», если она получила чётное число и «False», если нечётное.

def Even( N ):

return (N % 2 == 0)

Программирование (Python), 9 класс

188 of 194

Рекурсивные функции

188

Рекурсивная функция — это функция, которая вызывает сама себя.

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

Как сформулировать решение рекурсивно?

?

Сумму цифр числа N нужно выразить через сумму цифр другого (меньшего) числа.

Сумма цифр числа N равна значению последней цифры плюс сумма цифр числа, полученного отбрасыванием последней цифры.

sumDig(12345) = 5 + sumDig(1234)

Программирование (Python), 9 класс

189 of 194

Рекурсивная функция

189

Вход: натуральное число N.

Шаг 1: d = N % 10

Шаг 2: M = N // 10

Шаг 3: s = сумма цифр числа M

Шаг 4: sum = s + d

Результат: sum.

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

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

число без последней цифры

Что забыли?

?

Когда остановить?

?

Программирование (Python), 9 класс

190 of 194

Сумма цифр числа (рекурсия)

190

def sumDigRec( N ):

if N == 0: return 0

else:

d = N % 10

sum = sumDigRec(N // 10)

return sum + d

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

?

if N == 0: return 0

Зачем это?

?

Программирование (Python), 9 класс

191 of 194

Задачи

191

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

Пример:

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

Ответ: Да

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

Пример:

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

Ответ: Нет

Программирование (Python), 9 класс

192 of 194

Задачи

192

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

Пример:

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

Число простое!

Пример:

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

Число составное!

Программирование (Python), 9 класс

193 of 194

Конец фильма

193

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

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

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

kpolyakov@mail.ru

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

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

eremin@pspu.ac.ru

Программирование (Python), 9 класс

194 of 194

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

194

иллюстрации художников издательства «Бином»
авторские материалы

Программирование (Python), 9 класс