Числовые задачи на Python: целочисленная арифметика и алгоритмы

Раздел: Задачи -> Числовые задачи на Python

Эффективное решение задачи о палиндроме числа

Наиболее эффективный способ проверки, является ли целое число палиндромом, основан на математическом развороте числа без преобразования в строку. Этот подход использует только операции целочисленной арифметики и требует O(n) времени, где n количество цифр числа, а дополнительная память не зависит от длины числа.

def is_palindrome(num):
    if num < 0:
        return False
    reversed_num = 0
    temp = num
    while temp > 0:
        digit = temp % 10
        reversed_num = reversed_num * 10 + digit
        temp //= 10
    return num == reversed_num

задачи на целые числа python (задачи на целые числа в python)

Сначала проверяется знак числа: отрицательные числа не считаются палиндромами (знак минус не симметричен). Затем в цикле извлекаются цифры справа и собирается перевёрнутое число. Сравнение оригинала с результатом даёт ответ.

Типичные ошибки:

Забывают обработать отрицательные числа (число -121 не может быть палиндромом).
Используют оператор / вместо целочисленного деления //, что приводит к ошибке типа при работе с плавающей точкой.
Не восстанавливают исходное значение num, если переменная temp не использовалась.

Как проверить палиндром с помощью преобразования в строку?

Это самый лаконичный способ, особенно удобный для быстрого прототипирования или когда производительность не критична.

def is_palindrome_str(num):
    s = str(num)
    return s == s[::-1]

Python произведение (произведение в python)

Число преобразуется в строку, затем строка сравнивается со своей обратной копией. Проблема возникает для отрицательных чисел: str(-121) == '-121' и обратная строка '121-' не совпадают, поэтому такой палиндром корректно отбрасывается. Однако для больших чисел (десятки тысяч цифр) этот подход потребляет много памяти, так как создаётся дублирующая строка.

Возможные затруднения:

Обратная строка создаётся через срез, что для длинных строк может быть медленнее арифметического разворота.
Необходимость импорта дополнительных модулей отсутствует.

Как реализовать рекурсивную проверку палиндрома?

Рекурсивный подход использует строку и сравнивает крайние символы, сокращая длину на каждом шаге.

def is_palindrome_rec(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome_rec(s[1:-1])

def check_palindrome(num):
    s = str(num)
    if s[0] == '-':
        return False
    return is_palindrome_rec(s)

сумма чисел задача python (сумма чисел на python)

Это решение демонстрирует принцип «разделяй и властвуй». Основной недостаток: глубина рекурсии равна половине длины числа, что может превысить лимит рекурсии Python для чисел с тысячами цифр. Кроме того, на каждом шаге создаются новые строки, что неэффективно по памяти.

Проблемы:

Рекурсия может вызвать RecursionError при большой длине числа (по умолчанию лимит 1000).
Постоянное создание подстрок замедляет выполнение.

Как обработать палиндром с учётом отрицательных чисел и нуля?

В некоторых задачах требуется проверять палиндромность абсолютного значения числа или же число 0 считается палиндромом. Эффективное решение можно дополнить условием.

def is_palindrome_ext(num):
    if num == 0:
        return True
    if num < 0:
        return False
    reversed_num = 0
    original = num
    while num > 0:
        reversed_num = reversed_num * 10 + num % 10
        num //= 10
    return original == reversed_num

Здесь явно обрабатывается ноль (часто его считают палиндромом) и отрицательные числа (сразу возвращается False). Такой вариант даёт полный контроль над всеми граничными случаями.

Распространённая ошибка:

Не учтён случай, когда число заканчивается на ноль (например, 10). reversed_num не может начаться с нуля, поэтому 10 даст 1, что не равно 10 – это корректно, так как 10 не палиндром. Но если бы требовалось считать 010 палиндромом, то это невозможно в целочисленной арифметике, поэтому задача обычно формулируется без ведущих нулей.

Расширенные примеры других числовых задач

Сумма цифр числа

Вычисление суммы цифр целого числа. Можно использовать строковый или арифметический метод. Ниже приведён арифметический способ.

Пример

def sum_digits(n):
    n = abs(n)  # учитываем отрицательные
    total = 0
    while n > 0:
        total += n % 10
        n //= 10
    return total

print(sum_digits(12345))  # 15
print(sum_digits(-987))   # 24

15
24

Факториал числа (итеративный)

Вычисление факториала с помощью цикла. Учитываются только неотрицательные целые числа.

Пример

def factorial(n):
    if n < 0:
        return None
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial(5))   # 120
print(factorial(0))   # 1

120
1

Числа Фибоначчи (итеративный)

Генерация n-го числа Фибоначчи без рекурсии для экономии памяти.

Пример

def fibonacci(n):
    if n < 0:
        return None
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci(10))  # 55
print(fibonacci(0))   # 0

55
0

Наибольший общий делитель (алгоритм Евклида)

Реализация НОД для двух целых чисел с помощью рекурсии или цикла.

Пример

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(48, 18))  # 6
print(gcd(100, 25)) # 25

6
25

Проверка числа на простоту

Эффективная проверка: перебор делителей до квадратного корня. Дополнительно обрабатываются чётные числа.

Пример

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

print(is_prime(29))  # True
print(is_prime(1))   # False

True
False

Задачи на целые числа в Python - comments

задачи на целые числа python (python)