Project Euler (answers)

Проект Эйлера: Ответ и решение 6 задачи (Разность между квадратом суммы и суммой квадратов)

Проект Эйлера (6 задача) легко решается простым перебором, однако всегда есть и другие варианты. Например – геометрическое решение

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

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

Сумма квадратов первых десяти натуральных чисел равна:

1² + 2² + … + 10²= 385

Квадрат суммы первых десяти натуральных чисел равен:

(1 + 2 + … + 10)² = 55²= 3025

Следовательно, разность между квадратом суммы и суммой квадратов первых десяти натуральных чисел составляет 3025 − 385 = 2640.
Найдите разность между квадратом суммы и суммой квадратов первых ста натуральных чисел.

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

Решение простым перебором

Геометрическое решение

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

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

Решение простым перебором - проект Эйлера (6 задача)

В программе перебираем натуральные числа от одного до сотни.

На каждой итерации:

суммируем квадраты чисел в переменную sum_sq;
складываем натуральные числа в другую переменную – sum_num;

Ответ (согласно заданию) находим как разность между квадратом суммы чисел и суммой квадратов.

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

printf("%d", answ);

Функция printf() служит для форматированного вывода.
%d – спецификатор преобразований преобразует информацию к необходимому виду. В данном случае указывает на целое число со знаком в десятичной форме.

num++

То же самое, что и: num = num + 1

sum_num += num

То же самое, что и: sum_num = sum_num + num

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

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

Геометрическое решение - проект Эйлера (6 задача)

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

Представим числа в виде геометрических фигур на бумаге. Одна клеточка – это 1, две – 2 и так далее.

Потому сумме чисел 1 + 2 + 3 + 4 + 5 будет соответствовать площадь фигуры, образованной этими клетками (15 клеток). На рисунке видно, что полученная фигура примерно соответствует половине квадрата со стороной 5 клеток. Однако видно, что половина клеток на диагонали квадрата не вошла (выделено зеленым на фигуре). Их нужно добавить отдельно.

В итоге получаем следующую формулу для расчета суммы чисел от 1 до 5:

(5 * 5 + 5) / 2

Т.е. берем площадь квадрата, добавляем клеточки диагонали и делим все пополам.

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

А теперь представим числа в виде объемных геометрических фигур. Один кубик – это 1, четыре – это 2^2 и так далее.

Получим своеобразную пирамидку из этих кубиков.

Еще тысячу лет назад математики сообразили, что из шести таких пирамидок всегда собирается параллелепипед, определенных пропорций.

В итоге искомая формула будет:

(num * (num + 1) * (2 * num + 1)) / 6

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

В итоге ответ на 6 задачу проекта Эйлера составил 25164150, программа работает довольно быстро (0.0 секунд).

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

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

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

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

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

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