Задача
Десятичное число 585 = 1001001001 (в двоичной системе), является палиндромом по обоим основаниям.
Найдите сумму всех чисел меньше миллиона, являющихся палиндромами по основаниям 10 и 2.
(Пожалуйста, обратите внимание на то, что палиндромы не могут начинаться с нуля ни в одном из оснований).
Решение
То, что палиндромы не могут начинаться с нуля, означает, что они не могут и оканчиваться нулём. Между тем, в двоичной системе любое чётное число оканчивается нулём. Значит, нужно перебирать только нечётные числа.
Как определить палиндром? Гуру-питонист, конечно, переведёт число в строку, а потом вызовет функцию reverse(). Но мы так делать не будем.
Мы будем брать остаток от деления на 10, то есть последнюю цифру числа, и переносить её в начало другого числа. Одно число будет последовательно делиться на 10, а другое наоборот, умножаться, и цифры в нём будут идти в обратном порядке.
Эта функция определяет палиндром по основанию 10, и на самом деле вместо 10 можно подставить любое основание, хоть 2, хоть 3, хоть 16. Всё будет работать так же.
Но для основания 2 я всё-таки написал свою функцию:
По сути это то же самое, только операции умножения и деления заменены битовыми сдвигами, а взятие остатка делается через логическое "и".
В теории такие операции быстрее, но на практике проверять лень. Хотя я всё-таки проверил и да, быстрее примерно в 2 раза.
Осталось только сделать перебор всех нечётных чисел до миллиона:
Опять же, если is_pali2() считается быстрее, чем is_pali10(), то её надо вызывать первой, но в то же время в двоичной системе больше разрядов, чем в десятичной, значит на то же самое число потребуется больше итераций. Поэтому я интуитивно поставил is_pali10() на первое место. Проверка показала, что разницы нет.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: