Задача:
Пятиугольные числа вычисляются по формуле: Pn=n(3n−1)/2. Первые десять пятиугольных чисел:
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
Можно убедиться в том, что P4 + P7 = 22 + 70 = 92 = P8. Однако, их разность, 70 − 22 = 48, не является пятиугольным числом.
Найдите пару пятиугольных чисел Pj и Pk, для которых сумма и разность являются пятиугольными числами и значение D = |Pk − Pj| минимально, и дайте значение D в качестве ответа.
Решение
Будем перебирать числа-кандидаты попарно во внешнем и внутреннем циклах. Для каждой пары найдём сумму и разность и проверим, пентачисла ли они.
Как определить пентачисло? Если приглядеться, это уже было в задаче про треугольные числа:
Треугольное число это (n * n + n) / 2, а пятиугольное это (3 * n * n - n) / 2, очень похоже, не правда ли? Тут тоже можно применить решение квадратного уравнения. Предположим, число равно 70. Приводим уравнение к виду:
3 * n * n - n - 140 = 0
Вычислим дискриминант D:
b^2 - 4ac → 1 - 4 * 3 * (-140) → 1681
И первый корень:
(-b + sqrt(D)) / 2a → (1 + sqrt(1681)) / 6 → 7
Значит 70 это 7-е пентачисло, верно? Переношу функцию из предыдущей задачи в адаптированном виде:
Что интересно, я вынужден полученный корень уравнения снова превращать в пентачисло и сравнивать с изначальным числом, потому что вычисления целочисленные, и дробные части в процессе теряются. В других вариантах (которые я потом подсмотрел) просто берут остаток от деления на 6, и если он равен нулю, то всё в порядке:
return (sqrt(d) + 1) % 6 == 0;
Но в C операция взятия остатка % работает только с целыми цислами, а для вещественных нужно использовать функцию fmod():
return fmod(sqrt(d) + 1, 6) == 0.0;
И так работает, но... значительно медленнее! Поэтому я оставил свой вариант.
Как генерировать пентачисла?
В циклах нужно перебирать не все числа подряд, а только пентачисла. У нас уже есть формула для n-го числа, поэтому можно генерировать очередное пентачисло на основе индекса цикла.
Но можно сделать проще. Между первыми числами 1 и 5 разница 4, а далее эта разница каждый раз увеличивается на 3. Т.е. можно установить шаг цикла step = 4, прибавлять его к текущему числу, а затем к step прибавлять 3. Как-то так:
Как перебирать?
Никакая сумма с 1, 5 или 12 не даст пентачисло, так как заведомо меньше ближайшего следующего пентачисла. Так что внешний цикл начинаем сразу с числа 35 и шага 16, а внутренний с числа 22 и шага 13.
Внутренний цикл работает до границы, заданной внешним. Допустим, если она равна 35, то во внутреннем перебираем единственно доступную пару (22, 35). Затем диапазон увеличивается до 51, и перебираем (22, 51) и (35, 51). Диапазон будем увеличивать, пока где-то что-то не найдётся.
Ну и так как проверки начинаются всегда с меньших значений, то первое найденное решение и будет минимальным.
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач:
