Проект Эйлера (8 задача) легко решается “в лоб” – многократным перемножением серии чисел. Однако для нее есть более “красивое” решение.
Узнать больше в телеграм-канале: ProjectEuler++
Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832.
“Найдите наибольшее произведение тринадцати последовательных цифр в данном числе.”
Первая проблема, с которой сталкиваешься в этой задаче – это длина числа. 1000-значное число в языке Си не влезет ни в один тип данных. Потому копируем число в программу в виде строки и далее преобразуем в массив чисел.
Для преобразования символов строки в числа воспользовался функцией atoi(). Однако это не самый удачный вариант, потому что эта функция служит для преобразования именно строки в число. Потому к каждому символу перед преобразованием пришлось добавлять знак окончания строки ‘\0’ и представлять именно в формате строки.
В итоге это приводит к лишним вызовам функции и замедлению программы. Подробно останавливаться на нем не будем, потому что ниже будет приведен более удачный способ данного преобразования.
По сути, это первое, что приходит в голову, глядя на условия задачи. Перемножаешь числа с 1 по 13. Потом со 2 до 14, с 3 до 15, с 4 до 16 и так далее. В итоге выбираешь максимальный результат.
Однако есть несколько моментов, которые можно улучшить:
Функция atoi(symb) служит для преобразования строки в число. Т.е. строку “0123” она преобразует в число 123. При этом:
То же самое, что и prod = prod * num_array[i + 1]
“%lld” спецификатор %d с суффиксами ll указывает, что тип выводимой переменной answ – long long int
Точно так же как в первом варианте решения, копируем число из задания в программу и сохраняем в виде строки.
Что такое строка? По сути своей – это обычный массив чисел. Однако есть отличия:
Значения всех кодов хранятся в так называемой сводной таблице кодов ASCII. Однако нас интересует, что символ ‘0’ (ноль) имеет код 48, а ‘1’ (один) – 49 и т.д.
Таким образом вполне достаточно из кода символов цифр вычитать 48, чтобы получить сами цифры. В итоге функция atoi() становится не нужна.
После того как перемножены числа с 1-го по 13-е, мы получаем произведение серии чисел от 1-го до 13-го в виде числа.
Однако далее мы не будем заново перемножать числа от 2-го до 14-го, чтобы получить следующее произведение (answ_2_14).
Вместо этого:
В итоге 12 операций перемножения 13 чисел заменены на две: одно деление и одно умножение. При этом серия из 13-ти чисел как бы смещается на одно число вправо, “ползет как змея“.
Для ясности и краткости изложения примем некоторые условные обозначения:
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Тернарный оператор ? : иначе можно записать следующим образом:
Поскольку хочется сделать “красивый” и универсальный вариант программы, воспользовался директивой препроцессора #define. С ее помощью в начале программы, моно задать как длину массива (1000), так и длину “змеи” – произведения серии чисел (13).
Так как у “змеи” есть начало и конец:
то создаем для нее структуру.
struct tip – ‘это новый тип данных и он будет описывать по сути число в массиве. Потому будет иметь два поля:
При этом (для красоты кода) с помощью директивы typedef изменяем название своего типа данных:
struct tip меняем на TIP.
В итоге TIP head создает структуру head типа struct tip.
К ее полям можно обратиться “через точку”:
Также создаем новый тип данных для структуры “змея” (SNAKE). Он будет содержать:
Поскольку “змея” состоит лишь из одного числа, то и “голова” и “хвост” инициализируются им же.
Snake.head – обращаемся к структуре head вложенной в структуру Shake.
Snake.head.indx – обращаемся к полю indx вложенной структуры head.
Директива макропроцессора #define заменяет в тексте программы строку LEN_ARR на цифры 1000 перед компиляцией
Подключаем стандартную библиотеку языка Си для работы с булевым типом данных.
Для стандарта C99 булевый тип _Bool, который принимает значения 0 и 1. Данная библиотека позволяет использовать более привычный тип данных bool со значениями false и true.
После инициализации структуры, “змея” занимает только лишь одно число:
… и дальше ей нужно “расти”, чтобы включить в себя 13 множителей:
В программе это реализовано с помощью функции snake_growth(), срабатывающей, если длина “змеи” меньше 13:
Пока “змея” не увеличится до 13 чисел:
Перемещаем “голову” на шаг вперед – на следующее число:
Обновляем значение “головы” новым числом из массива:
Изменяем “тело змеи” – умножаем произведение серии на следующее число:
Увеличиваем длину змеи:
Если “змея” успешно выросла (до 13 чисел), функция возвращает true. Иначе (если “змея” встретила ноль), работа функции прерывается и возвращается false:
Так как функция принимает не структуру, а указатель на структуру:
То к полям структуры внутри функции будем обращаться сначала “через стрелочку” и только затем “через точку“
Как только длина “змеи” достигает 13 чисел:
Ряд чисел начинает сдвигаться вправо – “змея ползет”:
Для чего служит функция snake_crawl(), срабатывающей, если длина “змеи” достигла 13.
Если “змея” успешно “выросла” или “проползла” на одно число, то в поле product сохраняется очередной результат – произведение серии из 13 последовательных цифр. При этом соответствующие функции возвращают true, которое сохраняется во флаг is_answ.
Конструкция:
Если во время “роста” или “ползания” встретится ноль, то функции вернут false и в действие вступит функция snake_jamp(). “Змея перепрыгнет” через ноль и сначала будет заново “расти“, а после – “ползти“. При этом в 1000-значном числе из задания есть не только одиночные нули, но и группы последовательно стоящих нулей. Потому длина “прыжка” будет изменяться в зависимости от их количества.
Вот так, ползком и вприпрыжку “змея” проходит весь массив чисел и находит в итоге ответ на 8 задачу проекта Эйлера – 23514624000. При этом программа работает молниеносно – возвращает ответ за 0.0 секунд.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
