Решение различных задач на Python (1 часть)
Задача 1: Проверка на простоту числа
Принцип решения: Проверка делителей до квадратного корня из числа
Что используется: Цикл, математические операции, оптимизация (проверка только нечётных делителей)
def is_prime(n: int) -> bool:
"""Проверяет, является ли число простым."""
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0: # Все чётные числа кроме 2 - составные
return False
# Проверяем только нечётные делители до корня из n
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0:
return False
return True
# Пояснение: Число является простым, если оно делится только на 1 и на себя.
# Достаточно проверять делители до √n, так как если есть делитель больше √n,
# то обязательно есть делитель меньше √n.
Задача 2: Поиск факториала
Принцип решения: Последовательное умножение чисел от 1 до N
Что используется: Цикл (итерация), рекурсия
def factorial_iterative(n: int) -> int:
"""Вычисляет факториал итеративно."""
result = 1
for i in range(2, n + 1):
result *= i
return result
def factorial_recursive(n: int) -> int:
"""Вычисляет факториал рекурсивно."""
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
# Пояснение: Факториал n! = 1 × 2 × 3 × ... × n.
# Итеративный подход более эффективен по памяти.
# Рекурсивный подход нагляден, но может вызвать переполнение стека при больших n.
Задача 3: Числа Фибоначчи
Принцип решения: Каждое следующее число равно сумме двух предыдущих
Что используется: Список, цикл, динамическое программирование
def fibonacci(n: int) -> list:
"""Генерирует первые N чисел Фибоначчи."""
if n <= 0:
return []
elif n == 1:
return [0]
fib = [0, 1] # Начальные значения
for i in range(2, n):
fib.append(fib[i-1] + fib[i-2])
return fib
# Пояснение: Последовательность Фибоначчи: 0, 1, 1, 2, 3, 5, 8, ...
# F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
# Используем список для хранения уже вычисленных значений.
Задача 4: Поиск наибольшего общего делителя (НОД)
Принцип решения: Алгоритм Евклида (деление с остатком)
Что используется: Математические операции, цикл while
def gcd(a: int, b: int) -> int:
"""Находит наибольший общий делитель двух чисел."""
while b:
a, b = b, a % b # Делаем b новым a, а остаток от деления - новым b
return a
# Пояснение: Алгоритм Евклида основан на том, что НОД(a,b) = НОД(b, a mod b).
# Процесс продолжается, пока b не станет равным 0.
# Пример: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6
Задача 5: Поиск наименьшего общего кратного (НОК)
Принцип решения: Использование связи НОК и НОД
Что используется: Математическая формула, ранее написанная функция gcd
def lcm(a: int, b: int) -> int:
"""Находит наименьшее общее кратное двух чисел."""
return abs(a * b) // gcd(a, b)
# Пояснение: НОК можно найти по формуле: НОК(a,b) = |a × b| / НОД(a,b)
# Используем целочисленное деление //, так как результат всегда целый.
# Пример: lcm(12, 18) = (12 × 18) / 6 = 36
Задача 6: Разложение числа на простые множители
Принцип решения: Последовательное деление на простые делители
Что используется: Цикл while, список, проверка делимости
def prime_factors(n: int) -> list:
"""Разлагает число на простые множители."""
factors = []
divisor = 2
while divisor * divisor <= n:
while n % divisor == 0:
factors.append(divisor)
n //= divisor
divisor += 1 if divisor == 2 else 2 # Проверяем 2, затем только нечётные
if n > 1:
factors.append(n)
return factors
# Пояснение: Делим число на простые делители, начиная с 2.
# Пока число делится на текущий делитель, добавляем его в список.
# Пример: 60 → 2×30 → 2×2×15 → 2×2×3×5
Задача 7: Обращение строки
Принцип решения: Построение новой строки из символов исходной в обратном порядке
Что используется: Срезы (slicing) или цикл, конкатенация строк
def reverse_string(s: str) -> str:
"""Возвращает перевернутую строку без использования reversed()."""
# Способ 1: Использование срезов (самый питонический)
return s[::-1]
# Способ 2: Через цикл
# reversed_str = ""
# for char in s:
# reversed_str = char + reversed_str
# return reversed_str
# Пояснение: Синтаксис среза [начало:конец:шаг].
# При шаге -1 строка перебирается от конца к началу.
# В цикле каждый новый символ добавляется в начало строки.
Задача 8: Подсчет гласных в строке
Принцип решения: Проверка каждого символа на принадлежность к множеству гласных
Что используется: Множество (set), цикл, метод lower()
def count_vowels(s: str) -> int:
"""Подсчитывает количество гласных букв в строке."""
vowels = set("aeiouаеёиоуыэюя") # Для английского и русского
count = 0
for char in s.lower():
if char in vowels:
count += 1
return count
# Пояснение: Используем множество для быстрой проверки принадлежности.
# Приводим все символы к нижнему регистру для унификации.
# Сложность O(n), где n - длина строки.
Задача 9: Проверка анаграмм
Принцип решения: Две строки являются анаграммами, если после сортировки символов они совпадают
Что используется: Сортировка, приведение к нижнему регистру
def are_anagrams(s1: str, s2: str) -> bool:
"""Проверяет, являются ли строки анаграммами."""
# Убираем пробелы и приводим к нижнему регистру
s1 = s1.replace(" ", "").lower()
s2 = s2.replace(" ", "").lower()
# Сортируем символы и сравниваем
return sorted(s1) == sorted(s2)
# Пояснение: Анаграммы имеют одинаковый набор символов.
# Пример: "listen" и "silent" → sorted('listen') = ['e','i','l','n','s','t']
# sorted('silent') = ['e','i','l','n','s','t']
Задача 10: Удаление дубликатов из списка
Принцип решения: Проход по списку с сохранением порядка первого вхождения
Что используется: Множество для отслеживания уникальности, список для результата
def remove_duplicates(lst: list) -> list:
"""Удаляет дубликаты из списка, сохраняя порядок."""
seen = set()
result = []
for item in lst:
if item not in seen:
seen.add(item)
result.append(item)
return result
# Пояснение: Используем множество seen для быстрой проверки (O(1)).
# Добавляем элемент в результат только если его еще не было.
# Порядок сохраняется благодаря последовательному проходу.
Задача 11: Поиск второго по величине элемента в списке
Принцип решения: Проход по списку с отслеживанием двух наибольших значений
Что используется: Переменные для хранения максимальных значений, цикл
def second_largest(lst: list) -> int:
"""Находит второй по величине элемент в списке."""
if len(lst) < 2:
return None
# Инициализируем два наибольших значения
first = second = float('-inf')
for num in lst:
if num > first:
second = first
first = num
elif num > second and num != first:
second = num
return second if second != float('-inf') else None
# Пояснение: Проходим по списку один раз, обновляя first и second.
# Важно: если num == first, не обновляем second (для повторяющихся значений).
# float('-inf') используется как начальное минимальное значение.
Задача 12: Частота символов в строке
Принцип решения: Подсчет вхождений каждого символа с использованием словаря
Что используется: Словарь (dict), цикл по строке
def char_frequency(s: str) -> dict:
"""Подсчитывает частоту каждого символа в строке."""
freq = {}
for char in s:
freq[char] = freq.get(char, 0) + 1
return freq
# Пояснение: Используем словарь для хранения пар "символ: количество".
# Метод get(key, default) возвращает значение по ключу или default, если ключа нет.
# Альтернатива: collections.Counter(s)
Задача 13: Сумма цифр числа
Принцип решения: Последовательное извлечение цифр через деление на 10
Что используется: Математические операции, цикл while
def digit_sum(n: int) -> int:
"""Находит сумму цифр числа."""
total = 0
n = abs(n) # Работаем с абсолютным значением
while n > 0:
total += n % 10 # Добавляем последнюю цифру
n //= 10 # Убираем последнюю цифру
return total
# Пояснение: Число 1234:
# Итерация 1: total=4, n=123
# Итерация 2: total=7, n=12
# Итерация 3: total=9, n=1
# Итерация 4: total=10, n=0
Задача 14: Проверка на степень двойки
Принцип решения: Использование битовых операций или математических свойств
Что используется: Битовые операции, свойства двоичного представления
def is_power_of_two(n: int) -> bool:
"""Проверяет, является ли число степенью двойки."""
if n <= 0:
return False
# Способ 1: Битовые операции
return (n & (n - 1)) == 0
# Пояснение: Степени двойки в двоичном виде: 1(1), 2(10), 4(100), 8(1000)
# Число n-1 будет иметь все биты противоположные: 3(11), 7(111), 15(1111)
# Побитовое И между n и n-1 даст 0 только для степеней двойки.
Задача 15: Слияние двух отсортированных списков
Принцип решения: Поэлементное сравнение и добавление минимального элемента
Что используется: Два указателя, список-результат, цикл while
def merge_sorted_lists(lst1: list, lst2: list) -> list:
"""Объединяет два отсортированных списка в один отсортированный."""
result = []
i = j = 0 # Указатели на текущие элементы
while i < len(lst1) and j < len(lst2):
if lst1[i] < lst2[j]:
result.append(lst1[i])
i += 1
else:
result.append(lst2[j])
j += 1
# Добавляем оставшиеся элементы
result.extend(lst1[i:])
result.extend(lst2[j:])
return result
# Пояснение: Алгоритм слияния из сортировки слиянием (merge sort).
# Сравниваем текущие элементы, добавляем меньший, двигаем соответствующий указатель.
# В конце добавляем остатки любого списка.
Задача 16: Нахождение пропущенного числа
Принцип решения: Использование формулы суммы арифметической прогрессии
Что используется: Математическая формула, сумма элементов
def find_missing_number(nums: list) -> int:
"""Находит пропущенное число в массиве 1..N+1."""
n = len(nums) + 1 # Должно быть n чисел, есть n-1
total_sum = n * (n + 1) // 2 # Сумма чисел от 1 до n
actual_sum = sum(nums)
return total_sum - actual_sum
# Пояснение: Сумма чисел от 1 до n = n(n+1)/2
# Разница между ожидаемой суммой и фактической дает пропущенное число.
# Пример: [1,2,4,5] → n=5, total=15, actual=12 → пропущено 3
Задача 17: Проверка сбалансированности скобок
Принцип решения: Использование стека для отслеживания открывающих скобок
Что используется: Стек (реализованный списком), словарь для соответствия скобок
def is_balanced(s: str) -> bool:
"""Проверяет правильность расстановки скобок."""
stack = []
brackets = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in brackets.values(): # Открывающая скобка
stack.append(char)
elif char in brackets: # Закрывающая скобка
if not stack or stack[-1] != brackets[char]:
return False
stack.pop()
return len(stack) == 0 # Все скобки должны быть закрыты
# Пояснение: Используем стек LIFO (Last In, First Out).
# Открывающие скобки добавляем в стек.
# При встрече закрывающей скобки проверяем, соответствует ли она последней открывающей.
Задача 18: Генерация всех подмножеств
Принцип решения: Использование битовой маски или рекурсии
Что используется: Битовая арифметика, циклы
def subsets(nums: list) -> list:
"""Генерирует все подмножества списка."""
n = len(nums)
result = []
# Всего 2^n подмножеств
for mask in range(1 << n): # 1 << n = 2^n
subset = []
for i in range(n):
if mask & (1 << i): # Проверяем i-й бит маски
subset.append(nums[i])
result.append(subset)
return result
# Пояснение: Каждое подмножество соответствует битовой маске длины n.
# Если i-й бит = 1, элемент входит в подмножество.
# Пример: [1,2] → маски: 00([]), 01([1]), 10([2]), 11([1,2])
Задача 19: Проверка на палиндром числа
Принцип решения: Построение обратного числа через математические операции
Что используется: Математические операции, цикл while
def is_palindrome_number(num: int) -> bool:
"""Проверяет, является ли число палиндромом без преобразования в строку."""
if num < 0:
return False
original = num
reversed_num = 0
while num > 0:
digit = num % 10
reversed_num = reversed_num * 10 + digit
num //= 10
return original == reversed_num
# Пояснение: Строим обратное число: последняя цифра становится первой.
# Пример: 123 → reversed=0
# Итерация 1: digit=3, reversed=3, num=12
# Итерация 2: digit=2, reversed=32, num=1
# Итерация 3: digit=1, reversed=321, num=0
Задача 20: Поиск пересечения двух списков
Принцип решения: Использование множеств для нахождения общих элементов
Что используется: Множества (sets), преобразование типов
def intersection_without_duplicates(lst1: list, lst2: list) -> list:
"""Находит пересечение списков без дубликатов."""
return list(set(lst1) & set(lst2))
def intersection_with_duplicates(lst1: list, lst2: list) -> list:
"""Находит пересечение списков с учетом повторений."""
from collections import Counter
counter1 = Counter(lst1)
counter2 = Counter(lst2)
result = []
for num in counter1:
if num in counter2:
result.extend([num] * min(counter1[num], counter2[num]))
return result
# Пояснение:
# Без дубликатов: используем операцию пересечения множеств.
# С дубликатами: используем Counter для подсчета, берем минимум вхождений.
Каждое решение сопровождается подробными комментариями, объясняющими принцип работы алгоритма и ключевые моменты реализации.