← Назад к курсу
Решение различных задач на Python (2 часть)
Задача 21: Проверка на совершенное число
Принцип решения: Найти все делители числа (кроме самого числа) и проверить их сумму
Что используется: Цикл, математические операции, проверка делителей
def is_perfect_number(n: int) -> bool:
"""Проверяет, является ли число совершенным."""
if n <= 1:
return False
divisors_sum = 1 # 1 всегда делитель
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
divisors_sum += i
if i != n // i: # Добавляем парный делитель, если он не равен i
divisors_sum += n // i
return divisors_sum == n
# Пояснение: Совершенное число равно сумме своих собственных делителей.
# Пример: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14
# Проверяем делители до √n, находим парные делители.
Задача 22: Вычисление числа π методом Монте-Карло
Принцип решения: Генерация случайных точек в квадрате и подсчет точек внутри четверти круга
Что используется: Библиотека random, математические операции, статистика
import random
def estimate_pi(num_points: int) -> float:
"""Оценивает число π методом Монте-Карло."""
points_inside = 0
for _ in range(num_points):
x = random.random() # [0, 1)
y = random.random() # [0, 1)
# Проверяем, попадает ли точка в четверть круга радиусом 1
if x**2 + y**2 <= 1:
points_inside += 1
# Площадь четверти круга / площадь квадрата = π/4
return 4 * points_inside / num_points
# Пояснение: Отношение точек внутри четверти круга к общему числу точек ≈ π/4
# Чем больше точек, тем точнее оценка. Нужно ≈ 1 млн точек для точности 0.001
Задача 23: Решето Эратосфена для поиска простых чисел
Принцип решения: Последовательное вычеркивание составных чисел
Что используется: Список булевых значений, вложенные циклы
def sieve_of_eratosthenes(n: int) -> list:
"""Находит все простые числа до n с помощью решета Эратосфена."""
if n < 2:
return []
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# Вычеркиваем все кратные i, начиная с i²
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
# Пояснение: Алгоритм последовательно помечает кратные каждого простого числа как составные.
# Начинаем с i=2, вычеркиваем 4,6,8... затем i=3, вычеркиваем 9,12,15...
# Оптимизация: начинаем вычеркивать с i², так как меньшие кратные уже вычеркнуты.
Задача 24: Числа Армстронга (нарциссические числа)
Принцип решения: Сумма цифр в степени количества цифр равна самому числу
Что используется: Преобразование числа в строку, возведение в степень
def is_armstrong_number(n: int) -> bool:
"""Проверяет, является ли число числом Армстронга."""
if n < 0:
return False
digits = str(n)
power = len(digits)
total = sum(int(digit)**power for digit in digits)
return total == n
# Пояснение: Число Армстронга: сумма его цифр, возведенных в степень количества цифр, равна самому числу.
# Пример: 153 = 1³ + 5³ + 3³ = 1 + 125 + 27 = 153
# 9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474
Задача 25: Конвертация числа в римскую систему счисления
Принцип решения: Последовательное вычитание максимальных возможных римских значений
Что используется: Словарь соответствий, цикл while
def int_to_roman(num: int) -> str:
"""Конвертирует целое число в римскую запись."""
roman_numerals = [
(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD'),
(100, 'C'), (90, 'XC'), (50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'), (5, 'V'), (4, 'IV'), (1, 'I')
]
result = []
for value, symbol in roman_numerals:
while num >= value:
result.append(symbol)
num -= value
return ''.join(result)
# Пояснение: Римская система использует вычитательную нотацию (IV = 4, IX = 9).
# Проходим от больших значений к меньшим, вычитая максимально возможные.
# Пример: 1994 → 1000(M) + 900(CM) + 90(XC) + 4(IV) = MCMXCIV
Задача 26: Конвертация римского числа в арабское
Принцип решения: Обработка символов слева направо с учетом вычитательной нотации
Что используется: Словарь значений, проверка следующего символа
def roman_to_int(s: str) -> int:
"""Конвертирует римскую запись в целое число."""
roman_values = {
'I': 1, 'V': 5, 'X': 10, 'L': 50,
'C': 100, 'D': 500, 'M': 1000
}
total = 0
i = 0
while i < len(s):
# Если текущий символ меньше следующего, это вычитательная нотация
if i + 1 < len(s) and roman_values[s[i]] < roman_values[s[i + 1]]:
total += roman_values[s[i + 1]] - roman_values[s[i]]
i += 2
else:
total += roman_values[s[i]]
i += 1
return total
# Пояснение: IV = 4 (5 - 1), IX = 9 (10 - 1), XL = 40 (50 - 10) и т.д.
# Если меньшая цифра стоит перед большей, вычитаем ее значение.
# Иначе складываем значения символов.
Задача 27: Проверка валидности email-адреса
Принцип решения: Проверка структуры с использованием регулярных выражений
Что используется: Модуль re (регулярные выражения)
import re
def is_valid_email(email: str) -> bool:
"""Проверяет валидность email-адреса."""
pattern = r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
return bool(re.match(pattern, email))
# Пояснение: Регулярное выражение проверяет:
# 1. Локальная часть: буквы, цифры, ., _, %, +, -
# 2. Символ @
# 3. Доменное имя: буквы, цифры, ., -
# 4. Точка и домен верхнего уровня (минимум 2 буквы)
# Пример валидных: user@example.com, name.last@sub.domain.org
Задача 28: Генерация случайного пароля
Принцип решения: Выбор случайных символов из разных наборов
Что используется: Библиотеки random и string
import random
import string
def generate_password(length: int = 12) -> str:
"""Генерирует случайный пароль заданной длины."""
if length < 4:
raise ValueError("Пароль должен быть минимум 4 символа")
# Наборы символов
lowercase = string.ascii_lowercase
uppercase = string.ascii_uppercase
digits = string.digits
special = "!@#$%^&*"
# Гарантируем минимум по одному символу из каждой категории
password = [
random.choice(lowercase),
random.choice(uppercase),
random.choice(digits),
random.choice(special)
]
# Добавляем остальные символы случайным образом
all_chars = lowercase + uppercase + digits + special
password.extend(random.choice(all_chars) for _ in range(length - 4))
# Перемешиваем для случайного порядка
random.shuffle(password)
return ''.join(password)
# Пояснение: Создаем пароль, гарантируя наличие разных типов символов.
# Перемешиваем результат для большей случайности.
# Длина по умолчанию 12 символов считается безопасной.
Задача 29: ROT13 шифрование
Принцип решения: Сдвиг букв на 13 позиций в алфавите
Что используется: Строковые операции, арифметика символов
def rot13(text: str) -> str:
"""Применяет шифр ROT13 к тексту."""
result = []
for char in text:
if 'a' <= char <= 'z':
# Сдвиг для строчных букв
result.append(chr((ord(char) - ord('a') + 13) % 26 + ord('a')))
elif 'A' <= char <= 'Z':
# Сдвиг для заглавных букв
result.append(chr((ord(char) - ord('A') + 13) % 26 + ord('A')))
else:
# Оставляем другие символы без изменений
result.append(char)
return ''.join(result)
# Пояснение: ROT13 - частный случай шифра Цезаря со сдвигом 13.
# Особенность: ROT13 обратим сам к себе (двойное применение дает исходный текст).
# Пример: rot13("Hello") = "Uryyb", rot13("Uryyb") = "Hello"
Задача 30: Проверка на счастливый билет
Принцип решения: Сравнение суммы первых трех цифр с суммой последних трех
Что используется: Преобразование числа в строку, сумма цифр
def is_lucky_ticket(ticket: int) -> bool:
"""Проверяет, является ли билет счастливым (суммы половин равны)."""
# Форматируем с ведущими нулями
ticket_str = f"{ticket:06d}"
if len(ticket_str) != 6:
return False
first_half = sum(int(digit) for digit in ticket_str[:3])
second_half = sum(int(digit) for digit in ticket_str[3:])
return first_half == second_half
# Пояснение: Счастливый билет - когда сумма первых трех цифр равна сумме последних трех.
# Пример: 123456 → 1+2+3 = 6, 4+5+6 = 15 → не счастливый
# 123321 → 1+2+3 = 6, 3+2+1 = 6 → счастливый
Задача 31: Упаковка и распаковка последовательных элементов (RLE)
Принцип решения: Кодирование последовательных одинаковых символов
Что используется: Цикл по строке, подсчет последовательностей
def rle_encode(s: str) -> str:
"""Кодирует строку с помощью RLE (Run-Length Encoding)."""
if not s:
return ""
encoded = []
count = 1
current_char = s[0]
for char in s[1:]:
if char == current_char:
count += 1
else:
encoded.append(f"{count}{current_char}")
current_char = char
count = 1
encoded.append(f"{count}{current_char}")
return ''.join(encoded)
def rle_decode(encoded: str) -> str:
"""Декодирует строку, закодированную RLE."""
decoded = []
i = 0
while i < len(encoded):
# Собираем число (может быть многозначным)
count_str = ""
while i < len(encoded) and encoded[i].isdigit():
count_str += encoded[i]
i += 1
if i < len(encoded):
char = encoded[i]
decoded.append(char * int(count_str))
i += 1
return ''.join(decoded)
# Пояснение: RLE заменяет последовательности одинаковых символов на "количество символ".
# Пример: "AAABBBCCDAA" → "3A3B2C1D2A"
# Эффективно для данных с большими последовательностями одинаковых значений.
Задача 32: Проверка на треугольник и определение его типа
Принцип решения: Проверка неравенства треугольника и сравнение сторон
Что используется: Условные операторы, математические проверки
def triangle_type(a: float, b: float, c: float) -> str:
"""Определяет тип треугольника по длинам сторон."""
# Проверка на треугольник
if a <= 0 or b <= 0 or c <= 0:
return "Не треугольник"
sides = sorted([a, b, c])
if sides[0] + sides[1] <= sides[2]:
return "Не треугольник"
# Определение типа
if a == b == c:
return "Равносторонний"
elif a == b or b == c or a == c:
if abs(a**2 + b**2 - c**2) < 0.0001 or \
abs(a**2 + c**2 - b**2) < 0.0001 or \
abs(b**2 + c**2 - a**2) < 0.0001:
return "Равнобедренный прямоугольный"
return "Равнобедренный"
elif abs(a**2 + b**2 - c**2) < 0.0001 or \
abs(a**2 + c**2 - b**2) < 0.0001 or \
abs(b**2 + c**2 - a**2) < 0.0001:
return "Прямоугольный"
else:
return "Разносторонний"
# Пояснение: Проверяем неравенство треугольника: сумма любых двух сторон > третьей.
# Типы: равносторонний (все равны), равнобедренный (две равны),
# прямоугольный (a² + b² = c²), разносторонный (все разные).
Задача 33: Вычисление определителя матрицы 2x2
Принцип решения: Применение формулы для определителя матрицы 2x2
Что используется: Списки списков, математическая формула
def determinant_2x2(matrix: list) -> float:
"""Вычисляет определитель матрицы 2x2."""
if len(matrix) != 2 or len(matrix[0]) != 2 or len(matrix[1]) != 2:
raise ValueError("Матрица должна быть 2x2")
# Формула: ad - bc
return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
# Пояснение: Для матрицы [[a, b], [c, d]] определитель = a*d - b*c
# Определитель показывает, обратима ли матрица (≠0) и масштаб преобразования.
# Пример: [[1, 2], [3, 4]] → 1*4 - 2*3 = 4 - 6 = -2
Задача 34: Проверка на магический квадрат
Принцип решения: Проверка сумм строк, столбцов и диагоналей
Что используется: Вложенные циклы, множества для проверки уникальности
def is_magic_square(matrix: list) -> bool:
"""Проверяет, является ли матрица магическим квадратом."""
n = len(matrix)
# Проверяем, что все строки имеют одинаковую длину
for row in matrix:
if len(row) != n:
return False
# Проверяем, что все числа от 1 до n² используются ровно один раз
numbers = set()
for row in matrix:
for num in row:
numbers.add(num)
if numbers != set(range(1, n*n + 1)):
return False
# Вычисляем магическую сумму
magic_sum = n * (n*n + 1) // 2
# Проверяем суммы строк
for row in matrix:
if sum(row) != magic_sum:
return False
# Проверяем суммы столбцов
for j in range(n):
col_sum = sum(matrix[i][j] for i in range(n))
if col_sum != magic_sum:
return False
# Проверяем главную диагональ
diag1 = sum(matrix[i][i] for i in range(n))
if diag1 != magic_sum:
return False
# Проверяем побочную диагональ
diag2 = sum(matrix[i][n-1-i] for i in range(n))
return diag2 == magic_sum
# Пояснение: Магический квадрат n×n содержит числа от 1 до n²,
# и суммы всех строк, столбцов и диагоналей равны.
# Магическая сумма = n(n² + 1)/2
Задача 35: Калькулятор выражений с учетом приоритета операций
Принцип решения: Преобразование в обратную польскую нотацию (RPN)
Что используется: Стеки, словарь приоритетов операций
def calculate_expression(expression: str) -> float:
"""Вычисляет арифметическое выражение с учетом приоритетов."""
def apply_operator(operators, values):
operator = operators.pop()
right = values.pop()
left = values.pop()
if operator == '+':
values.append(left + right)
elif operator == '-':
values.append(left - right)
elif operator == '*':
values.append(left * right)
elif operator == '/':
values.append(left / right)
elif operator == '^':
values.append(left ** right)
# Удаляем пробелы
expression = expression.replace(" ", "")
values = []
operators = []
i = 0
precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
while i < len(expression):
if expression[i].isdigit() or expression[i] == '.':
# Считываем число
j = i
while j < len(expression) and (expression[j].isdigit() or expression[j] == '.'):
j += 1
values.append(float(expression[i:j]))
i = j
elif expression[i] == '(':
operators.append('(')
i += 1
elif expression[i] == ')':
while operators and operators[-1] != '(':
apply_operator(operators, values)
operators.pop() # Удаляем '('
i += 1
else:
# Оператор
while (operators and operators[-1] != '(' and
precedence.get(operators[-1], 0) >= precedence.get(expression[i], 0)):
apply_operator(operators, values)
operators.append(expression[i])
i += 1
# Применяем оставшиеся операторы
while operators:
apply_operator(operators, values)
return values[0]
# Пояснение: Используем алгоритм сортировочной станции (Shunting-yard) Дейкстры.
# Преобразуем инфиксную запись в обратную польскую нотацию и вычисляем.
# Поддерживает скобки и приоритеты операций.
Задача 36: Генерация всех перестановок строки
Принцип решения: Рекурсивная генерация перестановок
Что используется: Рекурсия, множества для исключения дубликатов
def permutations(s: str) -> list:
"""Генерирует все уникальные перестановки строки."""
def backtrack(path, used, result):
if len(path) == len(s):
result.append(''.join(path))
return
for i in range(len(s)):
if used[i] or (i > 0 and s[i] == s[i-1] and not used[i-1]):
continue
used[i] = True
path.append(s[i])
backtrack(path, used, result)
path.pop()
used[i] = False
# Сортируем для обработки дубликатов
s = sorted(s)
result = []
backtrack([], [False] * len(s), result)
return result
# Пояснение: Используем backtracking для генерации всех перестановок.
# Отслеживаем использованные символы и пропускаем дубликаты при одинаковых символах.
# Количество перестановок для n уникальных символов = n!
# Для "aab": ["aab", "aba", "baa"]
Задача 37: Поиск самого частого слова в тексте
Принцип решения: Подсчет частоты слов с очисткой от знаков препинания
Что используется: Словарь Counter, регулярные выражения, обработка текста
import re
from collections import Counter
def most_common_word(text: str) -> tuple:
"""Находит самое частое слово в тексте."""
# Убираем знаки препинания и приводим к нижнему регистру
cleaned_text = re.sub(r'[^\w\s]', '', text.lower())
# Разбиваем на слова
words = cleaned_text.split()
# Подсчитываем частоту
word_counts = Counter(words)
# Находим самое частое
if word_counts:
most_common = word_counts.most_common(1)[0]
return most_common[0], most_common[1]
return None, 0
# Пояснение: Очищаем текст от знаков препинания, приводим к нижнему регистру,
# разбиваем на слова и подсчитываем частоту с помощью Counter.
# most_common(1) возвращает список из одного элемента (слово, частота).
Задача 38: Проверка на изоморфные строки
Принцип решения: Построение взаимно-однозначного соответствия между символами
Что используется: Два словаря для двустороннего отображения
def are_isomorphic(s1: str, s2: str) -> bool:
"""Проверяет, являются ли строки изоморфными."""
if len(s1) != len(s2):
return False
mapping_s1_to_s2 = {}
mapping_s2_to_s1 = {}
for c1, c2 in zip(s1, s2):
# Проверяем отображение из s1 в s2
if c1 in mapping_s1_to_s2:
if mapping_s1_to_s2[c1] != c2:
return False
else:
mapping_s1_to_s2[c1] = c2
# Проверяем отображение из s2 в s1
if c2 in mapping_s2_to_s1:
if mapping_s2_to_s1[c2] != c1:
return False
else:
mapping_s2_to_s1[c2] = c1
return True
# Пояснение: Строки изоморфны, если существует взаимно-однозначное отображение символов.
# Пример: "egg" и "add" изоморфны: e→a, g→d
# "foo" и "bar" не изоморфны: f→b, o→a, o→r (o отображается и в a, и в r)
Задача 39: Кодирование Хаффмана (базовый вариант)
Принцип решения: Построение префиксного кода на основе частоты символов
Что используется: Очередь с приоритетом (heapq), двоичное дерево
import heapq
from collections import Counter
class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def huffman_encode(text: str) -> dict:
"""Строит коды Хаффмана для символов текста."""
if not text:
return {}
# Подсчет частот
freq = Counter(text)
# Создаем узлы и помещаем в кучу
heap = [HuffmanNode(char, freq) for char, freq in freq.items()]
heapq.heapify(heap)
# Строим дерево Хаффмана
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
# Обходим дерево для получения кодов
codes = {}
def traverse(node, code):
if node.char is not None:
codes[node.char] = code
return
traverse(node.left, code + "0")
traverse(node.right, code + "1")
traverse(heap[0], "")
return codes
# Пояснение: Алгоритм Хаффмана строит оптимальный префиксный код.
# Частые символы получают короткие коды, редкие - длинные.
# Коды префиксные: ни один код не является началом другого.
Задача 40: Алгоритм Кадана для поиска максимального подмассива
Принцип решения: Динамическое программирование - нахождение лучшей подпоследовательности
Что используется: Динамическое программирование, один проход по массиву
def max_subarray_sum(arr: list) -> tuple:
"""Находит максимальную сумму подмассива и его границы."""
if not arr:
return 0, -1, -1
max_so_far = arr[0]
max_ending_here = arr[0]
start = 0
end = 0
temp_start = 0
for i in range(1, len(arr)):
if arr[i] > max_ending_here + arr[i]:
max_ending_here = arr[i]
temp_start = i
else:
max_ending_here += arr[i]
if max_ending_here > max_so_far:
max_so_far = max_ending_here
start = temp_start
end = i
return max_so_far, start, end
# Пояснение: Алгоритм Кадана находит подмассив с максимальной суммой за O(n).
# Идея: на каждом шаге выбираем - начать новый подмассив или продолжить текущий.
# Пример: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → сумма 6, подмассив [4, -1, 2, 1]
Каждая задача решена с использованием типичных для Python подходов и содержит подробные комментарии о принципах работы алгоритмов. Эти задачи охватывают различные аспекты программирования: математические вычисления, обработку строк, алгоритмы сжатия, динамическое программирование и структуры данных.