Project Euler (answers)

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

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

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

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

В таблице 20×20 (внизу) четыре числа на одной диагонали выделены красным.

Произведение этих чисел 26 × 63 × 78 × 14 = 1788696.
Каково наибольшее произведение четырех подряд идущих чисел в таблице 20×20, расположенных в любом направлении (вверх, вниз, вправо, влево или по диагонали)?

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

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

Заносим числа в массив
Решение задачи

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

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

Описание идеи алгоритма

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

по горизонтали;
по вертикали;
по диагонали – вправо вниз;
по диагонали – вправо вверх.

Во-вторых, в таблице есть нули (00) и произведение на них тоже будет равно нулю и может не вычисляться. Однако нулей в таблице всего семь штук. Потому реализовывать алгоритм их пропуска не будем.

Заносим числа в массив

Заносим числа в виде строки

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

Можно конечно забить вручную, однако, это не наш метод. Потому сначала сохраним их в виде строки, просто скопировав из задания и “закавычив” при сохранении в num_str[].

Заносим числа из строки в массив

Что такое строка? По сути своей – это обычный массив чисел. Однако есть отличия:

В конце этого массива обязательно стоит символ окончания строки ‘\0’.
Цифры в таком массиве означают не сами себя, а численный код того или иного символа. Например, 65 означает символ ‘А’.

Значения всех кодов хранятся в так называемой сводной таблице кодов ASCII. Однако нас интересует, что символ ‘0’ (ноль) имеет код 48, а ‘1’ (один) – 49 и т.д.

В итоге вполне достаточно из кода символов цифр вычитать 48, чтобы получить сами цифры. При этом десятки будут получаться умножением числа на десять (*10).

Также пропускаем символ (‘ ‘) потому что числа разделены пробелами.

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

i++

Инкремент. Выполняется после использования переменной i.

i++ тоже самое, что и i = i + 1

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

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

#include <time.h>

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

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

(double)

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

Решение - проект Эйлера (11 задача)

Задаем направление чисел в ряду

У числа в таблице есть две координаты – i и j. Для примера возьмем горизонтальный ряд из четырех чисел:

число1(0,0) * число2(0,1) * число3(0,2) * число4(0,3)

Видно, что координаты чисел в ряду подчиняются линейному закону и отличаются друг от друга на одну и ту же величину:

i = 0 и не изменяется, потому что ряд горизонтальный;
j = j + 1 – число справа отличается на единицу от предыдущего.

В итоге достаточно знать координаты только первого числа и необходимое смещение, чтобы вычислить координаты (и значения) остальных трех чисел ряда.

В итоге смещение координат в зависимости от направления сохраним в двумерном массиве:

{0, 1} – смещение i = 0, cмещение j = +1 – горизонтальный ряд чисел;
{1, 0} – смещение i = +1, cмещение j = 0 – вертикальный ряд чисел;
{1, 1} – смещение i = +1, cмещение j = +1 – ряд чисел по диагонали вправо-вниз;
{1, -1} – смещение i = +1, cмещение j = -1 – ряд чисел по диагонали вправо-вверх.

Вычисляем искомые произведения

Порядок вычисления следующий:

Перебираются все числа массива[i][j] и выбирается начальное число ряда.
Выбирается направление ряда чисел (по очереди выбираются смещения для всех четырех направлений).
Вычисляется произведение четырех чисел в заданном направлении. При этом проверяется то, что индексы чисел ряда не выходят за пределы массива.
В итоге обновляется максимальное значение ответа.

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

answ = (answ > prod) ? answ : prod;

Условное тернарное выражение. Если answ больше prod, то вернет answ, иначе – prod.

Оператор “ИЛИ”

%d %f

Спецификатор %d преобразует информацию в целое число со знаком в десятичной форме.

%f – вещественное число в виде десятичной дроби.

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

В итоге ответ на 11 задачу проекта Эйлера составил 70600674, программа работает практически мгновенно – быстрее 1 миллисекунды.

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

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

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

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

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

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