ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.12.2023
Просмотров: 410
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
§ 63. Алгоритмы обработки массивов
§ 63. Алгоритмы обработки массивов
Срезы в Python – отрицательные индексы
Особенности работы со списками
Метод пузырька (сортировка обменами)
Быстрая сортировка (QuickSort)
Сортировка в Python – на месте
Преобразования «строка» – «число»
§ 62. Массивы
§ 63. Алгоритмы обработки массивов
§ 64. Сортировка
§ 65. Двоичный поиск
§ 66. Символьные строки
§ 67. Матрицы
§ 68. Работа с файлами
§ 62. Массивы
Что такое массив?
Массив – это группа переменных одного типа, расположенных в памяти рядом (в соседних ячейках) и имеющих общее имя. Каждая ячейка в массиве имеет уникальный номер (индекс).
Надо:
Как ввести 10000 переменных?
?
- выделять память
- записывать данные в нужную ячейку
- читать данные из ячейки
Что такое массив?
| 5 | 10 | 15 | 20 | 25 |
| 0 | 1 | 2 | 3 | 4 |
A
массив
2
15
НОМЕР элемента массива
(ИНДЕКС)
A[0]
A[1]
A[2]
A[3]
A[4]
ЗНАЧЕНИЕ элемента массива
A[2]
НОМЕР (ИНДЕКС) элемента массива: 2
ЗНАЧЕНИЕ элемента массива: 15
Массив = таблица!
!
Массивы в 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]
Генераторы списков
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)
случайные числа
условие отбора
Создание массива:
Обработка:
N = 5
A = [0]*N
# обработать A[0]
# обработать A[1]
# обработать A[2]
# обработать A[3]
# обработать A[4]
1) если N велико (1000, 1000000)?
2) при изменении N программа не должна меняться!
?
Обработка с переменной:
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]
Создание массива:
Ввод с клавиатуры:
N = 10
A = [0]*N
for i in range(N):
print ( "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 = ""
не разделять элементы
не переходить на новую строку
Ввод без подсказок:
Ввод в одной строке:
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
построить список
Вывод массива на экран
Как список:
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)
Заполнение случайными числами
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)
или так:
Перебор элементов
Общая схема (можно изменять 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 )
Подсчёт нужных элементов
Задача. В массиве записаны данные о росте баскетболистов. Сколько из них имеет рост больше 180 см, но меньше 190 см?
count = 0
for x in A:
if 180 < x and x < 190:
count += 1
Как решать?
?
Python:
180 < x < 190
Перебор элементов
Сумма:
summa = 0
for x in A:
if 180 < x < 190:
summa += x
print ( summa )
print ( sum(A) )
или так:
Перебор элементов
Среднее арифметическое:
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) )
отбираем нужные
Задачи
«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
Задачи
«C»: Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку).
Пример:
Массив:
3 2 1 4 5
§ 63. Алгоритмы обработки массивов
Поиск в массиве
Найти элемент, равный X:
i = 0
while A[i] != X:
i += 1
print ( "A[", i, "]=", X, sep = "" )
Что плохо?
?
i = 0
while i < N and A[i] != X:
i += 1
if i < N:
print ( "A[", i, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
Что если такого нет?
?
i < N
Поиск в массиве
nX = -1
for i in range ( N ):
if A[i] == X:
nX = i
break
if nX >= 0:
print ( "A[", nX, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
Вариант с досрочным выходом:
break
досрочный выход из цикла
номер найденного элемента
Поиск в массиве
for i in range ( N ):
if A[i] == X:
print ( "A[", i, "]=", X, sep = "" )
break
else:
print ( "Не нашли!" )
Варианты в стиле Python:
если не было досрочного выхода из цикла
if X in A:
nX = A.index(X)
print ( "A[", nX, "]=", X, sep = "" )
else:
print ( "Не нашли!" )
Задачи
«A»: Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X.
Пример:
Массив:
1 2 3 1 2
Что ищем:
2
Нашли: A[2]=2, A[5]=2
Пример:
Массив:
1 2 3 1 2
Что ищем:
6
Ничего не нашли.
Задачи
«B»: Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом.
Пример:
Массив:
1 2 3 3 2 1
Есть: 3
Пример:
Массив:
1 2 3 4 2 1
Нет
Задачи
«C»: Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом.
Пример:
Массив:
3 2 1 3 2 5
Есть: 3, 2
Пример:
Массив:
3 2 1 4 0 5
Нет
Максимальный элемент
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 )
Если range(N)?
?
M = A[0]; nMax = 0
for i in range(1,N):
if A[i] > M:
M = A[i]
nMax = i
print ( "A[", nMax, "]=", M, sep = "" )
nMax = 0
nMax = i
Что можно улучшить?
?
По номеру элемента можно найти значение!
!
M = max(A)
nMax = A.index(M)
print ( "A[", nMax, "]=", M, sep = "" )
Вариант в стиле Python:
номер заданного элемента (первого из…)
Задачи
«A»: Заполнить массив случайными числами и найти минимальный и максимальный элементы массива и их номера.