Преобразовал 1000-значное число в строку, затем в массив, а споткнулся на особенностях использования математических операторов в языке и их влиянии на память.
Условия задачи
"Наибольшее произведение четырех последовательных цифр в нижеприведенном 1000-значном числе равно 9 × 9 × 8 × 9 = 5832.
Найдите наибольшее произведение тринадцати последовательных цифр в данном числе."
Преобразовываю 1000-значное число в удобный формат
В языке программирования Си невозможно оперировать столь большими числами как 1000-значное и поэтому неплохо бы представить его в виде массива цифр. Чтобы не набирать цифры вручную, сделаю несколько преобразований.
Преобразовываю число в строку
Для начала преобразую число в строку.
Все просто, объявил строку:
num_str[] = {""};
Скопировал внутрь кавычек набор цифр из задания, расставил кавычки, готово. Программа сама объединит ряд строк в одну.
На всякий случай проверил себя, все ли цифры занесены в строку:
printf("%d",strlen(num_str));
С помощью функции strlen() измерил длину строки (1000).
Преобразую строку в массив цифр
Создал массив для хранения цифр 1000-значного числа:
char num_array[1000];
Воспользовался функцией atoi() для преобразования символов строки в числа.
При этом важно знать, что эта функция служит для преобразования именно строки в число, так что к каждому символу перед преобразованием пришлось добавлять знак окончания строки '\0' и представлять именно в формате строки.
Используемые библиотеки
Для работы функций printf(), strlen() и atoi() программе использовал библиотеки:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
Их работа понятна из кода программы.
Ищу наибольшее произведение тринадцати последовательных цифр
Что может быть проще чем имея массив из чисел, вычислить наибольшее произведение последовательных цифр?
prod = num_array[i] * num_array[i + 1] * num_array[i + 2] * ... * num_array[i + 12];
Берешь число, перемножаешь на последующие, получаешь результат. Берешь следующее, перемножаешь и так в цикле.
Вот только ответ для тринадцати чисел получается неверный (2091059712). Причем для четырех чисел все верно (5832).
Не хватает памяти? Увеличил тип переменных до:
unsigned long long answ = 0; //ответ
unsigned long long prod = 1; //результат перемножения чисел
Ничего не изменилось.
Ранее я уже писал об особенностях арифметических операций в языке Си и разнице между:
<выражение 1> = <выражение1> + 1;
и
<выражение 1> += 1;
Возможно (поправьте меня кто знает) при многократном использовании после "=" операций возврата значения из массива и операций умножения, данные сохраняются на отдельных участках памяти, таким образом ее используется слишком много, память переполняется (!) и сохраняет неверный ответ.
prod = num_array[i] * num_array[i + 1] * num_array[i + 2] * ... * num_array[i + 12];
Решил использовать конструкцию вида
for( int j = 0; j < 13; j++)
prod *= num_array[i + j];
Арифметическая операция "*=" гарантированно меняет значение непосредственно в самой переменной не используя другие участки памяти.
Время работы программы составило 0.4 - 0.5 секунд.
Ответ на задачу:
Точно ли проблемы с памятью
Изменил тип переменных на:
long answ = 0; //ответ
long prod = 1; //результат перемножения чисел
Получил точно такой же неверный ответ(2091059712), как и изначально - таким образом проблема была в переполнении памяти.
Си - удивительный язык, чтобы не было проблем с памятью требуется следить даже за используемыми операторами в арифметических операциях.
P.S. Все мои рассуждения по поводу ошибки оказались неверны, причина проблемы - ниже в комментариях.
P.P.S. Изначальная цель блога - получить "фидбек" в комментариях, чтобы более опытные "кодеры" указывали мне на ошибки, советовали и всячески помогали в саморазвитии.
Также приглашаю всех на мой сайт)
На нем Вы можете посмотреть ответ на задачу Эйлера #8 (когда необходима лишь небольшая подсказка) и последний, самый быстрый вариант решения.
В общем, добро пожаловать на канал))