Массивы и последовательности чисел
Основы работы с массивами
Массив — это структура данных, содержащая набор элементов одного типа, доступ к которым осуществляется по индексу. В Python массивы часто представляются списками (list).
Обобщённые характеристики массива
1 Сумма и произведение
def array_sum(arr):
total = 0
for num in arr:
total += num
return total
def array_product(arr):
product = 1
for num in arr:
product *= num
return product
# Пример использования
numbers = [2, 4, 6, 8]
print("Сумма:", array_sum(numbers)) # 20
print("Произведение:", array_product(numbers)) # 3842 Среднее арифметическое
def array_average(arr):
if len(arr) == 0:
return 0
return sum(arr) / len(arr)
# Или с использованием нашей функции суммы
def array_average_v2(arr):
if len(arr) == 0:
return 0
return array_sum(arr) / len(arr)
# Пример использования
numbers = [5, 10, 15, 20, 25]
print("Среднее арифметическое:", array_average(numbers)) # 15.03 Минимум и максимум
def array_min(arr):
if len(arr) == 0:
return None
min_val = arr[0]
for num in arr:
if num < min_val:
min_val = num
return min_val
def array_max(arr):
if len(arr) == 0:
return None
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
# Пример использования
numbers = [34, 12, 78, 5, 42]
print("Минимальный элемент:", array_min(numbers)) # 5
print("Максимальный элемент:", array_max(numbers)) # 784 Количество по условию
def count_condition(arr, condition):
count = 0
for num in arr:
if condition(num):
count += 1
return count
# Пример использования: подсчет четных чисел
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
even_count = count_condition(numbers, lambda x: x % 2 == 0)
print("Количество четных чисел:", even_count) # 5
# Пример: подсчет чисел больше 5
greater_than_5 = count_condition(numbers, lambda x: x > 5)
print("Количество чисел > 5:", greater_than_5) # 5Поиск в массиве
Линейный поиск
Последовательный перебор всех элементов массива до нахождения нужного:
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # возвращаем индекс найденного элемента
return -1 # элемент не найден
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
target = 22
result = linear_search(numbers, target)
if result != -1:
print(f"Элемент {target} найден на позиции {result}")
else:
print(f"Элемент {target} не найден в массиве")64
34
25
12
22
11
90
Линейный поиск элемента 22 в массиве
Двоичный поиск
Быстрый поиск в отсортированном массиве путем деления пополам:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid # элемент найден
elif arr[mid] < target:
left = mid + 1 # ищем в правой половине
else:
right = mid - 1 # ищем в левой половине
return -1 # элемент не найден
# Пример использования (массив должен быть отсортирован)
numbers = [11, 12, 22, 25, 34, 64, 90]
target = 22
result = binary_search(numbers, target)
if result != -1:
print(f"Элемент {target} найден на позиции {result}")
else:
print(f"Элемент {target} не найден в массиве")11
12
22
25
34
64
90
Двоичный поиск в отсортированном массиве
Простые методы сортировки
Сортировка пузырьком
Многократное прохождение по массиву с сравнением и обменом соседних элементов:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Последние i элементов уже на месте
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# Меняем элементы местами
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers.copy())
print("Отсортированный массив:", sorted_numbers)64
34
25
12
22
11
90
Визуализация сортировки пузырьком
Сортировка выбором
Поиск минимального элемента и помещение его на правильную позицию:
def selection_sort(arr):
n = len(arr)
for i in range(n):
# Находим минимальный элемент в оставшейся части
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Меняем найденный минимальный элемент с первым элементом
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = selection_sort(numbers.copy())
print("Отсортированный массив:", sorted_numbers)Сортировка вставками
Построение отсортированного массива путем вставки элементов на правильные позиции:
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
# Перемещаем элементы arr[0..i-1], которые больше key
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = insertion_sort(numbers.copy())
print("Отсортированный массив:", sorted_numbers)Быстрая сортировка (QuickSort)
Эффективный алгоритм сортировки с использованием стратегии "разделяй и властвуй":
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # выбираем опорный элемент
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = quicksort(numbers.copy())
print("Отсортированный массив:", sorted_numbers)Сортировка слиянием
Алгоритм сортировки, основанный на принципе "разделяй и властвуй" с операцией слияния:
def merge_sort(arr):
if len(arr) <= 1:
return arr
# Разделяем массив на две половины
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Рекурсивно сортируем каждую половину
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
# Сливаем отсортированные половины
return merge(left_sorted, right_sorted)
def merge(left, right):
result = []
i = j = 0
# Сливаем два массива, выбирая меньший элемент
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Добавляем оставшиеся элементы
result.extend(left[i:])
result.extend(right[j:])
return result
# Пример использования
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = merge_sort(numbers.copy())
print("Отсортированный массив:", sorted_numbers)Сравнение алгоритмов сортировки
| Алгоритм | Сложность (в среднем) | Сложность (в худшем) | Память |
|---|---|---|---|
| Пузырьковая | O(n²) | O(n²) | O(1) |
| Выбором | O(n²) | O(n²) | O(1) |
| Вставками | O(n²) | O(n²) | O(1) |
| Быстрая | O(n log n) | O(n²) | O(log n) |
| Слиянием | O(n log n) | O(n log n) | O(n) |
Заключение
Работа с массивами и последовательностями чисел — фундаментальная тема в программировании и важная часть ЕГЭ по информатике. Понимание основных алгоритмов обработки массивов, методов поиска и сортировки необходимо для успешного решения задач.
При выборе алгоритма важно учитывать его временную сложность и требования к памяти, а также особенности конкретной задачи.