Проект Эйлера (36 задача). Просто перебрать и проверить все числа до миллиона вполне возможно, однако лучше сразу получать палиндромы.
Узнать больше в телеграм-канале: ProjectEuler++
Десятичное число 585 = 10010010012 (в двоичной системе), является палиндромом по обоим основаниям.
Найдите сумму всех чисел меньше миллиона, являющихся палиндромами по основаниям 10 и 2.
(Пожалуйста, обратите внимание на то, что палиндромы не могут начинаться с нуля ни в одном из оснований).
Поскольку функция main() получилась объемной, потому чтобы не “мельчить”, решил разбить ее на два скриншота.
Первое же улучшение, которое приходит в голову, глядя на условие задачи – это получать сразу палиндромы. Потому что иначе при переборе понадобится проверить 1000000 чисел.
Если же получать палиндромы, просто используя цифры одного числа зеркально:
… то понадобится перебрать числа только до 1000. Что в итоге сократит вычислений сразу на три порядка.
Однако зеркальным удвоением числа можно получить только палиндромы с четным количеством цифр в числе.
Как получать числа вида?:
Их можно получать перебором двух чисел: одной центральной цифры (от 0 до 9) и двух зеркальных чисел по краям (от 1 до 99).
Этот перебор 10 цифр на 100 в итоге даст еще 1000 комбинаций. Однако это опять-таки сильно меньше первоначального миллиона.
В итоге в программе перебираются все возможные палиндромы по основанию 10.
Поскольку палиндромы по основанию 10 мы получаем сразу, потому их остается только проверить на “палиндромность” по основанию 2. Соответственно напрашиваются и битовые операции для этой проверки.
Подробнее об алгоритме – ниже в описании соответствующих функций.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Данная функция получает из исходного числа большее, с цифрами, расположенными зеркально.
На первом этапе определяется порядок числа. Множитель (fact) увеличивается до тех пор, пока не достигнет нужного порядка:
Далее исходное число раскладывается на цифры и с помощью двух вспомогательных множителей формируются две половины палиндрома.
Один множитель (f_less) уменьшается (от 100 до 1) и формирует меньшую половину:
Второй (f_more) увеличивается (от 1000 до 100000) и формирует большую половину числа:
Их сумма в итоге образует искомый палиндром.
Похожая на предыдущую функция. Тут также на первом этапе формируется множитель, однако, в этот раз, на порядок больший числу.
Например, формируем палиндром на основе 3 и 12.
Тогда для числа 12 будет сформирован множитель fact = 100. Так происходит, потому что с его помощью должна получиться средняя цифра будущего палиндрома.
3 в итоге станет 300 и встанет ровно в середину пятизначного числа.
Точно так же как и в предыдущей функции, из исходного числа формируются большая и меньшая части:
Сумма всех трех чисел в итоге сформирует искомый палиндром:
Напомню, что десятичные числа в двоичном вид представляют собой ряд нолей и единиц. Возьмем пример из задания:
С двоичными операциями можно совершать ряд действий.
Битовый сдвиг влево. Все биты числа сдвигаются влево, крайне правый бит заполняется нулем:
То же самое, однако теперь все биты сдвигаются вправо. Крайне правый бит теряется:
Побитовое “И“. Два числа сравниваются побитно и 1 будет только в тех битах, в которых в обоих числах стояло 1:
Алгоритм функции в итоге следующий:
Число number в итоге постепенно уменьшается:
А palindrome постепенно растет:
Их совпадение в итоге и будет признаком, что исходное число – палиндром.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
