← Назад к курсу
20 нестандартных математических задач на Python с подробным разбором
Каждая задача в этом уроке демонстрирует важный математический или алгоритмический принцип, с подробными комментариями и примерами использования.
Задача 1: Поиск чисел Фибоначи через матричное умножение (O(log n))
Описание: Найти n-ное число Фибоначи, используя быстрое возведение матрицы в степень.
Методика: Используем матрицу [[1,1],[1,0]]^n = [[F(n+1), F(n)],[F(n), F(n-1)]].
def matrix_mult(a, b):
return [[a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
[a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]]
def matrix_pow(mat, power):
if power == 1:
return mat
if power % 2 == 0:
half = matrix_pow(mat, power // 2)
return matrix_mult(half, half)
else:
return matrix_mult(mat, matrix_pow(mat, power - 1))
def fibonacci_fast(n):
if n == 0:
return 0
base = [[1, 1], [1, 0]]
result = matrix_pow(base, n)
return result[0][1] # F(n)
print(fibonacci_fast(10)) # 55
Задача 2: Проверка числа на совершенство
Описание: Совершенное число равно сумме всех своих делителей (кроме себя).
Методика: Находим делители до sqrt(n), аккуратно суммируем.
def is_perfect_number(n):
if n < 2:
return False
divisors_sum = 1
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
divisors_sum += i
if i != n // i: # избегаем повторения для квадратов
divisors_sum += n // i
return divisors_sum == n
print(is_perfect_number(28)) # True (1+2+4+7+14=28)
Задача 3: Поиск всех чисел Армстронга (нарциссических чисел)
Описание: Число, равное сумме своих цифр, возведенных в степень количества цифр.
Методика: Перебор с разложением числа на цифры.
def narcissistic_numbers(limit):
result = []
for num in range(10, limit + 1):
digits = [int(d) for d in str(num)]
power = len(digits)
if sum(d**power for d in digits) == num:
result.append(num)
return result
print(narcissistic_numbers(10000)) # [153, 370, 371, 407, 1634, 8208, 9474]
Задача 4: Алгоритм Кадача для поиска максимальной суммы подмассива
Описание: Найти непрерывный подмассив с максимальной суммой.
Методика: Динамическое программирование за O(n).
def kadane_max_subarray(arr):
max_current = max_global = arr[0]
start = end = temp_start = 0
for i in range(1, len(arr)):
if arr[i] > max_current + arr[i]:
max_current = arr[i]
temp_start = i
else:
max_current += arr[i]
if max_current > max_global:
max_global = max_current
start = temp_start
end = i
return max_global, arr[start:end+1]
print(kadane_max_subarray([-2,1,-3,4,-1,2,1,-5,4])) # (6, [4,-1,2,1])
Задача 5: Генерация всех разбиений числа
Описание: Разбить число n в сумму положительных целых чисел (с учетом порядка).
Методика: Рекурсивный поиск с возвратом.
def partitions(n, max_part=None, current=None):
if current is None:
current = []
if max_part is None:
max_part = n
if n == 0:
yield current.copy()
return
for i in range(1, min(max_part, n) + 1):
current.append(i)
yield from partitions(n - i, i, current)
current.pop()
print(list(partitions(5))) # [[1,1,1,1,1], [2,1,1,1], [2,2,1], [3,1,1], [3,2], [4,1], [5]]
Задача 6: Задача о рюкзаке 0/1
Описание: Максимизировать стоимость предметов в рюкзаке ограниченной вместимости.
Методика: Динамическое программирование.
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, capacity+1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w],
values[i-1] + dp[i-1][w-weights[i-1]])
else:
dp[i][w] = dp[i-1][w]
# Восстановление выбранных предметов
selected = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i-1][w]:
selected.append(i-1)
w -= weights[i-1]
return dp[n][capacity], selected[::-1]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity)) # (7, [0, 1])
Задача 7: Расстояние Левенштейна (редакционное расстояние)
Описание: Минимальное количество операций для преобразования одной строки в другую.
Методика: Динамическое программирование.
def levenshtein_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1):
dp[i][0] = i
for j in range(n+1):
dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
cost = 0 if s1[i-1] == s2[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # удаление
dp[i][j-1] + 1, # вставка
dp[i-1][j-1] + cost # замена
)
return dp[m][n]
print(levenshtein_distance("kitten", "sitting")) # 3
Задача 8: Задача Иосифа Флавия
Описание: Определить выжившего в кругу из n человек, выбывающего каждого k-го.
Методика: Рецирентная формула f(n,k) = (f(n-1,k)+k-1)%n + 1.
def josephus(n, k):
survivor = 0
for i in range(2, n + 1):
survivor = (survivor + k) % i
return survivor + 1
print(josephus(7, 3)) # 4 (При n=7, k=3 выживает 4-й)
Задача 9: Алгоритм Дейкстры → Задача о расстановке ферзей на шахматной доске
Описание: Расставить N ферзей на доске N×N так, чтобы они не атаковали друг друга.
Методика: Бектрекинг с проверкой диагоналей.
def solve_n_queens(n):
def is_safe(board, row, col):
# Проверяем столбец сверху
for i in range(row):
if board[i] == col:
return False
# Проверяем диагонали
if abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(board, row):
if row == n:
result.append(board.copy())
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
backtrack(board, row + 1)
board[row] = -1
result = []
backtrack([-1] * n, 0)
return result
def print_solution(solution):
n = len(solution)
for row in range(n):
line = ['Q' if solution[row] == col else '.' for col in range(n)]
print(' '.join(line))
solutions = solve_n_queens(4)
print(f"Количество решений для 4 ферзей: {len(solutions)}")
if solutions:
print("Первое решение:")
print_solution(solutions[0])
Задача 10: Алгоритм Флойда-Уоршелла → Матричный алгоритм Штрассена
Описание: Умножение матриц алгоритмом Штрассена за O(n^log2(7)) ≈ O(n^2.81).
Методика: Рекурсивное разбиение матриц на подматрицы.
def split_matrix(matrix):
"""Разделение матрицы на 4 подматрицы"""
n = len(matrix)
mid = n // 2
A = [row[:mid] for row in matrix[:mid]]
B = [row[mid:] for row in matrix[:mid]]
C = [row[:mid] for row in matrix[mid:]]
D = [row[mid:] for row in matrix[mid:]]
return A, B, C, D
def add_matrices(A, B):
"""Сложение матриц"""
n = len(A)
return [[A[i][j] + B[i][j] for j in range(n)] for i in range(n)]
def subtract_matrices(A, B):
"""Вычитание матриц"""
n = len(A)
return [[A[i][j] - B[i][j] for j in range(n)] for i in range(n)]
def strassen_multiply(X, Y):
n = len(X)
# Базовый случай
if n == 1:
return [[X[0][0] * Y[0][0]]]
# Разбиваем матрицы
A, B, C, D = split_matrix(X)
E, F, G, H = split_matrix(Y)
# Вычисляем 7 произведений (алгоритм Штрассена)
# P1 = A * (F - H)
FH = subtract_matrices(F, H)
P1 = strassen_multiply(A, FH)
# P2 = (A + B) * H
AB = add_matrices(A, B)
P2 = strassen_multiply(AB, H)
# P3 = (C + D) * E
CD = add_matrices(C, D)
P3 = strassen_multiply(CD, E)
# P4 = D * (G - E)
GE = subtract_matrices(G, E)
P4 = strassen_multiply(D, GE)
# P5 = (A + D) * (E + H)
AD = add_matrices(A, D)
EH = add_matrices(E, H)
P5 = strassen_multiply(AD, EH)
# P6 = (B - D) * (G + H)
BD = subtract_matrices(B, D)
GH = add_matrices(G, H)
P6 = strassen_multiply(BD, GH)
# P7 = (A - C) * (E + F)
AC = subtract_matrices(A, C)
EF = add_matrices(E, F)
P7 = strassen_multiply(AC, EF)
# Собираем результат
# Q1 = P5 + P4 - P2 + P6
Q1 = add_matrices(subtract_matrices(add_matrices(P5, P4), P2), P6)
# Q2 = P1 + P2
Q2 = add_matrices(P1, P2)
# Q3 = P3 + P4
Q3 = add_matrices(P3, P4)
# Q4 = P1 + P5 - P3 - P7
Q4 = subtract_matrices(subtract_matrices(add_matrices(P1, P5), P3), P7)
# Объединяем подматрицы
result = [[0] * n for _ in range(n)]
mid = n // 2
for i in range(mid):
for j in range(mid):
result[i][j] = Q1[i][j]
result[i][j + mid] = Q2[i][j]
result[i + mid][j] = Q3[i][j]
result[i + mid][j + mid] = Q4[i][j]
return result
# Пример
X = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
Y = [[16, 15, 14, 13],
[12, 11, 10, 9],
[8, 7, 6, 5],
[4, 3, 2, 1]]
result = strassen_multiply(X, Y)
print("Результат умножения матриц (первые 2x2):")
for i in range(2):
print(result[i][:2])
Задача 11: Поиск эйлерова пути → Задача о Ханойских башнях
Описание: Перенести башню из N дисков со стержня A на стержень C, используя B как вспомогательный.
Методика: Рекурсивное решение с отображением шагов.
def towers_of_hanoi(n, source, target, auxiliary, moves=None):
if moves is None:
moves = []
if n == 1:
moves.append(f"Переместить диск 1 с {source} на {target}")
return moves
# Переместить n-1 дисков с source на auxiliary
towers_of_hanoi(n-1, source, auxiliary, target, moves)
# Переместить самый большой диск
moves.append(f"Переместить диск {n} с {source} на {target}")
# Переместить n-1 дисков с auxiliary на target
towers_of_hanoi(n-1, auxiliary, target, source, moves)
return moves
def towers_of_hanoi_iterative(n, source, target, auxiliary):
"""Итеративное решение"""
moves = []
total_moves = 2**n - 1
# Если n четно, меняем target и auxiliary
if n % 2 == 0:
target, auxiliary = auxiliary, target
rods = {source: list(range(n, 0, -1)),
auxiliary: [],
target: []}
for i in range(1, total_moves + 1):
if i % 3 == 1:
# Перемещение между source и target
if not rods[source] or (rods[target] and rods[source][-1] > rods[target][-1]):
disk = rods[target].pop()
rods[source].append(disk)
moves.append(f"Переместить диск {disk} с {target} на {source}")
else:
disk = rods[source].pop()
rods[target].append(disk)
moves.append(f"Переместить диск {disk} с {source} на {target}")
elif i % 3 == 2:
# Перемещение между source и auxiliary
if not rods[source] or (rods[auxiliary] and rods[source][-1] > rods[auxiliary][-1]):
disk = rods[auxiliary].pop()
rods[source].append(disk)
moves.append(f"Переместить диск {disk} с {auxiliary} на {source}")
else:
disk = rods[source].pop()
rods[auxiliary].append(disk)
moves.append(f"Переместить диск {disk} с {source} на {auxiliary}")
else:
# Перемещение между auxiliary и target
if not rods[auxiliary] or (rods[target] and rods[auxiliary][-1] > rods[target][-1]):
disk = rods[target].pop()
rods[auxiliary].append(disk)
moves.append(f"Переместить диск {disk} с {target} на {auxiliary}")
else:
disk = rods[auxiliary].pop()
rods[target].append(disk)
moves.append(f"Переместить диск {disk} с {auxiliary} на {target}")
return moves
# Пример
n = 3
print(f"Решение Ханойских башен для {n} дисков (рекурсивное):")
recursive_moves = towers_of_hanoi(n, 'A', 'C', 'B')
for i, move in enumerate(recursive_moves[:5], 1):
print(f"{i}. {move}")
if len(recursive_moves) > 5:
print("...")
print(f"Всего ходов: {len(recursive_moves)}")
print(f"\nПроверка формулы: 2^{n} - 1 = {2**n - 1}")
Задача 12: Решето Эратосфена с линейной сложностью O(n)
Описание: Найти все простые числа до n с линейным временем.
Методика: Модифицированное решето с хранением минимального простого делителя.
def linear_sieve(n):
primes = []
lp = [0] * (n + 1) # минимальный простой делитель
for i in range(2, n + 1):
if lp[i] == 0:
lp[i] = i
primes.append(i)
for p in primes:
if p > lp[i] or i * p > n:
break
lp[i * p] = p
return primes, lp
n = 30
primes, lp = linear_sieve(n)
print(f"Простые до {n}: {primes}")
print(f"Минимальные делители: {lp}")
Задача 13: Алгоритм Кадане для циклического массива
Описание: Максимальная сумма подмассива в циклическом массиве.
Методика: Ищем либо обычный максимальный подмассив, либо сумму всего массива минус минимальный подмассив.
def max_subarray_circular(arr):
if not arr:
return 0
# Стандартный алгоритм Кадане
def kadane(arr):
max_current = max_global = arr[0]
for x in arr[1:]:
max_current = max(x, max_current + x)
max_global = max(max_global, max_current)
return max_global
# Случай 1: Максимальный подмассив без зацикливания
max_kadane = kadane(arr)
# Случай 2: Максимальный подмассив с зацикливанием (вся сумма минус минимальный подмассив)
total_sum = sum(arr)
# Минимальный подмассив (инвертируем знаки и ищем максимум)
arr_neg = [-x for x in arr]
max_kadane_neg = kadane(arr_neg)
max_wrap = total_sum + max_kadane_neg # total - min_subarray
# Особый случай: если все числа отрицательные
if max_wrap == 0:
return max_kadane
return max(max_kadane, max_wrap)
print(max_subarray_circular([8, -1, 3, 4])) # 15 (8 + (-1) + 3 + 4)
print(max_subarray_circular([-3, -2, -1])) # -1
Задача 14: Задача о рюкзаке со стоимостью за единицу веса
Описание: Рюкзак с дробными предметами (можно брать части предметов).
Методика: Жадный алгоритм - сортируем по удельной стоимости.
def fractional_knapsack(weights, values, capacity):
items = [(values[i]/weights[i], weights[i], values[i])
for i in range(len(weights))]
items.sort(reverse=True, key=lambda x: x[0]) # сортировка по удельной стоимости
total_value = 0
remaining_capacity = capacity
for ratio, weight, value in items:
if remaining_capacity >= weight:
total_value += value
remaining_capacity -= weight
else:
total_value += ratio * remaining_capacity
break
return total_value
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(fractional_knapsack(weights, values, capacity)) # 240.0
Задача 15: Решение СЛАУ методом Гаусса
Описание: Решение системы линейных уравнений методом Гаусса.
Методика: Приведение матрицы к ступенчатому виду с обратным ходом.
def gauss_elimination(matrix):
n = len(matrix)
# Прямой ход
for i in range(n):
# Поиск максимального элемента в столбце для pivot
max_row = i
for k in range(i+1, n):
if abs(matrix[k][i]) > abs(matrix[max_row][i]):
max_row = k
# Перестановка строк
matrix[i], matrix[max_row] = matrix[max_row], matrix[i]
# Нормализация текущей строки
pivot = matrix[i][i]
if abs(pivot) < 1e-10:
continue
for j in range(i, n+1):
matrix[i][j] /= pivot
# Обнуление столбца под pivot
for k in range(n):
if k != i and abs(matrix[k][i]) > 1e-10:
factor = matrix[k][i]
for j in range(i, n+1):
matrix[k][j] -= factor * matrix[i][j]
# Извлечение решения
solution = [0] * n
for i in range(n):
solution[i] = matrix[i][n]
return solution
# Система: 2x + y = 5, x + 3y = 6
matrix = [
[2, 1, 5],
[1, 3, 6]
]
solution = gauss_elimination([row.copy() for row in matrix])
print(f"Решение: x = {solution[0]:.2f}, y = {solution[1]:.2f}")
Задача 16: Числа Каталана через биномиальные коэффициенты
Описание: Вычисление чисел Каталана для комбинаторных задач.
Методика: C_n = (1/(n+1)) * C(2n, n).
def binomial_coefficient(n, k):
if k < 0 or k > n:
return 0
# Оптимизация: используем симметрию
if k > n - k:
k = n - k
result = 1
for i in range(1, k + 1):
result = result * (n - i + 1) // i
return result
def catalan_number(n):
if n < 0:
return 0
# C_n = (1/(n+1)) * C(2n, n)
return binomial_coefficient(2*n, n) // (n + 1)
# Применения: скобочные последовательности, пути в сетке, деревья
for i in range(10):
print(f"C_{i} = {catalan_number(i)}")
Задача 17: Быстрое преобразование Фурье (FFT)
Описание: Умножение полиномов за O(n log n).
Методика: Рекурсивный алгоритм Cooley-Tukey.
import cmath
import math
def fft(poly, inverse=False):
n = len(poly)
if n <= 1:
return poly
# Разделение на четные и нечетные коэффициенты
even = fft(poly[0::2], inverse)
odd = fft(poly[1::2], inverse)
# Корни из единицы
angle = 2 * math.pi / n * (-1 if inverse else 1)
w = complex(math.cos(angle), math.sin(angle))
wk = complex(1, 0)
result = [0] * n
for k in range(n // 2):
# Теорема о сшивании
t = wk * odd[k]
result[k] = even[k] + t
result[k + n // 2] = even[k] - t
wk *= w
# Нормализация для обратного преобразования
if inverse:
result = [x / 2 for x in result]
return result
def multiply_polynomials(poly1, poly2):
# Дополняем до степени 2^k
n = 1
while n < len(poly1) + len(poly2):
n <<= 1
poly1 += [0] * (n - len(poly1))
poly2 += [0] * (n - len(poly2))
# Прямое преобразование
fft1 = fft(poly1)
fft2 = fft(poly2)
# Поточечное умножение
fft_product = [a * b for a, b in zip(fft1, fft2)]
# Обратное преобразование
result = fft(fft_product, inverse=True)
# Округление и извлечение вещественной части
return [round(x.real) for x in result]
# Умножение (x + 2) * (x + 3) = x^2 + 5x + 6
poly1 = [2, 1] # 2 + x
poly2 = [3, 1] # 3 + x
print(multiply_polynomials(poly1, poly2)) # [6, 5, 1]
Задача 18: Алгоритм Meet-in-the-Middle для задачи о сумме подмножества
Описание: Найти подмножество с заданной суммой за O(2^(n/2)).
Методика: Разделяем массив на две части и используем хеш-таблицы.
def subset_sum_meet_in_middle(arr, target):
n = len(arr)
half = n // 2
# Генерируем все суммы для первой половины
left_sums = {}
for mask in range(1 << half):
s = 0
for i in range(half):
if mask & (1 << i):
s += arr[i]
left_sums[s] = mask
# Ищем во второй половине
for mask in range(1 << (n - half)):
s = 0
for i in range(n - half):
if mask & (1 << i):
s += arr[half + i]
# Ищем комплементарную сумму в первой половине
needed = target - s
if needed in left_sums:
# Восстанавливаем подмножество
left_mask = left_sums[needed]
right_mask = mask
subset = []
for i in range(half):
if left_mask & (1 << i):
subset.append(arr[i])
for i in range(n - half):
if right_mask & (1 << i):
subset.append(arr[half + i])
return subset, s + needed
return None
arr = [3, 34, 4, 12, 5, 2]
target = 9
result = subset_sum_meet_in_middle(arr, target)
print(f"Подмножество с суммой {target}: {result}")
Задача 19: Дерево Фенвика (BIT) для суммы на префиксе
Описание: Структура данных для быстрого обновления и запроса суммы на префиксе.
Методика: Используем свойство двоичного представления индексов.
class FenwickTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, idx, delta):
"""Добавить delta к элементу idx (1-индексация)"""
while idx <= self.n:
self.tree[idx] += delta
idx += idx & -idx # переход к следующему узлу
def query(self, idx):
"""Сумма элементов от 1 до idx"""
result = 0
while idx > 0:
result += self.tree[idx]
idx -= idx & -idx # переход к предыдущему узлу
return result
def range_query(self, l, r):
"""Сумма на отрезке [l, r] (1-индексация)"""
return self.query(r) - self.query(l - 1)
# Пример использования
arr = [2, 1, 4, 6, 3, 5]
ft = FenwickTree(len(arr))
# Построение дерева
for i, val in enumerate(arr, 1):
ft.update(i, val)
print(f"Сумма на [1, 3]: {ft.range_query(1, 3)}") # 2+1+4=7
print(f"Сумма на [2, 5]: {ft.range_query(2, 5)}") # 1+4+6+3=14
# Обновление
ft.update(3, 2) # arr[2] += 2 (было 4, стало 6)
print(f"После обновления сумма на [1, 3]: {ft.range_query(1, 3)}") # 2+1+6=9
Задача 20: Поиск всех пифагоровых троек до предела
Описание: Найти все натуральные числа a, b, c такие что a² + b² = c² и a ≤ b ≤ c ≤ n.
Методика: Используем параметризацию Евклида: a = m² - n², b = 2mn, c = m² + n².
def pythagorean_triples(limit):
triples = []
# Перебор параметров m, n
for m in range(2, int(limit**0.5) + 1):
for n in range(1, m):
# Разные четности и взаимно простые
if (m - n) % 2 == 1 and math.gcd(m, n) == 1:
a = m*m - n*n
b = 2*m*n
c = m*m + n*n
if c > limit:
continue
# Сортируем a и b
if a > b:
a, b = b, a
# Добавляем все кратные
k = 1
while k*c <= limit:
triples.append((k*a, k*b, k*c))
k += 1
# Сортируем по гипотенузе
triples.sort(key=lambda x: x[2])
return triples
def pythagorean_triples_bruteforce(limit):
"""Прямой перебор для сравнения"""
triples = []
for a in range(1, limit + 1):
for b in range(a, limit + 1):
c_sq = a*a + b*b
c = int(c_sq**0.5)
if c <= limit and c*c == c_sq:
triples.append((a, b, c))
return triples
# Сравнение методов
limit = 50
triples_euclid = pythagorean_triples(limit)
triples_brute = pythagorean_triples_bruteforce(limit)
print("Метод Евклида:")
for t in triples_euclid[:10]:
print(f"{t[0]}² + {t[1]}² = {t[2]}²")
print(f"\nВсего троек до {limit}: {len(triples_euclid)}")
Задача 21: Алгоритм Карацубы для умножения больших чисел
Описание: Умножение больших чисел за O(n^log2(3)) ≈ O(n^1.585).
Методика: Разделяй и властвуй.
def karatsuba(x, y):
# Базовый случай
if x < 10 or y < 10:
return x * y
# Определяем размер чисел
n = max(len(str(x)), len(str(y)))
m = n // 2
# Разбиваем числа
high1, low1 = divmod(x, 10**m)
high2, low2 = divmod(y, 10**m)
# Рекурсивные вызовы
z0 = karatsuba(low1, low2)
z1 = karatsuba((low1 + high1), (low2 + high2))
z2 = karatsuba(high1, high2)
# Собираем результат
return z2 * 10**(2*m) + ((z1 - z2 - z0) * 10**m) + z0
# Пример с большими числами
num1 = 123456789
num2 = 987654321
result = karatsuba(num1, num2)
print(f"{num1} * {num2} = {result}")
print(f"Проверка: {num1 * num2 == result}")
Задача 22: RSA шифрование и дешифрование
Описание: Реализация алгоритма RSA для шифрования и дешифрования сообщений.
Методика: Теория чисел: генерация ключей, шифрование через модульную экспоненту.
import random
import math
from sympy import isprime, mod_inverse
def generate_rsa_keys(bits=64):
"""Генерация ключей RSA"""
# Генерация простых чисел
def generate_prime(bits):
while True:
p = random.getrandbits(bits)
# Убедимся, что число нечетное и достаточно большое
p |= (1 << bits - 1) | 1
if isprime(p):
return p
# Шаг 1: Выбираем два простых числа
p = generate_prime(bits // 2)
q = generate_prime(bits // 2)
while p == q:
q = generate_prime(bits // 2)
# Шаг 2: Вычисляем n = p * q
n = p * q
# Шаг 3: Вычисляем функцию Эйлера
phi = (p - 1) * (q - 1)
# Шаг 4: Выбираем открытую экспоненту e
e = 65537 # Стандартное значение
while math.gcd(e, phi) != 1:
e = random.randrange(3, phi, 2)
# Шаг 5: Вычисляем закрытую экспоненту d
d = mod_inverse(e, phi)
return {
'public': (e, n),
'private': (d, n),
'p': p, 'q': q, 'phi': phi
}
def rsa_encrypt(message, public_key):
"""Шифрование сообщения"""
e, n = public_key
# Преобразуем сообщение в число
if isinstance(message, str):
message_int = int.from_bytes(message.encode(), 'big')
else:
message_int = message
# Шифруем: c = m^e mod n
encrypted = pow(message_int, e, n)
return encrypted
def rsa_decrypt(encrypted, private_key):
"""Дешифрование сообщения"""
d, n = private_key
# Дешифруем: m = c^d mod n
decrypted_int = pow(encrypted, d, n)
# Преобразуем число обратно в строку
byte_length = (decrypted_int.bit_length() + 7) // 8
decrypted_bytes = decrypted_int.to_bytes(byte_length, 'big')
try:
return decrypted_bytes.decode()
except:
return decrypted_int
# Пример использования
print("RSA шифрование:")
keys = generate_rsa_keys(32) # 32 бита для демонстрации
print(f"Открытый ключ (e, n): {keys['public']}")
print(f"Закрытый ключ (d, n): {keys['private']}")
message = "Hello RSA"
print(f"\nИсходное сообщение: {message}")
encrypted = rsa_encrypt(message, keys['public'])
print(f"Зашифрованное: {encrypted}")
decrypted = rsa_decrypt(encrypted, keys['private'])
print(f"Расшифрованное: {decrypted}")
# Проверка
print(f"\nСообщение восстановлено корректно: {message == decrypted}")
Задача 23: Алгоритм симплекс-метода для линейного программирования
Описание: Решение задачи линейного программирования симплекс-методом.
Методика: Итеративное улучшение базисного решения.
import numpy as np
def simplex_method(c, A, b):
"""
Решение задачи линейного программирования:
Максимизировать c^T * x
При условиях A * x <= b, x >= 0
"""
m, n = A.shape
# Добавляем переменные неотрицательности
tableau = np.zeros((m + 1, n + m + 1))
# Коэффициенты целевой функции
tableau[-1, :n] = -c # Минимизируем -c^T*x для максимизации
# Ограничения
tableau[:m, :n] = A
tableau[:m, n:n+m] = np.eye(m) # Добавочные переменные
tableau[:m, -1] = b
# Коэффициенты добавочных переменных в целевой функции = 0
tableau[-1, n:n+m] = 0
while True:
# Находим вводимую переменную (самый отрицательный в последней строке)
if np.all(tableau[-1, :-1] >= 0):
break # Оптимум достигнут
entering = np.argmin(tableau[-1, :-1])
# Находим выводимую переменную (минимальное отношение)
ratios = []
for i in range(m):
if tableau[i, entering] > 0:
ratio = tableau[i, -1] / tableau[i, entering]
ratios.append((ratio, i))
if not ratios:
raise ValueError("Задача неограничена")
_, leaving = min(ratios)
# Нормализуем строку выводимой переменной
pivot = tableau[leaving, entering]
tableau[leaving] /= pivot
# Обнуляем столбец вводимой переменной в других строках
for i in range(m + 1):
if i != leaving:
factor = tableau[i, entering]
tableau[i] -= factor * tableau[leaving]
# Извлекаем решение
solution = np.zeros(n)
for i in range(n):
col = tableau[:, i]
if np.sum(col == 1) == 1 and np.sum(col != 0) == 1:
row = np.where(col == 1)[0][0]
if row < m:
solution[i] = tableau[row, -1]
optimal_value = tableau[-1, -1]
return solution, -optimal_value # Возвращаем максимум
# Пример: Максимизировать 3x + 4y
# При условиях: x + y <= 4, 2x + y <= 5, x,y >= 0
c = np.array([3, 4]) # Целевая функция
A = np.array([[1, 1], # Ограничения
[2, 1]])
b = np.array([4, 5]) # Правые части
solution, optimal_value = simplex_method(c, A, b)
print("Симплекс-метод:")
print(f"Решение: x = {solution[0]:.2f}, y = {solution[1]:.2f}")
print(f"Максимальное значение: {optimal_value:.2f}")
print(f"Проверка ограничений:")
print(f" x + y = {solution[0] + solution[1]:.2f} <= 4")
print(f" 2x + y = {2*solution[0] + solution[1]:.2f} <= 5")
24: Интерполяционный многочлен Лагранжа
Описание: Построение многочлена, проходящего через заданные точки.
Методика: Формула Лагранжа для интерполяции.
def lagrange_interpolation(points):
"""
points: список кортежей (x, y)
Возвращает функцию-полином Лагранжа
"""
def L(k, x, points):
"""Вычисление k-го базисного полинома Лагранжа"""
result = 1
x_k = points[k][0]
for i, (x_i, _) in enumerate(points):
if i != k:
result *= (x - x_i) / (x_k - x_i)
return result
def polynomial(x):
"""Полином Лагранжа"""
result = 0
for k, (_, y_k) in enumerate(points):
result += y_k * L(k, x, points)
return result
return polynomial
# Пример: интерполяция квадратичной функции
import numpy as np
# Задаем точки: y = x^2
points = [(-2, 4), (-1, 1), (0, 0), (1, 1), (2, 4)]
# Строим интерполяционный полином
poly = lagrange_interpolation(points)
# Проверяем в точках
print("Интерполяционный полином Лагранжа:")
print("Точки: (x, фактическое y, интерполированное y)")
for x, y_true in points:
y_interp = poly(x)
print(f" ({x}, {y_true}, {y_interp:.6f})")
# Проверяем в промежуточных точках
print("\nПроверка в промежуточных точках:")
test_points = [-1.5, -0.5, 0.5, 1.5]
for x in test_points:
y_true = x**2
y_interp = poly(x)
print(f" x={x:4.1f}: x²={y_true:5.2f}, интерполяция={y_interp:8.6f}, "
f"погрешность={abs(y_true - y_interp):.6f}")
# Визуализация
import matplotlib.pyplot as plt
x_vals = np.linspace(-2.5, 2.5, 100)
y_true_vals = x_vals**2
y_interp_vals = [poly(x) for x in x_vals]
plt.figure(figsize=(10, 6))
plt.plot(x_vals, y_true_vals, 'b-', label='y = x²', alpha=0.7)
plt.plot(x_vals, y_interp_vals, 'r--', label='Полином Лагранжа', alpha=0.7)
plt.scatter([p[0] for p in points], [p[1] for p in points],
color='red', s=100, zorder=5, label='Узлы интерполяции')
plt.xlabel('x')
plt.ylabel('y')
plt.title('Интерполяция полиномом Лагранжа')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()
Итоговый набор из 20 нестандартных задач:
- Числа Фибоначи через матрицы - O(log n) алгоритм
- Совершенные числа - теория чисел
- Числа Армстронга - комбинаторика
- Алгоритм Кадане - динамическое программирование
- Разбиения числа - комбинаторная генерация
- Задача о рюкзаке 0/1 - динамическое программирование
- Расстояние Левенштейна - динамическое программирование
- Задача Иосифа Флавия - математическая рекурсия
- Расстановка ферзей - бектрекинг
- Алгоритм Штрассена - умножение матриц
- Ханойские башни - рекурсия и итерация
- Линейное решето Эратосфена - теория чисел
- Циклический алгоритм Кадане - оптимизация
- Дробный рюкзак - жадный алгоритм
- Метод Гаусса - линейная алгебра
- Числа Каталана - комбинаторика
- Быстрое преобразование Фурье - численные методы
- Meet-in-the-Middle - оптимизация перебора
- Дерево Фенвика - структуры данных
- Пифагоровы тройки - теория чисел
- Алгоритм Карацубы (умножение чисел)
- RSA шифрование (криптография)
- Симплекс-метод (оптимизация)
- Полином Лагранжа (интерполяция)
Ключевые моменты:
- Оптимизация алгоритмов - от экспоненциальных к полиномиальным (задачи 1, 18)
- Разделяй и властвуй - FFT и Карацуба (задачи 17, бонус)
- Динамическое программирование - рюкзак, расстояние Левенштейна (задачи 6, 7)
- Комбинаторика и теория чисел - числа Каталана, решето (задачи 12, 16)
- Структуры данных - дерево Фенвика (задача 19)
Эти задачи охватывают ключевые алгоритмические техники и часто встречаются на собеседованиях в IT-компаниях.