Project Euler (answers)

Проект Эйлера: Ответ и решение 22 задачи (Очки за имена)

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

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

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

Используйте names.txt (щелкнуть правой кнопкой мыши и выбрать ‘Save Link/Target As…’), текстовый файл размером 46 КБ, содержащий более пяти тысяч имен. Начните с сортировки в алфавитном порядке. Затем подсчитайте алфавитные значения каждого имени и умножьте это значение на порядковый номер имени в отсортированном списке для получения количества очков имени.
Например, если список отсортирован по алфавиту, имя COLIN (алфавитное значение которого 3 + 15 + 12 + 9 + 14 = 53) является 938-м в списке. Поэтому, имя COLIN получает 938 × 53 = 49714 очков.
Какова сумма очков имен в файле?

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

Решение задачи

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

Используемые при расчете функции

Функция, открывающая файл и копирующая его содержимое в массив работы функций
Функция, которая отмечает индексы начала слов в массиве
Функция, которая определяет превышение переменной своего предельного значения и выводит предупреждение
Функция, которая сортирует два имени по алфавиту
Функция, которая копирует один массив в другой
Функция, которая реализует сортировку массива слиянием
Функция, которая считает алфавитное значение имени

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

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

Описание применяемых функций будет ниже, здесь лишь опишем общий алгоритм:

Для хранения содержимого файла создадим массив text_arr[] длиной 50000, потому что в условии заранее сказано о весе файла в 46 кБ. Однако, если в итоге понадобится ее изменить, то это будет легко сделать, изменив значение в:

#define LEN_ARR 50000

При помощи функции open_file() открываем файл “euler22text.txt” и копируем его в созданный ранее массив. При этом он будет содержать не только имена, но и все символы, содержащиеся в файле:

[“,M,A,R,Y,”,’\,’,”,P,A,T,R,I,C,I,A,”,..]

Потому и, чтобы легче было сортировать список, создадим еще один массив (смотрите выше):

name_arr[6000]

В нем будем хранить полученные с помощью функции parser_names() индексы первых букв имен в массиве text_arr[]. Т.е. если первая буква слова “MARY” расположена в:

name_arr[1] = ‘M’;

… а “PATRICIA”

name_arr[8] = ‘P’;

… то массив name_arr[] в итоге будет заполнен примерно так:

[1, 8, 19, 27, 46…]

Далее, с помощью функции merge_sort() имена сортируются. Однако при этом в массиве text_arr[], где имена фактически сохранены, ничего не трогается. Перемещаются лишь их индексы в массиве name_arr[]:

[1, 8, 19, 27, 46…] -> [1, 8, 27, 19, 46…]

Изменение порядка индексов, в итоге означает изменение порядка слов:

“MARY”,”PATRICIA”,”LINDA”,”BARBARA” -> “MARY”,”PATRICIA”,”BARBARA”,”LINDA”

В итоге после сортировки остается лишь посчитать с помощью функции get_name_score() искомую сумму очков имен.

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

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

Используемые при расчете функции (проект Эйлера - 22 задача)

Функция, открывающая файл и копирующая его содержимое в массив

Используем здесь стандартные функции языка Си:

fopen() – открывает файл, относительный путь к которому в данном случае “euler22text.txt” на чтение (“r”)
fgets() – служит для считывания строк из файла. Поскольку в данном документе строк нет, как и символа окончания строки (‘\n’), потому функция скопирует в массив text_arr[] полностью все содержимое до символа окончания файла (EOF).
ftell() возвращает текущую файловую позицию потока (ее содержит указатель на файловый поток file). По окончанию считывания файла, указатель на файловую позицию будет находиться в конце файла и потому будет равен длине файла.
fclose() – закрываем файл

Также функция выводит сообщение об ошибке, если невозможно прочитать файл (например, неправильно написан путь к нему). Кроме того, выводится сообщение о количестве скопированной информации. Это также полезно знать, потому что иначе, при недостаточной длине массива будет скопирован не весь файл.

Функция, которая отмечает индексы начала слов в массиве

Подключив <ctype.h> мы получаем возможность использовать стандартный набор функций для анализа символов. Однако понадобится нам лишь одна:

isalpha() – возвращает true, если принимаемый функцией символ является буквой.

Работа parser_name() реализована при помощи данной функции и флага start_name (первоначально false):

функция проходит по всем символам массива text_arr[];
как только встретится первая буква, функция заносит ее индекс в массив name_arr[] и устанавливает флаг start_name в положение true;
последующие буквы пропускаются (т.к. флаг начала слова уже true);
первый же символ, не являющийся буквой, означает конец слова;
в итоге флаг переводится в положение false и поиск начала следующего слова продолжается.

Проверка выхода за пределы массивов text_arr[] и name_arr[] реализована с помощью отдельной функции – input_more_limit().

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

Данная проверка вынесена отдельной функцией, потому что иначе пришлось бы многократно писать одно и тоже в каждой функции. Она выводит предупреждение, в котором пишет название функции в которой она сработала, название и значение проверяемой переменной и параметры, которые она превысила. Также она вернет true, в случае превышения, что позволит в прервать функцию, в которой она используется через return. Или, если выход параметра за пределы в итоге не критичен, как-либо иначе это использовать.

Функция, которая сортирует два имени по алфавиту

Функция использует вышеупомянутую функцию isalpha(). Она проходит по двум именам и сравнивает буквы между собой:

если буквы одинаковые, то указатели идут дальше по именам до тех пор пока не встретят разные или не кончится одно из имен (символ будет не буквой);
если буквы разные, то определяет, необходимо ли менять слова местами (смотрите задание);

[A,N,N,A] [B,E,N] -> [A,N,N,A] [B,E,N]

[A,N,N,A] [B,E,N] -> [B,E,N][A,N,N,A]
при этом, конечно, меняются не слова в массиве text_arr[], а лишь их индексы в name_arr[];
в случае если слова содержат одинаковые буквы, но разную длину, то первым ставится более короткое слово;
[ANNA] [ANN] -> [ANN] [ANNA]

В итоге функция возвращает true – нет необходимости менять слова местами, false – если необходимо.

Функция, которая копирует один массив в другой

Данная функция служит, чтобы скопировать в один массив (receive_arr[]) часть другого (sourse_arr[]). Поскольку копируется лишь часть массива (lenght элементов начиная индекса start_indx), потому контролируется невыход за пределы только второго массива. Количество в итоге скопированных в массив элементов возвращается функцией.

Функция, которая реализует сортировку массива слиянием

Первый проход функции по массиву

Данная функция реализует сортировку массива слиянием и работает следующим образом

выделяет из массива name_arr[] (например {1,8,17,26,…}) два подмассива;
в массиве text_arr[] эти индексы указывают на слова “MARY”,”PATRICIA”,”LINDA”,”BARBARA”;
на первом этапе подмассивы будут длиной в один элемент, потому в данном случае это: первый – {1} и второй – {8};
далее значения из первого подмассива копируются во временный массив temp_arr[] ({1});
с помощью функции compare_names() сравниваются имена с индексами из массива temp_arr[] ({1}) и второго подмассива {8};
однако напомню, что фактически между собой будут сравниваться слова из массива text_arr[] начала которых записаны по этим индексам (MARY и PATRICIA);
массив name_arr[] в итоге заполняется из дополнительного массива и второго подмассива, параллельно сортируясь;
после того как в массив занесены {1,8} все повторяется, но уже со следующими двумя словами (их индексы к примеру {17,26});
пройдя до последнего слова в массиве (с индексом name_arr[lenght – 1] равен количеству слов в массиве), функция их отсортировала попарно.

Второй и последующие проходы

цикл далее повторяется, однако размеры подмассивов теперь увеличиваются вдвое {1,8} и {26,17};
теперь сравниваются оба массива слева направо, сначала {1} и {26}, т.е. слова “MARY” и “BARBARA”;
заносится {26} (“BARBARA”);
сравниваются {1} и {17} (“MARY” и“LINDA”);
заносится {17} (“LINDA”);
в массив name_arr[] занесены два элемента {26,17}, однако второй подмассив уже кончился и остался лишь временный{1,8};
данные из него просто заносятся в массив после них {26,17,1,8};
таким образом мы получили уже четыре отсортированных имени “BARBARA”,”LINDA”,”MARY”,”PATRICIA”;
в итоге к концу прохода все имена будут отсортированы уже по четыре;
удваивая после каждого прохода длину массивов, за несколько таких итераций будет отсортирован весь массив.

Функция, которая считает алфавитное значение имени

Функция использует тот факт, что каждому символы хранятся в компьютере в виде чисел – кодов ASCII. Так буква ‘A’ хранится в виде числа 65, ‘B’ – 66. Потому порядковый номер в алфавите можно легко вычислить вычитая из кода числа 64.

Также здесь используется функция isalpha(), с помощью которой считаются коды только букв. Первый же символ не являющийся буквой указывает на окончание слова.

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

В итоге ответ на 22 задачу проекта Эйлера составил 871198282, программа считает ответ за 8-12 миллисекунд.

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

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

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

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

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