Конспект

Массивы (списки) и алгоритмы в Python

Ключевые тезисы

• Программирование — это в первую очередь алгоритмы, а не синтаксис конкретного языка.
• Массив (список) — это контейнер для хранения множества данных под одним именем.
• В Python используется ссылочная модель данных: есть изменяемые и неизменяемые объекты.
• Для изменения элементов массива необходим доступ по индексу, а не через переменную в цикле for.
• Важно тестировать функции, чтобы гарантировать их корректность.

Основное содержание

Что такое массив (список)

Массив (в контексте — тип list) — это способ хранения множества данных под одним именем.

• Элементы в массиве обычно имеют одинаковый тип (например, целые числа).
• У элементов нет собственных имён, но к ним можно обратиться по индексу.
• Индексация начинается с 0.

Пример создания:

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

Модель данных в Python

В Python есть изменяемые (mutable) и неизменяемые (immutable) объекты.

• Неизменяемые: целые числа (int), числа с плавающей точкой (float), строки. Их значение нельзя изменить.
• Изменяемые: списки (list). Их внутреннее состояние можно менять.

Ключевой момент: Операция x += 1 для целого числа не меняет сам объект 1, а создаёт новый объект 2 и перенаправляет на него имя x.

Цикл for и изменение элементов

При переборе массива for x in a: переменная x становится альтернативным именем для элемента, но это не ссылка на ячейку массива.

• x = x * 2 — создаст новый объект, но не изменит элемент в массиве.
• Для изменения элемента массива нужен доступ по индексу.

Правильный способ изменить элементы (например, возвести в квадрат):

for i in range(len(a)):
    a[i] = a[i] * a[i]

Работа с массивом: заполнение и индексы

Создание массива заданного размера:

a = [0] * 1000  # Массив из 1000 нулей

Контроль заполненности: Используется дополнительная переменная (например, top), которая указывает на индекс, куда будет помещён следующий элемент, и равна количеству реально хранящихся элементов.

Пример: Считать последовательность чисел до 0 и вывести её в обратном порядке.

a = [0] * 1000
top = 0
x = int(input())
while x != 0:
    a[top] = x
    top += 1
    x = int(input())

# Вывод в обратном порядке
for i in range(top-1, -1, -1):
    print(a[i])

Ссылочная модель и копирование массивов

Присваивание b = a не создаёт копию списка. Обе переменные (a и b) начинают ссылаться на один и тот же изменяемый объект.

• Изменение через a[0] = 777 также изменит b[0].

Способы создания копии списка:

1. Поэлементное копирование:

b = [0] * n
for i in range(n):
    b[i] = a[i]

2. Использование конструктора list():

c = list(a)  # Создаёт новый список — копию `a`

Алгоритмы работы с массивами

Линейный поиск

Функция ищет число x в массиве a в диапазоне индексов [0, n-1].

Протокол функции:

• Возвращает индекс первого найденного элемента.
• Если элемент не найден, возвращает -1.
• Если одинаковых элементов несколько, возвращает индекс первого из них.

Пример заголовка функции с аннотацией типов:

def ray_search(a: list, n: int, x: int) -> int:

Инверсия (обращение) массива

Алгоритм меняет порядок элементов в массиве на противоположный в том же массиве (in-place).

Ключевая идея: Менять местами элементы с противоположных концов, двигаясь к середине.

def invert_ray(a: list, n: int):
    for i in range(n // 2):  # Идём до середины
        # Обмен значений
        a[i], a[n-1-i] = a[n-1-i], a[i]

Циклический сдвиг

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

Решето Эратосфена

Алгоритм для нахождения всех простых чисел до заданного n.

• Создаётся массив логических значений (True/False), где индекс соответствует числу.
• Изначально все числа, кроме 0 и 1, помечаются как простые (True).
• Для каждого числа i, начиная с 2, если оно простое, то все его кратные отмечаются как составные (False).

Пример фрагмента кода:

n = 100
is_prime = [True] * n
is_prime[0] = is_prime[1] = False

for k in range(2, n):
    if is_prime[k]:  # Если число простое
        for m in range(2*k, n, k):  # Отмечаем кратные
            is_prime[m] = False

# Вывод результатов с тернарным оператором
for k in range(n):
    print(k, '-', 'простое' if is_prime[k] else 'составное')

Выводы

• Для работы с данными в Python необходимо понимать разницу между изменяемыми и неизменяемыми типами и ссылочную модель.
• Доступ по индексу — основной способ модификации элементов массива.
• Создание тестов для функций — важная практика, обеспечивающая надёжность и соответствие кода заявленному протоколу (интерфейсу).
• Базовые алгоритмы (поиск, инверсия, сдвиг, решето) — фундамент для решения более сложных задач.