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

Содержание

Слайд 2

Программирование на языке Python § 62. Массивы

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

§ 62. Массивы

Слайд 3

Что такое массив? Массив – это группа переменных одного типа, расположенных

Что такое массив?

Массив – это группа переменных одного типа, расположенных в

памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер (индекс).

Надо:

выделять память
записывать данные в нужную ячейку
читать данные из ячейки

Слайд 4

Что такое массив? A массив 2 15 НОМЕР элемента массива (ИНДЕКС)

Что такое массив?

A

массив

2

15

НОМЕР элемента массива
(ИНДЕКС)

A[0]

A[1]

A[2]

A[3]

A[4]

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

A[2]

НОМЕР (ИНДЕКС) элемента массива: 2

ЗНАЧЕНИЕ

элемента массива: 15
Слайд 5

Массивы в Python: списки A = [1, 3, 4, 23, 5]

Массивы в Python: списки

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

A =

[1, 3] + [4, 23] + [5]

[1, 3, 4, 23, 5]

A = [0]*10

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

A = list ( range(10) )

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Слайд 6

Генераторы списков A =[ i for i in range(10) ] [0,

Генераторы списков

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

[0, 1, 2, 3,

4, 5, 6, 7, 8, 9]

A =[ i*i  for i in range(10) ]

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

for i in range(10)

i*i

from random import randint
A = [ randint(20,100)
for x in range(10)]

randint(20,100)

A = [ i for i in range(100)  
if isPrime(i)  ]

if isPrime(i)

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

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

Слайд 7

Добавление элементов A = [1, 2, 3] x = 5 A.append

Добавление элементов

A = [1, 2, 3]
x = 5
A.append ( x+3 )

#

[1, 2, 3, 8]

append

Метод – операция, которую можно применить к списку.

A = [1, 2, 3]
A.insert ( 1, 35 )

# [1, 35, 2, 3]

insert

A.insert ( 0, 90 )

A = [90] + A

в конец списка

Слайд 8

Удаление элементов A = [1, 2, 3] x = A.pop (

Удаление элементов

A = [1, 2, 3]
x = A.pop ( 1 )

# x = 2, A = [1, 3]

удалить A[1]

A = [1, 2, 3]
x = A.pop () # x = 3, A = [1, 2]

удалить последний

A = [11, 29, 37, 45]
A.remove( 37 ) # A = [11, 29, 45]

Слайд 9

Ввод массива с клавиатуры Создание массива: Ввод с клавиатуры: N =

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

Создание массива:
Ввод с клавиатуры:

N = 10
A = [0]*N

for

i in range(N):
print ( f"A[{i}]=",
sep = "", end = "" )
A[i] = int( input() )

A[0] =
A[1] =
A[2] =
A[3] =
A[4] =

5
12
34
56
13

sep = ""

end = ""

не разделять элементы

не переходить на новую строку

Слайд 10

Ввод массива с клавиатуры Ввод без подсказок: Ввод в одной строке:

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

Ввод без подсказок:
Ввод в одной строке:

A = [

 int(input())  for i in range(N) ]

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]

int(input())

int(x)

или так:

s = input().split() # ["1","2","3","4","5"]
A = list( map(int, s) ) # [1,2,3,4,5]

применить int ко всем элементам s

построить список

Слайд 11

Вывод массива на экран Как список: print ( A ) [1,

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

Как список:

print ( A )

[1, 2, 3, 4,

5]

В строчку через пробел:

for i in range(N):
print ( A[i], end = " " )

1 2 3 4 5

или так:

for x in A:
print ( x, end = " " )

1 2 3 4 5

или так:

print ( *A )

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

Слайд 12

Как обработать все элементы массива? Создание массива: Обработка: N = 5

Как обработать все элементы массива?

Создание массива:
Обработка:

N = 5
A = [0]*N

# обработать

A[0]
# обработать A[1]
# обработать A[2]
# обработать A[3]
# обработать A[4]
Слайд 13

Как обработать все элементы массива? Обработка с переменной: i = 0

Как обработать все элементы массива?

Обработка с переменной:

i = 0
# обработать A[i]
i

+= 1
# обработать A[i]
i += 1
# обработать A[i]
i += 1
# обработать A[i]
i += 1
# обработать A[i]

i += 1

Обработка в цикле:

i = 0
while i < N:
# обработать A[i]
i += 1

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

for i in range(N):
# обработать A[i]

Слайд 14

Заполнение случайными числами from random import randint N = 10 A

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

from random import randint
N = 10
A = [ randint(20,100)


for x in range(N)]

randint(20,100)

случайные числа
[20,100]

from random import randint
N = 10
A = [0]*N
for i in range(N):
A[i] = randint(20,100)

или так:

Слайд 15

Перебор элементов Общая схема (можно изменять A[i]): for i in range(N):

Перебор элементов

Общая схема (можно изменять A[i]):

for i in range(N):
... #

сделать что-то с A[i]

Если не нужно изменять A[i]:

for x in A:
... # сделать что-то с x

for i in range(N):
A[i] += 1

x = A[0], A[1], ..., A[N-1]

for x in A:
print ( x )

Слайд 16

Подсчёт количества нужных элементов Задача. В массиве записаны данные о росте

Подсчёт количества нужных элементов

Задача. В массиве записаны данные о росте баскетболистов.

Сколько из них имеет рост больше 180 см, но меньше 190 см?

count = 0
for x in A:
if 180 < x and x < 190:
count += 1

Python:
180 < x < 190

Слайд 17

Сумма элементов массива summa = 0 for x in A: if

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

summa = 0
for x in A:
if 180 <

x < 190:
summa += x
print ( summa )

print ( sum(A) )

или так:

Слайд 18

Перебор элементов Среднее арифметическое: count = 0 summa = 0 for

Перебор элементов

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

count = 0
summa = 0
for x in A:
if

180 < x < 190:
count += 1
summa += x
print ( summa/count )

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

или так:

B = [ x for x in A ]
if 180 < x < 190]
print ( sum(B)/len(B) )

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

Слайд 19

Задачи «A»: Заполните массив случайными числами в интервале [0,100] и найдите

Задачи

«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

Слайд 20

Задачи «C»: Заполните массив из N элементов случайными числами в интервале

Задачи

«C»: Заполните массив из N элементов случайными числами в интервале [1,N]

так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку).
Пример:
Массив:
3 2 1 4 5
Слайд 21

Программирование на языке Python § 63. Алгоритмы обработки массивов

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

§ 63. Алгоритмы обработки массивов

Слайд 22

Поиск в массиве Найти элемент, равный X: i = 0 while

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

Найти элемент, равный X:

i = 0
while A[i] != X:

i += 1
print ( f"A[{i}]={X}" )

i = 0
while i < N and A[i] != X:
i += 1
if i < N:
print ( f"A[{i}]={X}" )
else:
print ( "Не нашли!" )

i < N

Слайд 23

Поиск в массиве nX = -1 for i in range (

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

nX = -1
for i in range ( N ):

if A[i] == X:
nX = i
break
if nX >= 0:
print ( f"A[{nX}]={X}" )
else:
print ( "Не нашли!" )

Вариант с досрочным выходом:

break

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

номер найденного элемента

Слайд 24

for i in range ( N ): if A[i] == X:

for i in range ( N ):
if A[i] == X:

print ( f"A[{i}]={X}" )
break
else:
print ( "Не нашли!" )

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

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

if X in A:
nX = A.index(X)
print ( f"A[{nX}]={X}" )
else:
print ( "Не нашли!" )

Слайд 25

Задачи «A»: Заполните массив случайными числами в интервале [0,5]. Введите число

Задачи

«A»: Заполните массив случайными числами в интервале [0,5]. Введите число X

и найдите все значения, равные X.
Пример:
Массив:
1 2 3 1 2
Что ищем:
2
Нашли: A[2]=2, A[5]=2
Пример:
Массив:
1 2 3 1 2
Что ищем:
6
Ничего не нашли.
Слайд 26

Задачи «B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть

Задачи

«B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли

в нем элементы с одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1 2 3 3 2 1
Есть: 3
Пример:
Массив:
1 2 3 4 2 1
Нет
Слайд 27

Задачи «C»: Заполните массив случайными числами. Определить, есть ли в нем

Задачи

«C»: Заполните массив случайными числами. Определить, есть ли в нем элементы

с одинаковыми значениями, не обязательно стоящие рядом.
Пример:
Массив:
3 2 1 3 2 5
Есть: 3, 2
Пример:
Массив:
3 2 1 4 0 5
Нет
Слайд 28

Максимальный элемент M = A[0] for i in range(1,N): if A[i]

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

M = A[0]
for i in range(1,N):
if A[i] > M:


M = A[i]
print ( M )

M = A[0]
for x in A:
if x > M:
M = x

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

M = max ( A )

Слайд 29

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

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

Слайд 30

Максимальный элемент и его номер M = max(A) nMax = A.index(M)

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

M = max(A)
nMax = A.index(M)
print ( f"A[{nMax}]={M}"

)

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

Слайд 31

Задачи «A»: Заполнить массив случайными числами и найти минимальный и максимальный

Задачи

«A»: Заполнить массив случайными числами и найти минимальный и максимальный элементы

массива и их номера.
Пример:
Массив:
1 2 3 4 5
Минимальный элемент: A[1]=1
Максимальный элемент: A[5]=5

«B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5

Слайд 32

Задачи «C»: Введите массив с клавиатуры и найдите (за один проход)

Задачи

«C»: Введите массив с клавиатуры и найдите (за один проход) количество

элементов, имеющих максимальное значение.
Пример:
Массив:
3 4 5 5 3 4 5
Максимальное значение 5
Количество элементов 3
Слайд 33

Реверс массива «Простое» решение: for i in range( N ): поменять

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

«Простое» решение:

for i in range( N ):
поменять местами A[i]

и A[N-1-i]

N//2

остановиться на середине!

Слайд 34

Реверс массива for i in range(N//2): c = A[i] A[i] =

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

for i in range(N//2):
c = A[i]
A[i] = A[N-1-i]

A[N-1-i] = c

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

for i in range(N//2):
A[i], A[N-i-1]= A[N-i-1], A[i]

A.reverse()

Слайд 35

Циклический сдвиг элементов «Простое» решение: c = A[0] for i in

Циклический сдвиг элементов

«Простое» решение:

c = A[0]
for i in range(N-1):
A[i] =

A[i+1]
A[N-1] = c
Слайд 36

Срезы в Python A[1:3] [12, 5] A[2:3] [5] A[:3] [7, 12,

Срезы в Python

A[1:3]

[12, 5]

A[2:3]

[5]


A[:3]

[7, 12, 5]

A[0:3]

с начала

A[3:N-2]

[8,…,18,34]

A[3:]

[8,…,18,34,40,23]

A[3:N]

до конца

A[:]

[7,12,5,8,…,18,34,40,23]

копия массива

Слайд 37

Срезы в Python – отрицательные индексы A[1:-1] [12,5,8,…,18,34,40] A[1:N-1] A[-4:-2] [18, 34] A[N-4:N-2]

Срезы в Python – отрицательные индексы

A[1:-1]

[12,5,8,…,18,34,40]

A[1:N-1]

A[-4:-2]

[18, 34]

A[N-4:N-2]

Слайд 38

Срезы в Python – шаг A[1:6:2] [12, 8, 18] A[::3] [7,

Срезы в Python – шаг

A[1:6:2]

[12, 8, 18]


A[::3]

[7, 8, 34]

A[8:2:-2]

[23, 34, 76]

A[::-1]

[23,40,34,18,76,8,5,12,7]

реверс!

A.reverse()

шаг

Слайд 39

Задачи «A»: Заполнить массив случайными числами и выполнить циклический сдвиг элементов

Задачи

«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

Слайд 40

Задачи «C»: Заполнить массив случайными числами в интервале [-100,100] и переставить

Задачи

«C»: Заполнить массив случайными числами в интервале [-100,100] и переставить элементы

так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов.
Пример:
Массив:
20 -90 15 -34 10 0
Результат:
20 15 10 -90 -34 0
Количество положительных элементов: 3
Слайд 41

Отбор нужных элементов Простое решение: Задача. Отобрать элементы массива A, удовлетворяющие

Отбор нужных элементов

Простое решение:

Задача. Отобрать элементы массива 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

Слайд 42

Отбор нужных элементов Решение в стиле Python: Задача. Отобрать элементы массива

Отбор нужных элементов

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

Задача. Отобрать элементы массива A, удовлетворяющие

некоторому условию, в массив B.

B = [ x for x in A ] 
if x % 2 == 0  ]

если x – чётное число

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

Слайд 43

Особенности работы со списками A = [1, 2, 3] B =

Особенности работы со списками

A = [1, 2, 3]
B = A

[1, 2,

3]

A

B

A[0] = 0

A = [1, 2, 3]
B = A[:]

копия массива A

[1, 2, 3]

A

[1, 2, 3]

B

A[0] = 0

Слайд 44

Копирование списков «Поверхностное» копирование: import copy A = [1, 2, 3]

Копирование списков

«Поверхностное» копирование:

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

0

«Глубокое» копирование:

D = copy.deepcopy(C)

Слайд 45

Задачи «A»: Заполнить массив случайными числами в интервале [-10,10] и отобрать

Задачи

«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

Слайд 46

Задачи «C»: Заполнить массив случайными числами и отобрать в другой массив

Задачи

«C»: Заполнить массив случайными числами и отобрать в другой массив все

числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи.
Пример:
Массив А:
12 13 85 34 47
Массив B:
13 34
Слайд 47

Программирование на языке Python § 64. Сортировка

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

§ 64. Сортировка

Слайд 48

Что такое сортировка? Сортировка – это расстановка элементов массива в заданном

Что такое сортировка?

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

…по

возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, …

Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
сложные, но эффективные
«быстрая сортировка» (QuickSort)
сортировка «кучей» (HeapSort)
сортировка слиянием (MergeSort)
пирамидальная сортировка

Слайд 49

Метод пузырька (сортировка обменами) Идея: пузырек воздуха в стакане воды поднимается

Метод пузырька (сортировка обменами)

Идея: пузырек воздуха в стакане воды поднимается со

дна вверх.
Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).

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

1-й проход:

Слайд 50

Метод пузырька 2-й проход: 3-й проход: 4-й проход:

Метод пузырька

2-й проход:

3-й проход:

4-й проход:

Слайд 51

Метод пузырька 1-й проход: сделать для j от N-2 до 0

Метод пузырька

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]

1

единственное отличие!

Слайд 52

Метод пузырька 1-й проход: for j in range(N-2, -1 ,-1): if

Метод пузырька

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]

0

единственное отличие!

от N-2 до 0 шаг -1

Слайд 53

Метод пузырька for i in range(N-1): for j in range(N-2, i-1

Метод пузырька

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]

i-1

Слайд 54

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

Задачи

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

«тяжёлый» элемент опускается в конец массива.

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

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

Слайд 55

Метод выбора (минимального элемента) Идея: найти минимальный элемент и поставить его

Метод выбора (минимального элемента)

Идея: найти минимальный элемент и поставить его на

первое место.

for i in range(N-1):
найти номер nMin минимального элемента из A[i]..A[N]
if i != nMin:
поменять местами A[i] и A[nMin]

Слайд 56

Метод выбора (минимального элемента) for i in range(N-1): if i!= nMin:

Метод выбора (минимального элемента)

for i in range(N-1):
if i!= nMin:
A[i], A[nMin]

= A[nMin], A[i]

nMin = i
for j in range(i+1,N):
if A[j] < A[nMin]:
nMin = j

Слайд 57

Метод вставок (insertion sort) Идея: освобождаем место для нового элемента, сдвигая

Метод вставок (insertion sort)

Идея: освобождаем место для нового элемента, сдвигая те,

которые должны стоять после него.

key

key

key

1

5

1

4

5

4

2

2

5

4

key

3

3

5

4

Слайд 58

Метод вставок (insertion sort) Идея: освобождаем место для нового элемента, сдвигая

Метод вставок (insertion sort)

Идея: освобождаем место для нового элемента, сдвигая те,

которые должны стоять после него.

for i in range(N):
key = A[i]
A[j] = key

все N!

j = i
while j > 0 and A[j-1] > key:
A[j] = A[j-1]:
j -= 1

сдвиг всех, которые больше key

ставим key на место

Слайд 59

Задачи «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует

Задачи

«A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую

половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
Слайд 60

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

Задачи

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

в нем.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5

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

Слайд 61

Сортировка слиянием Слияние отсортированных массивов: A B С Na = len(A);

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

Слияние отсортированных массивов:

A

B

С

Na = len(A); Nb = len(B)
iA = iB

= 0; C = []
while iA < Na and iB < Nb:
if A[iA] <= B[iB]:
C.append(A[iA]); iA += 1
else:
C.append(B[iB]); iB += 1
C = С + A[iA:] + B[iВ:]

пока оба массива непустые

добавить остаток

Слайд 62

Сортировка слиянием def mergeSort( A ): if len(A) mid = len(A)

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

def mergeSort( A ):
if len(A) <= 1: return
mid

= len(A) // 2
L = A[:mid]
R = A[mid:]
mergeSort(L)
mergeSort(R)
C = merge(L, R)
for i in range(len(A)):
A[i] = C[i]

слияние

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

копируем результат в массив A

Слайд 63

Сортировка слиянием def merge( A, B ): Na = len(A); Nb

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

def merge( A, B ):
Na = len(A); Nb =

len(B)
iA = iB = 0; C = []
while iA < Na and iB < Nb:
if A[iA] <= B[iB]:
C.append(A[iA]); iA += 1
else:
C.append(B[iB]); iB += 1
C = С + A[iA:] + B[iВ:]
return C

Процедура слияния:

Слайд 64

Сортировка слиянием задача разбивается на несколько подзадач меньшего размера; эти подзадачи

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

задача разбивается на несколько подзадач меньшего размера;
эти подзадачи решаются с

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

«Разделяй и властвуй» (divide and conquer):

работает быстро

нужен дополнительный массив

Слайд 65

Быстрая сортировка (QuickSort) разделение Медиана – такое значение X, что слева

Быстрая сортировка (QuickSort)

разделение

Медиана – такое значение X, что слева и справа

от него в отсортированном массиве стоит одинаковое число элементов (долго искать …).
Слайд 66

Быстрая сортировка (QuickSort) B1: B2: > X BX: = X import

Быстрая сортировка (QuickSort)

B1: < X

B2: > X

BX: = X

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

расход памяти!

Слайд 67

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

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

Слайд 68

Быстрая сортировка «на месте» Шаг 2: переставить элементы так: при сортировке

Быстрая сортировка «на месте»

Шаг 2: переставить элементы так:
при сортировке

элементы не покидают « свою область»!

Шаг 1: выбрать некоторый элемент массива X

Шаг 3: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Слайд 69

Быстрая сортировка Разделение: выбрать любой элемент массива (X=67) установить L =

Быстрая сортировка

Разделение:
выбрать любой элемент массива (X=67)
установить L = 0, R

= N-1
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп.

L

R

L

R

78

44

44

78

Слайд 70

Быстрая сортировка

Быстрая сортировка

Слайд 71

Быстрая сортировка N = 7 A = [0]*N # заполнить массив

Быстрая сортировка

N = 7
A = [0]*N
# заполнить массив
qSort( A, 0,

N-1 ) # сортировка
# вывести результат

Основная программа:

массив

начало

конец

Слайд 72

Быстрая сортировка def qSort ( A, nStart, nEnd ): if nStart

Быстрая сортировка

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

qSort ( A, nStart, R )
qSort ( A, L, nEnd )

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

while A[L] < X: L += 1
while A[R] > X: R -= 1

разделение на 2 части

массив

начало

конец

меняем местами

Слайд 73

Быстрая сортировка Случайный выбор элемента-разделителя: from random import randint def qSort

Быстрая сортировка

Случайный выбор элемента-разделителя:

from random import randint
def qSort ( A,

nStart, nEnd ):
...
X = A[randint(L,R)]
...

X = A[randint(L,R)]

или так:

from random import choice
def qSort ( A, nStart, nEnd ):
...
X = choice ( A[L:R+1] )
...

X = choice ( A[L:R+1] )

Слайд 74

Сортировка в Python B = sorted( A ) алгоритм Timsort По

Сортировка в Python

B = sorted( A )

алгоритм Timsort

По возрастанию:

B =

sorted( A, reverse = True )

По убыванию:

reverse = True

По последней цифре:

def lastDigit ( n ):
return n % 10
B = sorted( A, key = lastDigit )

key = lastDigit

или так:

B = sorted( A, key = lambda x: x % 10  )

lambda x: x % 10

«лямбда»-функция
(функция без имени)

Слайд 75

Сортировка в Python – на месте A.sort() По возрастанию: A.sort (

Сортировка в Python – на месте

A.sort()

По возрастанию:

A.sort ( reverse =

True )

По убыванию:

reverse = True

По последней цифре:

def lastDigit ( n ):
return n % 10
A.sort ( key = lastDigit )

key = lastDigit

или так:

A.sort( key = lambda x: x % 10  )

lambda x: x % 10

Слайд 76

Задачи «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует

Задачи

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

возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2
После сортировки:
2 3 4 5 6 3 2 1
Слайд 77

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

Задачи

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

в нем. Используйте алгоритм быстрой сортировки.
Пример:
Массив:
5 3 4 2 1 6 3 2 4
После сортировки:
1 2 2 3 3 4 4 5 6
Различных чисел: 5
Слайд 78

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

Задачи

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

«пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

«D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки c с выбором среднего элемента показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

Слайд 79

Программирование на языке Python § 65. Двоичный поиск

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

§ 65. Двоичный поиск

Слайд 80

Двоичный поиск X = 7 X 8 4 X > 4

Двоичный поиск

X = 7

X < 8

8

4

X > 4

6

X > 6

Выбрать средний

элемент A[c] и сравнить с X.
Если X == A[c], то нашли (стоп).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.
Слайд 81

Двоичный поиск X = 44

Двоичный поиск

X = 44

Слайд 82

Двоичный поиск L = 0; R = N # начальный отрезок

Двоичный поиск

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 ( f"A[{L}]={X}" )
else:
print ( "Не нашли!" )
Слайд 83

Двоичный поиск скорость выше, чем при линейном поиске нужна предварительная сортировка Число сравнений:

Двоичный поиск

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

нужна предварительная сортировка

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

Слайд 84

Задачи «A»: Заполнить массив случайными числами и отсортировать его. Ввести число

Задачи

«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
Слайд 85

Задачи «B»: Заполнить массив случайными числами и отсортировать его. Ввести число

Задачи

«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 не встречается.
Слайд 86

Задачи «C»: Заполнить массив случайными числами и ввести число и отсортировать

Задачи

«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.
Слайд 87

Программирование на языке Python § 66. Символьные строки

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

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

Слайд 88

Символьные строки Начальное значение: Вывод на экран: print ( s )

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

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

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

print ( s )

s = "Привет!"

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

n

= len ( s )

print ( s[5] )

print ( s[-2] )

s[len(s)-2]

Слайд 89

Символьные строки Ввод с клавиатуры: s = input ( "Введите имя:

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

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

s = input ( "Введите имя: " )

Изменение

строки:

s[4] = "a"

... но можно составить новую строку:

s1 = s + "a"

Слайд 90

Символьные строки s = input( "Введите строку:" ) s1 = ""

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

s = input( "Введите строку:" )
s1 = "" # строка-результат
for

c in s:
if c == "а":
c = "б"
s1 = s1 + c
print ( s1 )

Задача: заменить в строке все буквы "а" на буквы "б".

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

добавить символ к строке-результату

Слайд 91

Задачи «A»: Ввести с клавиатуры символьную строку и заменить в ней

Задачи

«A»: Ввести с клавиатуры символьную строку и заменить в ней все

буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные).
Пример:
Введите строку:
ааббААББссСС
Результат:
ббааББААссСС
Слайд 92

Задачи «B»: Ввести с клавиатуры символьную строку и определить, сколько в

Задачи

«B»: Ввести с клавиатуры символьную строку и определить, сколько в ней

слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.
Пример:
Введите строку:
Вася пошел гулять
Найдено слов: 3
Слайд 93

Задачи «C»: Ввести с клавиатуры символьную строку и найдите самое длинное

Задачи

«C»: Ввести с клавиатуры символьную строку и найдите самое длинное слово

и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.
Пример:
Введите строку:
Вася пошел гулять
Самое длинное слово: гулять, длина 6
Слайд 94

Сравнение строк print( "Введите 2 строки:" ) s1 = input() s2

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

print( "Введите 2 строки:" )
s1 = input()
s2 = input()
if

s1 == s2:
print( s1, "=", s2 )
elif s1 < s2:
print( s1, "<", s2 )
else:
print( s1, ">", s2 )
Слайд 95

Сравнение строк 5STEAM steam

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

5STEAM < STEAM < Steam < steam 

steam < ПАР < Пар < пАр < пар < парк

Слайд 96

Операции со строками Объединение (конкатенация) : s1 = "Привет" s2 =

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

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

s1 = "Привет"
s2 = "Вася"
s

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

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

Срезы:

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

этот символ не входит!

Слайд 97

Операции со строками Срезы: s = "0123456789" s1 = s[:8] #

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

Срезы:

s = "0123456789"
s1 = s[:8] # "01234567"

от начала

строки

s = "0123456789"
s1 = s[3:] # "3456789"

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

s1 = s[::-1] # "9876543210"

реверс строки

Слайд 98

Операции со строками Срезы с отрицательными индексами: s = "0123456789" s1

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

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

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

"01234567"

N-2

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

N-2

N-6

Слайд 99

Удаление и вставка символов Вставка: s = "0123456789" s1 = s[:3]

Удаление и вставка символов

Вставка:

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

s[3:]

Удаление:

s = "0123456789"
s1 = s[:3] + s[9:] # "0129"

"012"

"9"

"012ABC3456789"

Слайд 100

Стандартные функции Верхний/нижний регистр: s = "aAbBcC" s1 = s.upper() #

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

Верхний/нижний регистр:

s = "aAbBcC"
s1 = s.upper() # "AABBCC"
s2 = s.lower()

# "aabbcc"

Проверка на цифры:

s = "abc"
print ( s.isdigit() ) # False
s1 = "123"
print ( s1.isdigit() ) # True

… и много других.

Слайд 101

Поиск в строках s = "Здесь был Вася." n = s.find

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

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

) # n = 3
if n >= 0:
print ( "Номер символа", n )
else:
print ( "Символ не найден." )

s = "Здесь был Вася."
n = s.rfind ( "с" ) # n = 12

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

Слайд 102

Пример обработки строк Задача: Ввести имя, отчество и фамилию. Преобразовать их

Пример обработки строк

Задача: Ввести имя, отчество и фамилию. Преобразовать их к

формату «фамилия-инициалы».
Пример:
Введите имя, отчество и фамилию:
Василий Алибабаевич Хрюндиков
Результат:
Хрюндиков В.А.

Алгоритм:
найти первый пробел и выделить имя
удалить имя с пробелом из основной строки
найти первый пробел и выделить отчество
удалить отчество с пробелом из основной строки
«сцепить» фамилию, первые буквы имени и фамилии, точки, пробелы…

Алибабаевич Хрюндиков

Хрюндиков

Хрюндиков В.А.

Слайд 103

Пример обработки строк print ( "Введите имя, отчество и фамилию:" )

Пример обработки строк

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 )
Слайд 104

Пример обработки строк print ( "Введите имя, отчество и фамилию:" )

Пример обработки строк

print ( "Введите имя, отчество и фамилию:" )
s =

input()
fio = s.split()
s = fio[2] + " " + fio[0][0] + "." + fio[1][0] + "."
print ( s )

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

Василий Алибабаевич Хрюндиков

fio[2]

fio[1]

fio[0]

Слайд 105

Задачи «A»: Ввести с клавиатуры в одну строку фамилию, имя и

Задачи

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

разделив их пробелом. Вывести фамилию и инициалы.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
П.С. Иванов
Слайд 106

Задачи «B»: Ввести адрес файла и «разобрать» его на части, разделенные

Задачи

«B»: Ввести адрес файла и «разобрать» его на части, разделенные знаком

"/". Каждую часть вывести в отдельной строке.
Пример:
Введите адрес файла:
C:/Фото/2013/Поход/vasya.jpg
C:
Фото
2013
Поход
vasya.jpg
Слайд 107

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

Задачи

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

на другую.
Пример:
Введите строку:
(X > 0) and (Y < X) and (Z > Y) and (Z <> 5)
Что меняем: and
Чем заменить: &
Результат
(X > 0) & (Y < X) & (Z > Y) & (Z <> 5)
Слайд 108

Преобразования «строка» – «число» Из строки в число: s = "123"

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

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

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"

Слайд 109

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

Задачи

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

символьной строки. Все числа целые.
Пример:
Введите выражение:
12+3+45
Ответ: 60

«B»: Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые.
Пример:
Введите выражение:
12-3+45
Ответ: 54

Слайд 110

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

Задачи

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

двух знаков (допускаются знаки «+», «–», «*» и «/»). Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление.
Пример:
Введите выражение:
12*3+45
Ответ: 81
Слайд 111

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

Задачи

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

двух знаков (допускаются знаки «+», «–», «*» и «/») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление (div).
Пример:
Введите выражение:
2*(3+45)+4
Ответ: 100
Слайд 112

Строки в процедурах и функциях Задача: построить функцию, которая возвращает первое

Строки в процедурах и функциях

Задача: построить функцию, которая возвращает первое слово

в предложении.

def firstWord( s ):
s = s.strip()

p = s.find( ' ' )
if p < 0:
return s
else:
return s[:p]

p = s.find( ' ' )
return s[:p]

word = firstWord( s )
print( word )

Однажды весною, в час…

Однажды

Однажды весною, в час…

Однажды

Слайд 113

Замена подстроки Задача: построить функцию, которая заменяет в строке s все

Замена подстроки

Задача: построить функцию, которая заменяет в строке s все вхождения

слова-образца wOld на слово-замену wNew.

пока слово wOld есть в строке s
удалить слово wOld из строки
вставить на это место слово wNew

wOld: "12"
wNew: "A12B"

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

Слайд 114

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

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

Слайд 115

Замена всех экземпляров подстроки s = "12.12.12" s = replaceAll (

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

s = "12.12.12"
s = replaceAll ( s, "12",

"A12B" )
print( s )
Слайд 116

Замена всех экземпляров подстроки def replaceAll ( s, wOld, wNew ):

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

def replaceAll ( s, wOld, wNew ):
lenOld

= len(wOld)
res = ""
while len(s) > 0:
p = s.find ( wOld )
if p < 0:
return res + s
if p > 0: res = res + s[:p]
res = res + wNew
if p+lenOld >= len(s):
s = ""
else:
s = s[p+lenOld:]
return res

добавить слово-замену

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

взять «хвост»

взять начало перед образцом

искать образец

если не нашли

Слайд 117

Замена всех экземпляров подстроки s = "12.12.12" s = s.replace( "12",

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

s = "12.12.12"
s = s.replace( "12", "A12B" )
print

( s )

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

Слайд 118

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

Задачи

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

строку: Однажды в студёную зимнюю пору...
Первое слово: Однажды
Слайд 119

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

Задачи

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


Пример:
Введите имя файла: qq
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.exe
Введите новое расширение: tmp
Результат: qq.tmp
Пример:
Введите имя файла: qq.work.xml
Введите новое расширение: tmp
Результат: qq.work.tmp
Слайд 120

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

Задачи

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

на соответствующие десятичные числа.
Пример:
Введите строку:
В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов.
Результат:
В 2013 году в школе 123 состоялся очередной выпуск 11 классов.
Слайд 121

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

Рекурсивный перебор

Задача. В алфавите языка племени «тумба-юмба» четыре буквы: «Ы», «Ш»,

«Ч» и «О». Нужно вывести на экран все слова, состоящие из L букв, которые можно построить из букв этого алфавита.

перебор L-1 символов

задача для слов длины L сведена к задаче для слов длины L-1!

Слайд 122

Рекурсивный перебор перебор L символов w[0]="Ы" # перебор последних L-1 символов

Рекурсивный перебор

перебор L символов
w[0]="Ы"
# перебор последних L-1 символов
w[0]="Ш"

# перебор последних L-1 символов
w[0]="Ч"
# перебор последних L-1 символов
w[0]="О"
# перебор последних L-1 символов
Слайд 123

Рекурсивный перебор # основная программа TumbaWords ( "ЫШЧО", "", 3 )

Рекурсивный перебор

# основная программа
TumbaWords ( "ЫШЧО", "", 3 )

def TumbaWords (

A, w, L ):
if len(w) == L:
print ( w )
return
for c in A:
TumbaWords ( A, w + c, L )

нужная длина слова

слово полной длины

по всем символам алфавита

алфавит

слово

Слайд 124

Рекурсивный перебор + счётчик TumbaWords ( "ЫШЧО", "", 3 ) print(

Рекурсивный перебор + счётчик

TumbaWords ( "ЫШЧО", "", 3 )
print( count )

def

TumbaWords ( A, w, L ):
if len(w) == L:
print ( w )
return
for c in A:
TumbaWords ( A, w + c, L )

будем менять глобальную переменную

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

count = 0

count += 1

global count

Слайд 125

Рекурсивный перебор + условие TumbaWords ( "ЫШЧО", "", 3 ) print(

Рекурсивный перебор + условие

TumbaWords ( "ЫШЧО", "", 3 )
print( count )

def

TumbaWords ( A, w, L ):
global count
if len(w) == L:
if not "ОО" in w:
print ( w )
count += 1
return
for c in A:
TumbaWords ( A, w + c, L )

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

count = 0

if not "ОО" in w:

Слайд 126

Рекурсивный перебор + условие (функция) def TumbaWords ( A, w, L

Рекурсивный перебор + условие (функция)

def TumbaWords ( A, w, L ):

global count
if len(w) == L:
if valid(w):
print ( w )
count += 1
return
for c in A:
TumbaWords ( A, w + c, L )

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

if valid(w):

def valid ( s ):
if not "ОО" in w:
return True
else:
return False

return not "ОО" in w

Слайд 127

Задачи «A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш»,

Задачи

«A»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч»

и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов.

«B»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

Слайд 128

Задачи «C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш»,

Задачи

«C»: В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч»

и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.
Слайд 129

Сортировка строк aS = [] # пустой список строк print (

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

aS = [] # пустой список строк
print ( "Введите

строки для сортировки:" )
while True:
s1 = input()
if s1 == "": break
aS.append ( s1 ) # добавить в список
aS.sort() # сортировка
print ( aS )
Слайд 130

Задачи «A»: Вводится 5 строк, в которых сначала записан порядковый номер

Задачи

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

с точкой, а затем – слово. Вывести слова в алфавитном порядке.
Пример:
Введите 5 строк:
1. тепловоз
2. арбуз
3. бурундук
4. кефир
5. урядник
Список слов в алфавитном порядке:
арбуз, бурундук, кефир, тепловоз, урядник
Слайд 131

Задачи «B»: Вводится несколько строк (не более 20), в которых сначала

Задачи

«B»: Вводится несколько строк (не более 20), в которых сначала записан

порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке.
Пример:
Введите слова:
1. тепловоз
2. арбуз
Список слов в алфавитном порядке:
арбуз, тепловоз
Слайд 132

Задачи «C»: Вводится несколько строк (не более 20), в которых сначала

Задачи

«C»: Вводится несколько строк (не более 20), в которых сначала записаны

инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии.
Пример:
Введите ФИО:
А.Г. Урядников
Б.В. Тепловозов
В.Д. Арбузов
Список в алфавитном порядке:
В.Д. Арбузов
Б.В. Тепловозов
А.Г. Урядников
Слайд 133

Программирование на языке Python § 67. Матрицы

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

§ 67. Матрицы

Слайд 134

Что такое матрица? Матрица — это прямоугольная таблица, составленная из элементов

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

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

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

нет знака

нолик

крестик

A[1][2]

A

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

Слайд 135

Создание матриц A = [[-1, 0, 1], [-1, 0, 1], [0,

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

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

[0, 1, -1]]

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

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

или так:

Слайд 136

Создание матриц N = 3 M = 2 row = [0]*M

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

N = 3
M = 2
row = [0]*M
A = [row]*N

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

row

A

A[0][0]

= 1

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

A = []
for i in range(N):
A.append ( [0]*M )

A

A[0][0] = 1

Слайд 137

Ввод матрицы с клавиатуры 3 4 1 2 3 4 5

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

3 4
1 2 3 4
5 6 7 8
9

10 11 12

Данные на входе:

N

M

N, M = map( int, input().split() )
A = []
for i in range(N):
row = [int(x) for x in input().split()]
A.append( row )

Программа:

Слайд 138

Вывод матриц print ( A ) [[1, 12, 3], [4, 5,

Вывод матриц

print ( A )

[[1, 12, 3], [4, 5, 146], [7,

118, 99]]

def printMatrix ( A ):
for row in A:
for x in row:
print ( f"{x:4d}", end = "" )
print ()

1 12 3
4 5 146
7 118 99

for x in row:
print ( f"{x:4d}", end = "" )

Слайд 139

Простые алгоритмы Заполнение случайными числами: import random for i in range(N):

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

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

import random
for i in range(N):
for j in

range(M):
A[i][j] = random.randint ( 20, 80 )
print ( f"{A[i][j]:4d}", 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 )

A[i][j] = random.randint ( 20, 80 )

Слайд 140

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

Задачи

«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
Слайд 141

Задачи «B»: Яркости пикселей рисунка закодированы числами от 0 до 255

Задачи

«B»: Яркости пикселей рисунка закодированы числами от 0 до 255 в

виде матрицы. Преобразовать рисунок в черно-белый по следующему алгоритму:
вычислить среднюю яркость пикселей по всему рисунку
все пиксели, яркость которых меньше средней, сделать черными (записать код 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
Слайд 142

Задачи «С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными

Задачи

«С»: Заполните матрицу, содержащую N строк и M столбцов, натуральными числами

по спирали и змейкой, как на рисунках:
Слайд 143

Перебор элементов матрицы Главная диагональ: for i in range(N): # работаем

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

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

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]

Слайд 144

Перестановка строк и столбцов 2-я и 4-я строки: A[2], A[4] =

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

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

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

2-й

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

for i in range(N):
A[i][2], A[i][4] = A[i][4], A[i][2]

Слайд 145

Выделение строк и столбцов 1-я строка: R = A[1][:] 2-й столбец:

Выделение строк и столбцов

1-я строка:

R = A[1][:]

2-й столбец:

C = []
for row

in A:
C.append(row[2])

R = A[1]

или так:

C = [ row[2] for row in A ]

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

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

Слайд 146

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

Задачи

«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
Слайд 147

Задачи «B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы,

Задачи

«B»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей

N строк и M столбцов. Выполните отражение рисунка сверху вниз:

«С»: Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

Слайд 148

Программирование на языке Python § 68. Работа с файлами

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

§ 68. Работа с файлами

Слайд 149

Какие бывают файлы? файлы текстовые двоичные «plain text»: для чтения человеком

Какие бывают файлы?

файлы

текстовые

двоичные

«plain text»:
для чтения человеком
текст, разбитый на строки;
из специальных

символов только символы перехода на новую строку

любые символы
рисунки, звуки, видео, …

12
123
1234

Слайд 150

Принцип сэндвича хлеб хлеб начинка Fin = open ( "input.txt" )

Принцип сэндвича

хлеб

хлеб

начинка

Fin = open ( "input.txt" )
Fout = open ( "output.txt",

"w" )
# здесь работаем с файлами
Fin.close()
Fout.close()

файловые переменные-указатели

"r" - чтение
"w" – запись
"a" – добавление

по умолчанию – на чтение (режим "r")

Слайд 151

Ввод данных Fin = open( "input.txt" ) s = Fin.readline() #

Ввод данных

Fin = open( "input.txt" )

s = Fin.readline() # "1 2"

Чтение

строки:

Чтение строки и разбивка по пробелам:

s = Fin.readline().split() # ["1","2"]

Чтение целых чисел:

s = Fin.readline().split() # ["1","2"]
a, b = int(s[0]), int(s[1])

или так:

a, b = [int(x) for x in s]

или так:

a, b = map( int, s )

Слайд 152

Вывод данных в файл a = 1 b = 2 Fout

Вывод данных в файл

a = 1
b = 2
Fout = open( "output.txt",

"w" )
Fout.write ( f"{a} + {b} = {a+b}\n" )
Fout.close()

a = 1
b = 2
Fout = open( "output.txt", "w" )
print( f"{a} + {b} = {a+b}", file = Fout )
Fout.close()

file = Fout

не надо "\n"

Слайд 153

Чтение неизвестного количества данных пока не конец файла прочитать число из

Чтение неизвестного количества данных

пока не конец файла
прочитать число из файла

добавить его к сумме

Задача. В файле записано в столбик неизвестное количество чисел. Найти их сумму.

Fin = open ( "input.txt" )
sum = 0
while True:
s = Fin.readline()
if not s: break
sum += int(s)
Fin.close()

если конец файла, вернёт пустую строку

Слайд 154

Чтение неизвестного количества данных Задача. В файле записано в столбик неизвестное

Чтение неизвестного количества данных

Задача. В файле записано в столбик неизвестное количество

чисел. Найти их сумму.

sum = 0
Fin = open ( "input.txt" )
lst = Fin.readlines()
for s in lst:
sum += int(s)
Fin.close()

прочитать все строки в список строк

Слайд 155

Чтение неизвестного количества данных Задача. В файле записано в столбик неизвестное

Чтение неизвестного количества данных

Задача. В файле записано в столбик неизвестное количество

чисел. Найти их сумму.

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)

Слайд 156

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

Задачи

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

файле в столбик, и выводит результат в другой файл.
«B»: Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть.
«C»: В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.
Слайд 157

Обработка массивов Задача. В файле записаны в столбик целые числа. Вывести

Обработка массивов

Задача. В файле записаны в столбик целые числа. Вывести в

другой текстовый файл те же числа, отсортированные в порядке возрастания.
Слайд 158

Обработка массивов Ввод массива: A = [] while True: s =

Обработка массивов

Ввод массива:

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

Слайд 159

Обработка массивов Вывод результата: Fout = open ( "output.txt", "w" )

Обработка массивов

Вывод результата:

Fout = open ( "output.txt", "w" )
Fout.write ( str(A)

)
Fout.close()

или так:

for x in A:
Fout.write ( str(x)+"\n" )

[1, 2, 3]

1
2
3

или так:

for x in A:
Fout.write ( f"{x:4d}" )

1 2 3

Слайд 160

Задачи «A»: В файле в столбик записаны числа. Отсортировать их по

Задачи

«A»: В файле в столбик записаны числа. Отсортировать их по возрастанию

последней цифры и записать в другой файл.
«B»: В файле в столбик записаны числа. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа.
«C»: В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.
Слайд 161

Обработка строк Задача. В файле записано данные о собаках: в каждой

Обработка строк

Задача. В файле записано данные о собаках: в каждой строчке

кличка собаки, ее возраст и порода:
Мухтар 4 немецкая овчарка
Вывести в другой файл сведения о собаках, которым меньше 5 лет.

пока не конец файла Fin
прочитать строку из файла Fin
разобрать строку – выделить возраст
если возраст < 5 то
записать строку в файл Fout

Слайд 162

Чтение данных из файла Чтение одной строки: s = Fin.readline() Разбивка

Чтение данных из файла

Чтение одной строки:

s = Fin.readline()

Разбивка по пробелам:

data =

s.split()

Выделение возраста:

sAge = data[1]
age = int ( sAge )

Кратко всё вместе:

s = Fin.readline()
age = int ( s.split()[1] )

Слайд 163

Обработка строк Fin = open ( "input.txt" ) Fout = open

Обработка строк

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

Полная программа:

Слайд 164

Обработка строк lst = Fin.readlines() for s in lst: age =

Обработка строк

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 )

или так:

Слайд 165

Задачи «A»: В файле записаны данные о результатах сдачи экзамена. Каждая

Задачи

«A»: В файле записаны данные о результатах сдачи экзамена. Каждая строка

содержит фамилию, имя и количество баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл фамилии и имена тех учеников, которые получили больше 80 баллов.
«B»: В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией:
П. Иванов
И. Петров
...
Слайд 166

Задачи «C»: В файле записаны данные о результатах сдачи экзамена. Каждая

Задачи

«C»: В файле записаны данные о результатах сдачи экзамена. Каждая строка

содержит фамилию, имя и количество баллов, разделенные пробелами:
<Фамилия> <Имя> <Количество баллов>
Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных:
П. Иванов 98
И. Петров 96
...
Слайд 167

Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ №

Конец фильма

ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
kpolyakov@mail.ru

ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
eremin@pspu.ac.ru
- Предыдущая
Соединения щелочных металлов
Следующая -
Мастер-класс по выполнению задания № 21

Похожие презентации

Электронные презентации
ОГЛАВЛЕНИЕ Разделы Страницы День 1 1.0 Введение в MSC.Mvision Builder and Evaluator MSC.Mvision – база данных, содержащая свойства материалов……………………………………………………………………………………………… Компоненты MSC.Mvision………………………………………………
Дети в интернете. Как не попасть в сети?
Что такое компьютер? Обзорный урок
VebMast. Установка
9.34перевод из 2 в 2n
Регрессионный анализ
Знакомство с языком программирования Python. Ввод. Вывод. Оператор присваивания. Математические операции
Редактирование, добавление и удаление записей в таблице СУБД MySQL
Цифровые видеокамеры Цифровая видеокамера - устройства для записи и сохранение видео данных в цифровой форме
Системы счисления
DAS, NAS, SAS. Обзор дисковых интерфейсов и архитектур
Профессия Журналист
Подключение ПК, периферийного и мультимедийного оборудования к электросети, запуск оборудования. Урок 21
Разработка и администрирование баз данных
Фундаментальные типы данных и операции. С / С++. Тема 06
Презентация "Программное обеспечение. Сжатие файлов. Архиваторы" - скачать презентации по Информатике
Информационные материалы для абитуриентов и студентов профессиональных образовательных организаций о состоянии рынка труда
Безопасность Linux
Программа подготовки презентаций и просмотра презентаций
Презентация "Создание запросов в базе данных OpenOffice.org Base" - скачать презентации по Информатике
Основные понятия языка программирования. Структура ЯВУ
Quick Start Software Training
What is the Internet
Творческий проект по информатике. Новогодняя анимация
Способы организации поддержки устройств, драйверы оборудования. Схема подключения. (Лекция 10)
Распределенные системы LSM-Tree
ОЦЕНКА ЭФФЕКТИВНОСТИ ЭЛЕКТРОННОЙ КОММЕРЦИИ Подготовила Плотникова Виктория
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть