Project Euler (answers)

Language:

Проект Эйлера: Ответ и решение 4 задачи (Наибольшее произведение-палиндром)

Проект Эйлера (4 задача) создает ложное впечатление внешней простотой. Но она хранит в себе довольно интересные возможности оптимизации.

Узнать больше в телеграм-канале: ProjectEuler++

Условия задачи

Число-палиндром с обеих сторон (справа налево и слева направо) читается одинаково. Самое большое число-палиндром, полученное умножением двух двузначных чисел – 9009 = 91 × 99.
Найдите самый большой палиндром, полученный умножением двух трехзначных чисел.

Содержание статьи

Работа функции для определения, является ли число палиндромом

Описание работы программы

Примечания

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

Работа функции для определения, является ли число палиндромом - проект Эйлера (4 задача)

Задача Эйлера 4 в своем решении потребует определять, является ли число палиндромом или нет.

Для простоты поясню работу функции (смотрите выше) is_palindrom() на примере .

Допустим, функция принимает в качестве проверяемого числа 123 и сохраняет его в переменной check_num = 123. Также нам понадобится переменная revers_num для хранения обратного числа (revers_num = 0).

Пока check_num не равно нулю, будут выполняться следующие операции:

check_num = 123, revers_num = 0;
от check_num = 123 отрезается младший регистр (123%10 = 3) и в итоге прибавляется к обратному числу revers_num;
check_num = 12, revers_num = 3;
revers_num увеличивает регистр своих чисел (revers_num *= 10) revers_num = 30;
далее от check_num (12) отрезается 2 и прибавляется к revers_num (30 + 2);
check_num = 1, revers_num = 32;
после аналогичной итерации получим check_num = 0, revers_num = 321;
цикл закончен.

Сравнение обратного числа revers_num = 321 и изначально заданного для проверки num = 123, вернет false – потому что проверяемое число не палиндром.

Описание работы программы - проект Эйлера (4 задача)

Алгоритм работы программы

в двух циклах for() перебираются множители i и j;
перемножаются;
в итоге, если их произведение является палиндромом и максимальным среди уже найденных, обновляем ответ.

Особенности алгоритма, ускоряющие работу программы

Перебираться будут не все числа, а только в диапазоне от 99 до 999, потому что в условиях задачи речь идет о двузначных числах.
В цикле for() перебираем значения от большего к меньшему(от 999 до 99). Это позволит при нахождении палиндрома прерывать цикл, с помощью break – потому что остальные числа будут заведомо меньше (999 * 999 > 999 * 998).
Существует любопытный математический факт – “Все палиндромы с четным числом цифр делятся на 11“. Потому один из циклов for() перебирает числа от 990 (делится на 11) до 99 (тоже делится) с шагом 11. В итоге это уменьшает объем вычислений на порядок.
чтобы уменьшить количество вызовов функции is_palindrom() проверка на максимальность числа if(answ > num) вынесена перед ней.

* Примечания:

stdbool.h

Подключаем стандартную библиотеку языка Си для работы с булевым типом данных. Для стандарта C99 булевый тип _Bool, который принимает значения 0 и 1. Данная библиотека позволяет использовать более привычный тип данных bool со значениями false и true.

revers_num *= 10

То же самое, что

revers_num = revers_num * 10

check_num % 10

check_num % 10 возвращает остаток от целочисленного деления 1234 % 10 = 4

revers_num += check_num % 10

То же самое, что

revers_num = revers_num + check_num % 10

revers_num /= 10

То же самое, что

revers_num = revers_num / 10

revers_num == num

Если значение переменных revers_num и num равны, то вернет true. Иначе – false

break

Прерывает текущий цикл:

for (int i = 999; i > 99; i–) // этот цикл не прерывается

{

for (int j = 990; j > 99; j -= 11) // break прервет этот цикл

{

num = i*j;

if(answ > num)

break;

Измеряем время работы программы

Для измерения времени работы программы подключаем библиотеку time.h:

#include <time.h>

С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.

* Примечания:

clock_t

clock_t это тип данных, определенный через typedef. По сути это обычный целочисленный long

(double)

(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)

CLOCKS_PER_SEC

CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000

Проект Эйлера (4 задача) - ответ и скорость работы программы

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

Задача несложная и вполне решается обычным перебором, без всяких оптимизаций. Однако вопрос встал бы во времени ее работы.

По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.

Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))

Есть вопросы, господа?

Политика конфиденциальности

Конфиденциальность