Проект Эйлера (42 задача). Позволяет поработать с файлами: открываем файл, копируем содержимое в массив, «парсим» текст на отдельные слова.
Узнать больше в телеграм-канале: ProjectEuler++
n-й член последовательности треугольных чисел задается как tn = ½n(n+1). Таким образом, первые десять треугольных чисел:
- 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Преобразовывая каждую букву в число, соответствующее ее порядковому номеру в алфавите, и складывая эти значения, мы получим числовое значение слова. Для примера, числовое значение слова SKY равно 19 + 11 + 25 = 55 = t10. Если числовое значение слова является треугольным числом, то мы назовем это слово треугольным словом.
Используя words.txt (щелкнуть правой кнопкой мыши и выбрать ‘Save Link/Target As…’), 16 КБ текстовый файл, содержащий около двух тысяч, часто используемых английских слов, определите, сколько в нем треугольных слов.
Уже привычно разбил функцию main() на два скриншота.
В задании приведена формула для вычисления треугольного числа по его номеру. Для удобства данную формулу можно преобразовать в квадратное уравнение. Это позволит проверять соответствие кода слова условиям задачи, просто вычисляя его корни.
Однако в таком случае придется вычислять одни и те же треугольные числа снова и снова. Так произойдет, потому что в файле около двух тысяч слов и занимает он 16 килобайт. И в итоге слово в среднем будет содержать восемь букв. Даже если предположить, что оно состоит из одних букв ZZZZZZZZ, то получим максимальный цифровой код 8 * 26 = 208.
Потому, если мы вычислим заранее все треугольные числа до 1000 (возьмем с большим запасом), и сохраним в массив по индексу:
Все две тысячи слов практически гарантированно попадут в этот диапазон и в итоге для проверки кода слова достаточно будет просто обращаться к массиву по индексу.
Второй вопрос, как заполнять этот массив.
Можно по формуле из задания, однако есть способ сократить вычисления. Если выписать ряд треугольных чисел:
… то можно увидеть закономерность – каждое последующее число отличается от предыдущего ровно на его порядковый номер:
Таким образом массив с треугольными числами в итоге легко заполняется за один проход. Причем без всяких формул и лишних вычислений.
После открытия файла, его содержимое заносится в массив структуры text. Подробнее об этом – в описании соответствующей функции ниже.
Из этого массива мы и «парсим» слова. Каждое слово в тексте обрамлено «кавычками», потому они и будут служить сигналом начала или окончания слова, переключая флаг start_word_fl.
Как только слово началось, числовые значения букв складываются между собой.
Чтобы получить порядковый номер буквы в алфавите, воспользуемся самим принципом их хранения в памяти. Символы ‘A’, ‘B’, ‘C’ и прочие хранятся в памяти устройства в виде числовых кодов: ‘A’ = 65, ‘B’ = 66 и так далее.
И работать с ними можно как с числами. Например: ‘A’ + 1 = ‘B’, ‘C’ – ‘A’ = 2 и т.п.
Потому порядковый номер буквы мы сможем получать вычитанием:
По сигналу окончания слова, цифровой код сравнивается с массивом треугольных чисел и, если необходимо, слово учитывается в ответе.
Значение слова обнуляется, подготавливаясь к вычислению следующего кода.
Для измерения времени работы программы подключаем библиотеку time.h:
С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.
(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)
CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000
Поскольку работа с файлами не раз встречается в цикле задач проекта Эйлера, потому постараемся сделать эту функцию максимально универсальной.
Для хранения текста создадим структуру text. Она будет иметь два поля:
Это позволит не привязываться к фиксированной длине массива.
Сначала функция открывает файл на чтение при помощи fopen(). Если, однако, что-то пошло не так (например, неправильно указано название файла или путь к нему), то функция прервется и выведет предупреждение.
Далее с помощью функций fseek() и ftell() определяем длину файла и сохраняем в структуру.
С помощью функции malloc() выделяем в памяти массив нужной длины и указатель на него также сохраняем (text.arr).
Поскольку функция выделяет память, потому обязательно (!!!) следует после окончания работы с ней освобождать (используем free()). Так как память освобождается не внутри самой функции, потому напоминание об использовании malloc() записано прямо в названии:
Перед началом копирования данных из файла, указатель на файловую позицию устанавливаем обратно в начало файла.
Функция fgets() будет копировать данные в буфер до тех пор, пока не дойдет до конца файла и не вернет NULL.
Из буфера в массив информация будет копироваться при помощи fputs().
При корректной работе функция вернет структуру с длиной массива и указателем на него. Т.е. не понадобится в итоге копировать все данные еще раз.
По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.
Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))
Есть вопросы, господа?
© 2023-2024 | eulerproject.ru
