Как найти число палиндром в диапазоне

I need some help with below:

write a function (main) which will ask the user to enter a starting and ending number range (inclusive). Count through the numbers using a while loop. Add the number into the total only if it is a palindrome (call isNumberPalindrome). Print the total after adding the numbers.’

What I have so far for this (main) function is…

def main():
start = int(input("Enter a number to start counting at:"))
end = int(input("Enter a number to end counting at:"))
while start <= end:
    print(start)
    start = start + 1

AND here is what I have for my (isNumberPalindrome) function.

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

So far my (main) function asks for user input(starting and ending number) and counts them using a while loop. I have no idea what to add to my code for (main) function next to achieve «Add the number into the total only if it is a palindrome (call isNumberPalindrome). Print the total after adding the numbers.»

Thanks for the help.

So far with the code provided to me, this is what happens.

Enter a number to start counting at:1
Enter a number to end counting at:6
1
Traceback (most recent call last):
File "C:/Users/Tyler/Desktop/AWDADXC.py", line 38, in <module>
main()
File "C:/Users/Tyler/Desktop/AWDADXC.py", line 33, in main
if isNumberPalindrome(start):
File "C:/Users/Tyler/Desktop/AWDADXC.py", line 18, in isNumberPalindrome
if len(s) < 1:
TypeError: object of type 'int' has no len()

Does anyone know what is wrong?

Продолжаем разбирать задачки с сайта Leetcode. В прошлый раз было про массив и сумму чисел, теперь тоже необычное. 

Условия

В переменной X лежит какое-то целое число

Задача — проверить, является ли это число палиндромом.

Задача со звёздочкой — проверить на наличие палиндрома, не используя строки.

Палиндром — это когда строка или число одинаково читается в прямом и обратном направлении:

121 — это палиндром.

А роза упала на лапу Азора — тоже палиндром (если не считать заглавных букв).

12321 — и это палиндром.

Решение, где используем строки

Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.

Сначала решим это на Python. Тут вообще суть в одной строке:

X = 121
if str(X) == str(X)[::-1]:
    print("Это палиндром")
else:
    print("Это не палиндром")

Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию [::-1]. Работает это так:

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

Теперь решим это же, но на JavaScript:

var X = 121;
if (X.toString().split("").reverse().join("") == X.toString()) {
    console.log("Это палиндром")
} else {
    console.log("Это не палиндром")
}

Здесь мы использовали другой метод пересборки:

Решение без строк

Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.

Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:

function palindrome(x) {
}

Теперь обработаем три стандартные ситуации:

Запишем это на JavaScript:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
}

Чтобы проверить, является ли число палиндромом или нет, можно сделать так: отрезаем от числа цифры справа по одной, добавляем их в начало нового числа и постоянно сравниваем новое и старое значение. Если они станут равны — перед нами палиндром. Читайте комментарии, чтобы вникнуть в то, что происходит в коде:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
    // сюда будем собирать число в обратном порядке
    temp = 0;
    // а тут будем хранить промежуточные значения икса
    preX = x;
    // пока не дойдём до середины числа — повторяем цикл
    while (x > temp) {
        // берём самую правую цифру в числе — это остаток от деления на 10
        pop = x%10;
        // запоминаем старое значение переменной X
        preX = x;
        // и отрезаем от переменной последнюю цифру — делаем это через целую часть деления на 10
        x /= 10;
        // добавляем отрезанную цифру к обратной переменной
        temp = temp*10 + pop;
    }
    // если обратная переменная совпала с оставшейся половиной исходной переменной — это палиндром
    // мы добавляем сравнение с предыдущей версией исходной половины (которая на 1 цифру больше) на тот случай, если исходное число состояло из нечётного количества символов и его нельзя было бы разбить строго пополам
    if(x == temp || preX == temp)
        return true;
    // 
    else
        return false;
};

Для запуска кода просто вызываем функцию и передаём её нашу переменную:

// запускаем код
var X = 121;
console.log(palindrome(X));

Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.

f(k) — число чисел-палиндромов из k разрядов. Тогда

• f(2k) = 9·10^k-1;
• f(2k + 1) = 9·10^k.

Девятка отвечает за цифры старшего разряда — от единицы до девяти. Степень десятки — за остальные разряды из старшей половины числа.

g(k) — число чисел-палиндромов из не более чем k разрядов. Тогда

• g(2k) = 2·10^k — 2;
• g(2k + 1) = 11·10^k — 2.

Доказывается по индукции (g(n + 1) = g(n) + f(n + 1)).

h(n) — число чисел-палиндромов не более n. Я покажу на примере как его можно сосчитать быстро. Пусть n = 345678. Разобъём все палиндромы не более n на группы:

     ? - палиндромы длины один. Их f(1)
    ?? - палиндромы длины два. Их f(2)
   ??? - палиндромы длины три. Их f(3)
  ???? - палиндромы длины четыре. Их f(4)
 ????? - палиндромы длины пять. Их f(5)

1????1 - таких палиндромов 100 (все палиндромные цифровые строки длины 4)
2????2 - тоже самое (первые цифры от единицы до 3 - 1)

30??03 - таких палиндромов 10 (все палиндромные цифровые строки длины 2)
31??13 - тоже самое
32??23 - тоже самое
33??33 - тоже самое (вторые цифры от нуля до 4 - 1)

340043 - такой палиндром один (все палиндромные цифровые строки длины 0)
341143 - тоже самое
342243 - тоже самое
343343 - тоже самое
344443 - тоже самое (третьи цифры от нуля до 5 - 1)

345543 - такой палиндром один, но надо отдельно проверить
         что он не больше n

Получается такая программа:

def ps_count(k):
    """ число палиндромных строк длины k """
    return 10 ** ((k + 1) // 2)


def p_count_10p(k):
    """ число чисел-палиндромов не более k разрядов """
    return 10 ** ((k + 1) // 2) + 10 ** (k // 2) - 2


def p_count(n):
    """ число чисел-палиндромов не более n """

    if n == 0:
        return 0

    digits = tuple(map(int, str(n)))
    m = len(digits)

    # короткие палиндромы
    c = p_count_10p(m - 1)

    for i in range((m + 1) // 2):
        # палиндромы вида ABC????CBA
        c += (digits[i] - (0 if i > 0 else 1)) * ps_count(m - 2 * (i + 1))

    if digits[:m // 2 - 1::-1] <= digits[(m + 1) // 2:]:
        # палиндром вида ABCDEEDCBA
        c += 1

    return c


def main():
    n1, n2 = map(int, input().split())
    # число чисел-палиндромов диапазоне [n1, n2]
    print(p_count(n2) - p_count(n1 - 1))


main()

echo 1026376 1_000_000_000_000_000  | python pcount.py
109997973

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

Войти на сайт

или

Забыли пароль?
Еще не зарегистрированы?