💡 Определение

Массив — это набор элементов одного типа, которым присвоено общее имя. Каждый элемент массива имеет свой номер (индекс).

🎮 Пример из жизни

Ты создаёшь команду для онлайн-игры и сохраняешь никнеймы игроков. Вместо:

player1 = "DragonSlayer"
player2 = "NinjaKid"
player3 = "ProGamer"

Ты используешь массив:

players = ["DragonSlayer", "NinjaKid", "ProGamer"]

Круто же? Один объект вместо трёх!

🐍 Python и массивы

Важно! В Python нет "настоящих" массивов в классическом понимании. Вместо них используются списки (list) — более гибкая структура. Но для простоты мы будем называть их массивами, помня, что говорим о списках.

⚠️ Очень важно!

Нумерация элементов массива в Python всегда начинается с нуля.

📏 Длина массива

Количество элементов массива определяется функцией len():

N = len(A)  # N = 8

Как правило, длину массива хранят в отдельной переменной:

N = 8

Создать массив можно перечислением элементов через запятую в квадратных скобках:

A = [1, 2, -3, 5, 7]

С помощью записи A = [0]*5 будет создан массив из пяти элементов, каждый из которых равен 0.

Небольшие массивы можно вводить с клавиатуры. Для этого используется цикл с параметром:

N = 5
A = [0]*N
for i in range(N):
    A[i] = int(input())

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

for i in range(N):
    print("A[{}]=".format(i), end="\n")
    A[i] = int(input())

Задавать значения элементов массива можно по формуле:

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

Для работы со случайными числами нужно подключить функцию randint:

from random import randint

Далее можно использовать цикл с параметром:

for i in range(N):
    A[i] = randint(10, 110)

Массив A из N элементов будет заполнен случайными числами из отрезка [10, 110].

Самый простой способ — вывести массив как один объект:

print(A)

В этом случае весь массив выводится в квадратных скобках, а его элементы разделяются запятыми.

Можно вывести элементы массива на экран в строку:

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

Параметр end определяет, что после вывода каждого элемента добавляется пробел.

Значения элементов массива можно вывести в столбик:

for i in range(len(A)):
    print(A[i])

Более наглядный вариант — вывод с комментариями:

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

N = 10                        # Создание массива
A = [0]*N

from random import randint    # Подключение генератора 
                              # случайных чисел

for i in range(N):            # Заполнение массива
    A[i] = randint(0, 99)
    
for i in range(N):            # Вывод массива
    print('A[',i,']=', A[i])

💻 Выполните эту программу на компьютере!

В некотором населённом пункте N домов. Известно, сколько людей проживает в каждом из домов. Составим алгоритм подсчёта числа жителей населённого пункта.

Исходные данные: одномерный массив A, содержащий N элементов:

• A[0] — число жильцов дома 1
• A[1] — число жильцов дома 2
• A[N-1] — число жильцов дома N

💡 Принцип суммирования

Суммирование элементов массива осуществляется по тому же принципу, что и суммирование значений простых переменных: за счёт поочерёдного добавления слагаемых.

N = 10                        # Создание массива
A = [0]*N

from random import randint    # Подключение генератора
                              # случайных чисел

for i in range(N):            # Заполнение массива
    A[i] = randint(50, 200)
    
for i in range(N):            # Вывод массива
    print('A[',i,']=', A[i])

s = 0                         # Вычисление суммы
for i in range(N):            # элементов массива
    s += A[i]
    
print('s=', s)                # Вывод результата

✏️ Задание для размышления

💻 Выполните программу на компьютере, считая число жильцов дома случайным числом из диапазона от 50 до 200 человек, а число домов N = 30.

🤔 Вы уже составляли программу, получавшую на вход количество чисел N и последовательности, а затем сами эти числа и вычисляющую сумму введённых чисел. Воспроизведите эту программу. Сравните её с программой суммирования элементов массива с точки зрения процессов, происходящих в памяти. Что у них общее? В чём отличие? Обсудите этот вопрос в группе.

🎯Типовые задачи поиска

1. Найти наибольший (наименьший) элемент массива
2. Найти элемент массива, значение которого равно заданному значению
3. Найти количество (сумму) элементов массива, удовлетворяющих заданному условию

Для решения таких задач в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.

💭 Идея алгоритма (метод карточек)

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

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

В итоге на доске будет записано самое большое значение элемента просмотренного массива.

🔄 Инвариант цикла

Инвариант цикла — логическое выражение (условие), зависящее от переменных, изменяющихся в теле цикла; оно истинно непосредственно перед началом выполнения цикла и после каждого прохода тела цикла.

Условие «записанное на доске число — самое большое из всех просмотренных до сих пор» является инвариантом цикла для рассмотренного алгоритма.

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

N = 10                           # Создание массива
A = [0]*N

from random import randint       # Подключение генератора
                                 # случайных чисел

for i in range(N):               # Заполнение и вывод
    A[i] = randint(0,99)         # массива
    print('A[',i,']=',A[i])

imax = 0                         # Поиск индекса
for i in range(1,N):             # наибольшего элемента
    if A[i] > A[imax]: 
        imax = i

print('Наибольший элемент:', A[imax])  # Вывод результата

❓ Задания для размышления

• Если в массиве несколько элементов, значения которых равны максимальному значению, то данная программа найдёт первый из них (первое вхождение). Подумайте, что следует изменить в программе, чтобы она находила последний из максимальных элементов.
• Как следует преобразовать программу, чтобы с её помощью можно было найти минимальный элемент массива?
• Проверьте свои предположения на компьютере.

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

• k — индекс элемента массива такой, что A[k] = x, где x — заданное число
• Сообщение о том, что искомого элемента в массиве не обнаружено

N = 10                           # Создание массива
A = [0]*N

from random import randint       # Подключение генератора
                                 # случайных чисел

for i in range(N):               # Заполнение и вывод
    A[i] = randint(0,99)         # массива
    print('A[',i,']=',A[i])

x = int(input('x='))             # Ввод значения x

nx = -1                          # Поиск индекса элемента,
for i in range(0,N):             # равного x
    if A[i] == x: 
        nx = i

if nx == -1:                     # Вывод результата
    print('Нет')
else:
    print('nx=', nx)

В этой программе последовательно просматриваются все элементы массива. Номер найденного элемента сохраняется в переменной nx. Начальное значение, присваиваемое этой переменной, заведомо не совпадает ни с одним из значений индексов элементов массива. Если значение переменной nx не изменилось в ходе выполнения цикла и осталось равным -1, то это означает, что в массиве нет элемента, равного x.

Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдёт последний из них. Во многих случаях требуется найти первый из элементов, имеющих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующий фрагмент программы:

nx = -1
for i in range(N):
    if A[i] == x:
        nx = i
        break

if nx >= 0:
    print('A[{}]={}'.format(nx,x))
else:
    print('Элемент не найден')

Используя цикл с параметром, мы начали последовательный перебор элементов массива и завершим его досрочно, как только будет найдено требуемое значение. Для выхода из цикла используется оператор break.

Здесь выполнение алгоритма будет завершено (прервано) в одном из двух случаев:

1. В массиве найден первый из элементов, равный заданному
2. Все элементы массива просмотрены

❓ Задания

• В чём ещё отличие первого варианта программы от второго? Запишите полные тексты двух вариантов программы. Выполните программы на компьютере.

Зачастую требуется определить количество элементов, удовлетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.

k = 0
for i in range(10):
    if A[i]%2 == 0: 
        k += 1
print('k=', k)

Подсказка: оператор % вычисляет остаток от деления.

Если требуется определить сумму значений элементов, удовлетворяющих некоторому условию, то вводят переменную, к значению которой прибавляют значение найденного элемента массива.

s = 0
for i in range(10):
    if A[i]%2 == 0 and A[i]%10 == 4: 
        s += A[i]
print('s=', s)

Подсказка: какие числа одновременно чётные И оканчиваются на 4?

💻 Задание

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

🎯 Цель сортировки

Облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.

Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:

1. В массиве выбирается максимальный элемент
2. Максимальный и первый элементы меняются местами, после чего первый элемент считается отсортированным
3. В неотсортированной части массива снова выбирается максимальный элемент; он и первый неотсортированный элемент массива меняются местами
4. Действия, описанные в п. 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным)

❓ Вопрос

В этом массиве из 8 элементов операцию выбора максимального элемента мы проводили 7 раз. В массиве из N элементов такая операция будет проводиться N - 1 раз. Объясните почему.

Приведём фрагмент программы, реализующий описанный алгоритм:for i in range(N-1): imax = i for j in range(i+1, N): if A[j] > A[imax]: imax = j A[i], A[imax] = A[imax], A[i]

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

💻 Задания

• Запишите полный текст программы и выполните её на компьютере для рассмотренного в примере массива А.
• Разработайте подпрограмму max для поиска максимального из двух элементов массива.
• Модифицируйте программу сортировки выбором, использовав в ней эту подпрограмму.

Камера наблюдения, установленная в населённом пункте, регистрирует в автоматическом режиме скорость проезжающих мимо неё автомобилей, округляя полученные значения до целых чисел. Программа, которую вам необходимо составить, получает на вход скорости проехавших N ⩽ 100 автомобилей. Программа должна анализировать скорость каждого автомобиля и один раз в сутки выводить на экран следующую информацию:

1. Количество автомобилей, проехавших со скоростью, превышающей 60 км/ч
2. Максимальную скорость проехавших автомобилей
3. Количество автомобилей, проехавших с максимальной скоростью
4. Среднюю скорость проехавших автомобилей
5. Количество автомобилей, проехавших со скоростью ниже средней
6. Для каждого проехавшего автомобиля его скорость и комментарий:
   • «Нарушитель», если скорость превышает 60 км/ч, но не превышает 250 км/ч
   • «Дисциплинированный водитель», если скорость от 30 до 60 км/ч
   • «Тише едешь — дальше будешь!», если скорость меньше 30 км/ч
   • «Ошибка», если значение скорости меньше 1 или больше 250

❓ Задания для размышления

• Для получения каких из требуемых результатов можно организовать обработку последовательности? Какие результаты можно получить, организовав обработку массива?
• Напишите программу, решающую поставленную задачу.