ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.12.2023
Просмотров: 416
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
§ 63. Алгоритмы обработки массивов
§ 63. Алгоритмы обработки массивов
Срезы в Python – отрицательные индексы
Особенности работы со списками
Метод пузырька (сортировка обменами)
Быстрая сортировка (QuickSort)
Сортировка в Python – на месте
Преобразования «строка» – «число»
Пример:
Массив:
1 2 3 4 5
Минимальный элемент: A[1]=1
Максимальный элемент: A[5]=5
«B»: Заполнить массив случайными числами и найти два максимальных элемента массива и их номера.
Пример:
Массив:
5 5 3 4 1
Максимальный элемент: A[1]=5
Второй максимум: A[2]=5
Задачи
«C»: Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение.
Пример:
Массив:
3 4 5 5 3 4 5
Максимальное значение 5
Количество элементов 3
Реверс массива
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | |
| 7 | 12 | 5 | 8 | 18 | 34 | 40 | 23 |
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | |
| 23 | 40 | 34 | 18 | 8 | 5 | 12 | 7 |
«Простое» решение:
for i in range( N ):
поменять местами A[i] и A[N-1-i]
N//2
Что плохо?
?
остановиться на середине!
Реверс массива
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()
Циклический сдвиг элементов
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | |
| 12 | 5 | 8 | 15 | 34 | 40 | 23 | 7 |
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | |
| 7 | 12 | 5 | 8 | 18 | 34 | 40 | 23 |
«Простое» решение:
c = A[0]
for i in range(N-1):
A[i] = A[i+1]
A[N-1] = c
Что плохо?
?
Почему не до N?
?
Срезы в Python
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | |
| 7 | 12 | 5 | 8 | 18 | 34 | 40 | 23 |
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | N |
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]
копия массива
Срезы в Python – отрицательные индексы
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | |
| 7 | 12 | 5 | 8 | 18 | 34 | 40 | 23 |
| 0 | 1 | 2 | 3 | N-4 | N-3 | N-2 | N-1 | N |
A[1:-1]
[12,5,8,…,18,34,40]
разрезы
A[1:N-1]
A[-4:-2]
[18, 34]
A[N-4:N-2]
Срезы в Python – шаг
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 7 | 12 | 5 | 8 | 76 | 18 | 34 | 40 | 23 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
A[1:6:2]
[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()
шаг
Задачи
«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
Задачи
«C»: Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов.
Пример:
Массив:
20 -90 15 -34 10 0
Результат:
20 15 10 -90 -34 0
Количество положительных элементов: 3
Отбор нужных элементов
Простое решение:
Задача. Отобрать элементы массива 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
Какие элементы выбираем?
?
Отбор нужных элементов
Решение в стиле Python:
Задача. Отобрать элементы массива A, удовлетворяющие некоторому условию, в массив B.
B = [ x for x in A ]
if x % 2 == 0 ]
если x – чётное число
перебрать все элементы A
Задачи
«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
Задачи
«C»: Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи.
Пример:
Массив А:
12 13 85 34 47
Массив B:
13 34
Особенности работы со списками
A = [1, 2, 3]
B = A
[1, 2, 3]
A
B
A[0] = 0
[0, 2, 3]
A
B
A = [1, 2, 3]
B = A[:]
копия массива A
[1, 2, 3]
A
[1, 2, 3]
B
A[0] = 0
[0, 2, 3]
A
[1, 2, 3]
B
Копирование списков
[1,2,3]
A
[4,5,6]
B
[A,B]
C
[A,B]
D
«Поверхностное» копирование:
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
[1,2,3]
A
[4,5,6]
B
0
A
Влияет на C и D!
!
«Глубокое» копирование:
D = copy.deepcopy(C)
[A,B]
C
[∙,∙]
D
[1,2,3]
A
[4,5,6]
B
[1,2,3]
[4,5,6]