РЕШИТЬ ЗАДАНИЕ НА PYTHON ПРОШУ ТЕХ КТО В НЁМ ХОРОШО РАЗБИРАЕТСЯ
Назовем число палиндромом, если оно не меняется при перестановке его цифр в обратном порядке. Напишите программу, которая по заданному числу K выводит количество натуральных палиндромов, не превосходящих K.

Входные данные
Задано единственное число K (1K100000).

Выходные данные
Необходимо вывести количество натуральных палиндромов, не превосходящих K.
Примеры
входные данный
1
выходные данные
1
входные данные
100
выходные данные
18

Для решения этой задачи напишем программу на Python, которая определяет количество натуральных палиндромов, не превосходящих заданное число $K$.

Шаги решения:

1. Определить, является ли число палиндромом: Палиндром — это число, которое читается одинаково слева направо и справа налево. Проверим это, сравнив строковое представление числа с его обратным вариантом.

2. Перебрать все числа от 1 до $K$: Пройдем по всем числам в диапазоне от 1 до $K$, проверяя каждое на палиндромичность.

3. Подсчитать количество палиндромов: Если число является палиндромом, увеличиваем счетчик.

4. Вывести результат.

Программа

python
def count_palindromes(K):
    count = 0
    for i in range(1, K + 1):
        # Проверяем, является ли число палиндромом
        if str(i) == str(i)[::-1]:
            count += 1
    return count
# Чтение входных данных
K = int(input("Введите число K: "))
# Вычисление и вывод результата
print(count_palindromes(K))

Объяснение кода

1. Функция count_palindromes:

   • Принимает $K$ как входной параметр.
   • Проходит по всем числам от 1 до $K$.
   • Проверяет, равна ли строка числа её обратной версии (str(i) == str(i)[::-1]).
   • Увеличивает счетчик для каждого палиндрома.

2. Основной блок:

   • Считывает число $K$ с клавиатуры.
   • Вызывает функцию count_palindromes.
   • Выводит результат.

Пример работы программы

Входные данные:

100

Выходные данные:

18

Объяснение:

Палиндромы от 1 до 100: 1, 2, 3, ..., 9, 11, 22, 33, 44, 55, 66, 77, 88, 99. Всего 18 чисел.

Временная сложность

• Перебор чисел от 1 до $K$ требует $O(K)$.
• Проверка числа на палиндромичность (реверс строки) выполняется за $O(d)$, где $d$ — количество цифр в числе (максимум 5 для $K \leq 100000$).
• Итоговая сложность: $O(K \cdot d)$, где $d \approx \log_{10} K$.

Программа успешно решает задачу для диапазона $K$ от 1 до 100000.