Project Euler (answers)

Проект Эйлера: Ответ и решение 9 задачи (Особая тройка Пифагора)

Проект Эйлера (9 задача) заставит вспомнить суть детского стишка про “Пифагоровы штаны” и решается довольно легко. Однако все можно улучшить

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

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

Тройка Пифагора – три натуральных числа a < b < c, для которых выполняется равенство
a² + b² = c²
Например, 3² + 4² = 9 + 16 = 25 = 5².
Существует только одна тройка Пифагора, для которой a + b + c = 1000.
Найдите произведение abc.

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

Функции, используемые для решения

Задача Эйлера 9 – решение

Ответ и скорость работы программы

Функции, используемые для решения - проект Эйлера (9 задача)

"Пифагоровы штаны во все стороны равны"

С помощью этой нехитрой поговорки мы на математике запоминали признак прямоугольности треугольника. А именно формулу:

a^2 +b^2 = c^2

Т.е. “сумма квадратов катетов треугольника (прямоугольного) равна квадрату его гипотенузы”. Не знаю, как это работает, однако запомнить помогало.

Функция is_triple

Функция is_triple принимает числа a, b, c и возвращает true, если они являются искомой тройкой. Работа ее основана на вышеизложенном признаке прямоугольного треугольника (a^2 +b^2 = c^2), однако есть одно улучшение:

Функция не вычисляет квадраты чисел, а принимает массив с заранее вычисленными квадратов натуральных чисел от 1 до 1000. Это происходит потому, что иначе одни и те же числа будут многократно (тысячи раз) вновь и вновь возводиться в квадрат.

Функция is_correct

Функция is_correct проверяет корректность полученной “тройки Пифагору” условию задачи (a + b + c = 1000). Она возвращает true, если условие корректно, иначе – false.

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

stdbool.h

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

is_triple(int sq[ ])

Функция is_triple принимает в качестве параметра указатель на массив sq[ ]. В итоге изнутри функции становится возможным обращаться к элементам массива (находящегося в функции main) по их индексу sq[a].

a + b + c == 1000

Если значение справа и слева от “==” равны, то вернет true. Иначе – false

Проект Эйлера (9 задача) - решение

Вычисляем квадраты натуральных чисел

Глядя на условия задачи, первое, что приходит в голову – это для чисел a, b и c перебрать в цикле все числа от одного до тысячи. И каждую комбинацию чисел проверить на удовлетворение условий задачи. Мы конечно, так делать не будем, потому что 1000 вариантов значений числа a на 1000 значений b, да на 1000 значений c дадут миллиард вариантов.

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

Например:

a = 123 проверяем с 1000 вариантов числа b * 1000 вариантов числа c

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

arr_sq[4] =16;

Т.е. индекс массива соответствует натуральному числу (4), а значение по этому индексу – квадрату числа (16).

Сокращаем диапазон возможных значений чисел a, b и c

Чтобы не перебирать миллиард комбинаций чисел воспользуемся несколькими соображениями:

Поскольку a + b + c = 1000, то такие варианты как a=1000, b=1000, c=1000 заведомо не подходят, как и a=1, b=1, c=1. Потому при изменении одного числа (c) принимаем, что сумма оставшихся находится как (a+b) = 1000 – с.
Далее, условие a^2 +b^2 = c^2 есть ничто иное как условие прямоугольности треугольника. А никакая сторона треугольника не может быть длиннее суммы двух других сторон (c < a+b). Потому не нужно перебирать до 1000, достаточно до 500 (если с = 500, то a+b=500).
Перебирая значения стороны b от максимального (b=a+b) до минимального, будем вычислять значение числа a (a = (a+b)-b). При этом значения числа b будут уменьшаться, числа a – увеличиваться, и в некоторый момент сравняются. Потому в момент (a>b) необходимо прерывать цикл, т.к. значения будут повторяться. a будет принимать значения, уже ранее принятые b и наоборот.
Поскольку по условиям ответ подразумевается только один, прерываем вычисления, как только он будет найден.

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

break

Прерывает текущий цикл. Например:

for(1 условие)
{
- for(2 условие)
- {
  - какой-то код…
  - break;
- }
}

Прервется цикл for(2 условие).

Не прервется цикл for(1 условие) – продолжится со следующей итерации.

Не прервется работа функции

return

Прерывает работу функции и возвращает результат

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

Для измерения времени работы программы подключаем библиотеку 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

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

В итоге, понимание физического смысла приведенного в задании уравнения может сократить объем вычислений. Ответ на 9 задачу проекта Эйлера составил – 31875000. Программа работает быстро – за 0.0 секунд.

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

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

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

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

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