автордың кітабын онлайн тегін оқу Алгоритмы на практике
Даниэль Зингаро

Үзіндіні оқу

Кітап туралы Пікірлер3 Дәйексөздер84 Қазір оқып жатыр6K Сөрелерде Тегін фрагмент

Даниэль Зингаро

Алгоритмы на практике

2023

Переводчик Д. Брайт

Даниэль Зингаро

Алгоритмы на практике. — СПб.: Питер, 2023.

ISBN 978-5-4461-1853-3

Предисловие

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

Программирование можно сравнить с теннисом. Начинающему программисту сложно доходчиво «объяснить» компьютеру, как нужно реализовать то или иное решение задачи. Но стоит превзойти уровень белого пояса, и работа с задачами начинает приносить удовольствие. Прежде всего, какой подход к решению выбрать? Хотя универсального средства эффективного решения всех задач не существует, есть надежные продвинутые инструменты и стратегии: хеш-таблицы, деревья поиска, рекурсия, мемоизация, динамическое программирование, поиск по графу и т. д. А опытному глазу многие задачи и алгоритмы сами указывают, какие инструменты подходят для них лучше всего. Ваш алгоритм выполняет повторяющийся поиск или минимальные вычисления? Ускорьте его с помощью хеш-таблицы или min-кучи соответственно. Общее решение основной задачи можно выстроить из вторичных решений ее подзадач? Используйте рекурсию! Эти подзадачи пересекаются? Ускорьте алгоритм с помощью мемоизации!

Будь то теннис или программирование, не получится перейти на более высокий уровень без двух вещей: практики и хорошего наставника. В случае программирования оба условия выполнят книга «Алгоритмы на практике» и ее автор Даниэль Зингаро. Он познакомит вас со всеми упомянутыми концепциями, но при этом не ограничится простым их перечнем. Под руководством Зингаро вы на примерах практических задач научитесь грамотному применению в работе правильных алгоритмических инструментов. Все это вы освоите с помощью книги, написанной понятным языком и с юмором. Удачи вам в решении задач!

Тим Рафгарден, Нью-Йорк, NY, май 2020

Благодарности

Работа с ребятами из No Stratch Press была абсолютной идиллией. Они чрезвычайно сосредоточены на издании книг, помогающих читателям учиться. Здесь я нашел единомышленников! Лиз Чедвик (Liz Chadwick) поддержала мою книгу с самого начала (и не поддержала другую, за что я ей признателен). Было удовольствием работать с Алексой Фрид (Alex Freed), которая редактировала рукопись. Она терпелива, добра и не просто исправляла ошибки, а стремилась помочь мне улучшить текст. Я благодарю всех, кто участвовал в процессе создания книги, включая литературного редактора Дэвида Кузенса (David Couzens), выпускающего редактора Кэсси Андрэдис (Kassie Andreadis), креативного директора Дерека Йи (Derek Yee) и дизайнера обложки Роба Гейла (Rob Gale).

Я выражаю признательность Университету Торонто за поддержку моего труда. Спасибо Ларри Чжану (Larry Zhang), научному редактору, за внимательную вычитку рукописи. В течение нескольких лет я преподавал совместно с ним, и именно наше сотрудничество помогло мне выработать правильный образ мышления касательно алгоритмов и того, как обучать их использованию.

Благодарю Тима Рафгардена (Tim Roughgarden) за предисловие к моей книге. Книги и видео Тима представляют собой образцы ясности и наглядности, к которым нам нужно стремиться, рассказывая людям об алгоритмах.

Благодарю моих коллег Яна Варенхольда (Jan Vahrenhold), Махику Путане (Mahika Phutane) и Нааз Сибия (Naaz Sibia) за их рецензии на черновой вариант книги.

Спасибо всем авторам использованных в книге задач, а также участникам соревнований по программированию. Выражаю признательность администраторам ресурса DMOJ за их поддержку моей работы. Отдельная благодарность — Тюдору Бриндусу (Tudor Brindus) и Раду Погонариу (Radu Pogonariu) за их помощь в выборе и доработке задач.

Спасибо моим родителям за то, что взяли на себя все, буквально все, и просили меня об одном — учиться.

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

В завершение я хочу выразить признательность всем вам за то, что читаете эту книгу и стремитесь к знаниям.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете подробную информацию о наших книгах.

Введение

Я предполагаю, что вы знакомы с такими языками, как Cи, C++, Java или Python… и разбираетесь в теме. Тяжело объяснять людям, незнакомым с программированием, почему написание кода для решения задач является настолько захватывающим.

Я также надеюсь, что вы готовы поднять свои навыки программирования на новый уровень. Для меня будет честью помочь вам в этом.

Я мог бы начать с разъяснения всяких изощренных техник, рассказывая о том, какие они полезные, и сравнивая их с другими изощренными техниками. Но я не буду этого делать. Такие знания очень недолго хранятся в памяти, ожидая возможности применения на практике (которая порой так и не появляется).

Вместо этого я на протяжении всей книги буду ставить конкретные трудные задачи. Надеюсь, что вы не сможете справиться с ними сразу, используя знакомые вам подходы. Вы — программист. Вам нужно решать задачи. Пришло время освоить хитрые техники. Книга построена на постановке сложных задач с их последующим решением, при этом вы будете пополнять имеющиеся у вас знания.

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

Мой подход предполагает использование задач, которые вы ранее вряд ли встречали. Каждый год тысячи людей участвуют в соревнованиях по программированию, и для этих соревнований постоянно требуются новые задачи, чтобы оценивать реальные навыки участников, а не способность быстрее всех переделывать старое на новый лад или гуглить решение. Эти задачи удивительны, они базируются на классических подходах, но вносят в них изменения и интересный контекст, подталкивая людей к поиску новых решений. В таких задачах заключается практически безграничный объем знаний по программированию и вычислениям.

Начнем с основ. Структура данных — это способ организации данных для быстрого выполнения нужных операций. Алгоритм — это последовательность шагов при решении задачи. Иногда можно создать быстрый алгоритм без применения сложных структур данных. В других же случаях правильно подобранная структура может существенно ускорить решение. Моя задача — не сделать из вас участника соревнований по программированию, хотя это было бы хорошим бонусом, а научить работать со структурами данных и алгоритмами на примерах интересно поданных задач спортивного программирования. Пишите мне об успехах в своем обучении. Пишите также, если материалы этой книги заставят вас улыбнуться.

Онлайн-ресурсы

Примеры листингов, приведенные в книге, вы можете скачать с сайта издательства «Питер» по ссылке: https://www.piter.com/product/algoritmy-na-praktike#tab-7

Для кого эта книга

Книга предназначена для программистов, которые хотят научиться решать трудные задачи. Вы изучите множество структур данных и алгоритмов, узнаете об их преимуществах, видах задач, где эти алгоритмы и структуры применимы, и способах решения.

Весь код в книге написан на языке программирования Cи. Но это не учебник по Cи. Если у вас уже есть опыт работы с Си или C++, то смело окунайтесь в материал. Если же вы знакомы только с такими языками, как Java или Python, то я думаю, что большую часть необходимого вы уясните по ходу чтения. Но все же желательно разобрать некоторые концепции Cи заранее или при первой необходимости. В частности, я буду использовать указатели и динамическое выделение памяти. Поэтому, независимо от имеющегося опыта, вам может потребоваться освежить эти темы в памяти.

Лучшая, на мой взгляд, книга по работе с Cи — это второе издание C Programming: A Modern Approach К.Н. Кинга (K. N. King). Даже если вы хорошо знакомы с Cи, все равно рекомендую ее прочесть. Она оказывается отличным помощником, когда особенности этого языка вызывают сложности в понимании кода.

Язык программирования

Итак, я выбрал для этой книги именно Cи, а не один из высокоуровневых языков вроде C++, Java или Python. Далее я вкратце опишу причину такого выбора, а также поясню пару других связанных с Си вещей.

Почему Cи?

Основная причина выбора именно языка Си состоит в том, что я хотел рассказать вам о структурах данных и алгоритмах, начиная с азов. Когда нам понадобится хеш-таблица, мы будем создавать ее сами, не полагаясь на словари, хеш-карты или аналогичные структуры данных других языков. Когда нам неизвестна максимальная длина строки, мы создаем расширяемый массив, поскольку Си не станет выделять память за нас. Я хочу, чтобы вы полностью контролировали происходящее и за кадром ничего не оставалось. В этом-то мне и поможет Cи.

Решение задач по программированию на Cи служит хорошей основой в случае, если дальше вы захотите работать с C++. Если вы всерьез увлечетесь спортивным программированием, то стоит отметить, что C++ является самым популярным языком среди участников соревнований. Причина этого — его богатая стандартная библиотека и возможности генерировать код, ориентированный на высокую производительность.

Ключевое слово Static

В Си регулярные локальные переменные хранятся в так называемом стеке вызовов. При каждом вызове функции часть памяти стека задействуется для сохранения локальных переменных. Далее, когда функция делает возврат, эта память освобождается для последующего использования для других локальных переменных. Однако стек вызовов мал и не подходит для крупных массивов, которые будут встречаться в книге. Поэтому мы будем использовать ключевое слово static. Для локальной переменной оно изменяет продолжительность хранения с динамической на статическую, в результате чего переменная сохраняет свое значение между вызовами функций. Побочным эффектом является то, что такие переменные не сохраняются в памяти вместе с регулярными локальными переменными, иначе при завершении функции их значения утрачивались бы. Они помещаются в отдельную область памяти, где им не приходится бороться за место под солнцем с другим содержимым стека вызовов.

При использовании ключевого слова static нужно иметь в виду, что такие переменные инициализируются всего один раз! В листинге 1 приводится краткий пример.

Листинг 1. Локальная переменная с ключевым словом static

int f(void) {

static int x = 5; ❶

printf("%d\n", x);

x++;

}

int main(void) {

f();

return 0;

}

Я использовал static для локальной переменной x ❶. Без него все три раза выводом была бы 5. Тем не менее благодаря static мы получаем:

Добавление файлов

С целью экономии места я не добавляю в листинги строки #include, которые необходимы для запуска программ Cи. Все будет в порядке, если вы будете добавлять самостоятельно следующий код:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

Освобождение памяти

В отличие от Java или Python, Си требует ручной настройки выделяемой памяти. Для выделения памяти служит функция malloc, а для освобождения — функция free.

Однако я не буду освобождать память по двум причинам. Во-первых, добавление соответствующих функций будет отвлекать от основной обучающей задачи кода. Во-вторых, эти программы занимают место в памяти недолго: ваш код будет выполняться в нескольких тестовых примерах, и на этом все. Операционная система возвращает всю неосвобожденную память при закрытии программы, так что беспокоиться не о чем, даже если вы будете выполнять код по нескольку раз. Конечно же, невыполнение освобождения памяти на практике является безответственным подходом: никто не будет рад программе, которая чем дольше выполняется, тем больше потребляет памяти. Если вы хотите попрактиковаться в освобождении памяти, то можете сами добавлять в приводимые на страницах книги программы вызовы функции free.

Темы

Структуры данных и алгоритмы — слишком обширная область для полного описания в одной книге. Поэтому при отборе тем я опирался на три критерия.

Прежде всего, я выбирал темы с широкой областью применения, чтобы каждую из них можно было использовать при решении не только задач, подобных тем, что приведены в книге, но и многих других. В каждой главе рассматривается не менее двух задач. Первая обычно служит для того, чтобы представить структуру данных или алгоритм вместе с одним из классических случаев применения. Последующие задачи представляют дополнительные возможности рассматриваемой структуры данных или алгоритма. Например, в главе 5 изучается алгоритм Дейкстры. Если вы поищете информацию о нем в Google, то узнаете, что он используется для поиска кратчайших путей. И действительно, в первой задаче главы данный алгоритм применяется именно для этой цели. Однако во второй задаче мы подстраиваем его для поиска не одного, а нескольких кратчайших путей. Надеюсь, что по мере знакомства с каждой главой вы будете все больше узнавать о возможностях, ограничениях и тонкостях каждой техники решения.

Второй критерий — это простота реализации, чтобы не перегружать общий поток повествования. Я хотел, чтобы решение любой задачи укладывалось максимум в 150 строк кода, включая считывание входных данных, само решение и вывод. Поэтому структуры данных и алгоритмы, чья реализация занимает 200 или 300 строк, из практических соображений не рассматривались.

Наконец, я выбирал темы, доказательства корректности которых на мой взгляд являются убедительными и интуитивно понятными. Моя цель — научить вас конкретным структурам данных и алгоритмам, потому что вы наверняка читаете эту книгу, чтобы освоить эффективные подходы к решению задач. При этом я также надеюсь, что вам будет интересно узнать, почему та или иная техника работает. Поэтому я тайно преследовал еще одну цель: убедить вас, что рассматриваемые структуры данных или алгоритмы являются корректными. Формальных доказательств или чего-то подобного здесь не будет. Тем не менее если мой секретный замысел сработает, то наряду с изучением самих структур данных и алгоритмов вы также убедитесь в их корректности. Не стоит ограничиваться чтением кода и восхищаться тем, как он всякий раз волшебным образом срабатывает. Магии здесь нет, и все принципы, заставляющие код работать, находятся в досягаемой для вашего понимания области.

Если у вас возникнет желание выйти за рамки материала книги, то я рекомендую заглянуть в приложение Б, где я добавил кое-какую дополнительную информацию к главам 1, 3, 4, 7 и 8.

Многим читателям будет полезно по ходу чтения книги заниматься дополнительной практикой и изучать сторонние материалы. В разделах «Примечания» в конце каждой главы приводятся ссылки на дополнительные ресурсы. Многие из них содержат дополнительные примеры кода и задачи. Помимо этого есть онлайн-ресурсы, которые содержат структурированный список задач и стратегий по их решению. Из всех известных мне ресурсов наиболее обширным в этом отношении является портал Methods to Solve братьев Стивена и Феликса Халимов: https://cpbook.net/methodstosolve.

Сайты с задачами

Каждая выбранная мной задача доступна на сайтах соревнований по программированию. Таких сайтов — множество, и на каждом из них содержатся сотни разных задач. Я старался, чтобы общее число источников было небольшим, но при этом достаточным для гибкого выбора наиболее подходящих задач. Каждый сайт потребует регистрации, и я советую сделать это сразу, чтобы потом не пришлось отвлекаться от решения предложенных в книге задач.

Вот список ресурсов, которые будут использоваться.

Название платформы	Адрес
Codeforces	codeforces.com
DMOJ	dmoj.ca
Kattis	open.kattis.com
POJ	poj.org
SPOJ	spoj.com
UVa	uva.onlinejudge.org

Описание каждой задачи начинается с указания ресурса, где ее можно найти, и номера/кода задачи.

Одни задачи написаны участниками сообществ, другие взяты из программ известных соревнований. Вот некоторые платформы, откуда были позаимствованы использованные в книге задания:

• Международная олимпиада по информатике (IOI) — престижное соревнование для учащихся старших классов школ. Каждую страну представляют по четыре человека, выступающих в индивидуальном зачете. Программа конкурса рассчитана на два дня, в течение которых участники решают множество задач по программированию.

• Канадский конкурс по программированию (CCC) и канадская олимпиада по программированию (CCO) — ежегодные соревнования для учащихся старших классов школ, организуемые Университетом Ватерлоо. CCC проходит в отдельных школах, после чего победители принимают участие в CCO в Университете Ватерлоо. Победители CCO представляют Канаду на IOI. Когда я был школьником, то неоднократно участвовал в CCC, но ни разу не попал на CCO — даже близко к этому не подошел.

• DWITE — онлайн-соревнование по программированию, проводившееся для подготовки студентов к участию в ежегодных конкурсах. К сожалению, DWITE больше не функционирует, но старые задачи — а они весьма хороши! — по-прежнему доступны.

• ACM East Central North America Regional Programming Contest — ежегодный конкурс для студентов университетов восточной части центрального региона Северной Америки, который проводится ассоциацией ACM. Победители приглашаются на финал международного студенческого соревнования по программированию (ACM International Collegiate Programming Contest, ICPC). В отличие от других упомянутых здесь конкурсов, на которых участники выступают в индивидуальном зачете, это соревнование является командным.

• SAPO — Южно-Африканская олимпиада по программированию. Ежегодное соревнование, которое состоит из трех раундов с растущей сложностью. По результатам конкурса отбираются участники, представляющие ЮАР на IOI.

• COCI — Хорватское открытое соревнование по информатике. Онлайн-конкурс, который проводится несколько раз в год. По его результатам формируется хорватская команда для участия в IOI.

• USACO — Олимпиада по программированию в США. Онлайн-соревнование, организуемое несколько раз в год. Самая сложная его часть — открытый чемпионат. В каждом соревновании участникам предлагаются четыре уровня сложности задач: бронзовый, серебряный, золотой и платиновый. По результатам отбирается команда для участия в IOI.

Полный список источников задач приведен в приложении Б. Когда вы отправляете код задачи, ресурс компилирует вашу программу и проверяет ее на тестовых примерах. Если она проходит все эти тесты за установленное время, то код принимается как верный. Принятые решения обозначают как AC. Если же ваша программа не проходит один или более тестов, то она не принимается. Такие программы обозначаются как WA (Wrong Answer). Третий вариант результата проверки относится к слишком медленным программам, которые обозначаются TLE (Time-Limit Exceeded). Обратите внимание, что TLE не означает корректность кода — если время истекает, то оставшиеся тесты не проводятся и возможны необнаруженные ошибки, ведущие к оценке WA.

На момент издания книги каждая из представленных в ней окончательных версий решений успешно проходила все тесты за установленное время. В рамках допустимого я стремился сделать код читаемым и отдавал предпочтение ясности, а не скорости, поскольку эта книга посвящена изучению структур данных и алгоритмов, а не выдавливанию максимальной производительности из программы, которая и без того справится со своей задачей.

Структура описания задачи

Прежде чем решать задачу, нужно четко определиться, что именно от нас требуется. Необходимо точно понимать саму задачу, а также предполагаемый способ считывания входных и генерации выходных данных. Поэтому каждая задача начинается с описания трех ее составляющих:

• Условие. Здесь я представляю контекст задачи и ее цель. Очень важно читать условие внимательно, чтобы в точности понимать, какую именно задачу вы решаете. Иногда невнимательное прочтение или неверная интерпретация даже, казалось бы, незначительных нюансов может вести к ошибочным решениям. Например, в одной из задач от нас потребуется купить «не менее» заданного количества яблок. Если же вместо этого вы будете покупать «ровно столько» яблок, то программа провалит некоторые из тестов.

• Входные данные. Автор задачи предоставляет тестовые примеры, которые необходимо выполнить, чтобы решение было зачтено правильным. Мы должны считывать из входных данных каждый тестовый пример, чтобы иметь возможность его обработать. Откуда нам знать, сколько там примеров? Какие данные находятся на каждой строке каждого примера? Если в них есть числа, то каков их диапазон? Если там строки, то каков предел их длины? Всю эту информацию я предоставляю в даннном разделе.

• Выходные данные. Может очень расстроить ситуация, в которой у нас будет программа, производящая верный ответ, но при этом проваливающая тестовые кейсы из-за вывода результата в неверном формате. Часть описания задачи, относящаяся к выводу, указывает, как именно он должен быть представлен. Например, в этом разделе будет описываться, сколько строк вывода должно получаться для каждого кейса, что размещать в каждой строке, нужно ли оставлять пустые строки до или после тестовых случаев и т.д. Кроме того, я устанавливаю для каждой задачи ограничение по времени: если программа не делает вывод для всех тестовых кейсов за этот установленный промежуток, она не проходит.

Я менял формулировки условий задач, не меняя их сути.

Для большинства задач книги мы будем считывать входные данные из стандартного ввода (stdin) и записывать результат в стандартный вывод (stdout) (только в двух задачах в главе 6 stdin и stdout не потребуются). Это означает, что нужно будет использовать такие функции Cи, как scanf, getchar, printf и т.д. без явного открытия и закрытия файлов.

Задача. Очереди за продуктами

Разберем пример описания задачи. Я буду давать в скобках комментарии, указывая на наиболее важные моменты. Когда условие задачи станет понятным, мы ее решим. В отличие от других задач книги, это можно будет сделать с помощью конструкций и понятий, которые, надеюсь, вам уже знакомы. Если вы справитесь с этой задачей сами или пробежитесь по моему решению без особых затруднений, значит, вы вполне готовы к грядущим испытаниям. Если же у вас возникнут серьезные трудности, то могу порекомендовать для начала еще раз ознакомиться с основами программирования и/или порешать базовые задачки.

Начнем мы с задачи с платформы DMOJ под номером lkp18c2p1 (найдите ее на сайте, чтобы после получения решения сразу отправить результат на проверку).

Условие

За продуктами выстроилось n очередей из известного количества людей. Далее по одному человеку будет прибывать еще m людей, занимая место в самой короткой очереди (то есть той, где меньше всего людей). Нужно определить количество людей в каждой очереди, к которой присоединяется каждый из m людей (внимательно обдумайте условие. Дальше идет пример, поэтому, если что-то остается неясным, попробуйте сопоставить его с описанием условия).

Предположим, что всего есть три очереди. В очереди 1 стоит три человека, в очереди 2 стоят двое, в очереди 3 — пятеро. Далее приходят еще четыре человека (прежде чем читать далее, попробуйте понять, что на этом этапе будет происходить). Первый человек встает в очередь с двумя людьми, то есть очередь 2. Теперь в ней стоят трое. Второй прибывший присоединяется к очереди из трех людей, то есть к 1-й или 2-й, пусть будет 1-я. Теперь в очереди 1 стоят четыре человека. Третий пришедший присоединяется к очереди 2, где стоят трое, и ее размер увеличивается до 4. Последний подошедший встает в очередь с четырьмя людьми, выбирая между очередями 1 и 2. Пусть он выберет 1-ю, и в ней теперь будет пять человек.

Входные данные

Входные данные содержат один тестовый пример. В первой строке находятся два положительных целых числа: n — количество очередей; m — количество людей. Их максимальное значение — 100. Вторая строка содержит n положительных целых чисел, описывающих количество людей в каждой очереди до прибытия новых. Каждое из этих чисел не больше 100.

Вот пример входных данных:

3 4

3 2 5

(Обратите внимание, что здесь представлен всего один тестовый пример, следовательно, нужно считывать именно две строки входных данных.)

Выходные данные

Для каждого из m подошедших людей нужно вывести строку, содержащую количество людей в очереди, к которой они присоединяются.

Рабочий вывод для предложенного примера будет таким:

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

Решение

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

Ключевые данные для решения — это количество людей в каждой очереди. Для их сохранения вполне подойдет массив, где каждая очередь будет занимать свой индекс. Этот массив я назову lines.

Каждый из прибывающих людей присоединяется к самой короткой очереди, поэтому нам потребуется вспомогательная функция, которая будет определять выбор очереди. Эта функция приведена в листинге 2.

Листинг 2. Индекс самой короткой очереди

int shortest_line_index(int lines[], int n) {

int j;

int shortest = 0;

for (j = 1; j < n; j++)

if (lines[j] < lines[shortest])

shortest = j;

return shortest;

}

Теперь, имея массив lines, а также значения n и m, можно решить тестовый пример. Соответствующий код дан в листинге 3.

Листинг 3. Решение задачи

void solve(int lines[], int n, int m) {

int i, shortest;

for (i = 0; i < m; i++) {

shortest = shortest_line_index(lines, n);

printf("%d\n", lines[shortest]);

lines[shortest]++; ❶

}

В каждой итерации внешнего цикла for мы вызываем вспомогательную функцию для извлечения индекса самой короткой очереди. Затем мы выводим длину этой очереди. Подошедший человек присоединяется именно к ней, поэтому ее размер надо увеличить на один ❶.

Далее осталось только считать входные данные и вызвать solve. Это выполняется в листинге 4.

Листинг 4. Функция main

#define MAX_LINES 100

int main(void) {

int lines[MAX_LINES];

int n, m, i;

scanf("%d%d", &n, &m);

for (i = 0; i < n; i++)

scanf("%d", &lines[i]);

solve(lines, n, m);

return 0;

}

Объединение функций shortest_line_index, solve и main с добавлением в начале обязательных строк #include дает законченное решение, которое можно отправлять на проверку. При этом нужно правильно указывать язык программирования: для наших программ следует выбирать GCC, C99, C11 или иное обозначение компилятора для Cи.

Если вы хотите протестировать код локально, прежде чем отправлять его на проверку, то это вполне можно сделать. Поскольку наши программы производят чтение из stdin, можно запустить программу и ввести тестовые данные вручную. Это приемлемо для небольших примеров, но будет утомительным, если процесс придется повторять либо требуется ввести большой объем данных. Более разумным вариантом будет сохранить входные данные в файле, а затем выполнить из командной строки перенаправление ввода, чтобы программа производила чтение из этого файла, а не с клавиатуры. Например, если сохранить тестовый пример для текущей задачи в food.txt, а скомпилированная программа будет называться food, то попробуйте следующее:

$ food < food.txt

Такой способ упрощает изменение тестового примера: просто отредактируйте содержимое food.txt, а затем запустите программу снова с перенаправлением ввода.

Поздравляю! Вы решили нашу первую задачу. Более того, теперь вы освоили структуру представления, которой будут соответствовать все последующие задачи книги.

Примечания

Задача «Очереди за продуктами» входила в программу конкурса LKP (Contest 2) на платформе DMOJ.

1. Хеш-таблицы

В этой главе мы решим две задачи, опираясь на средства эффективного поиска. В первой из них нужно будет проверить идентичность снежинок. Во второй мы будем определять, какие из слов являются сложносоставными. Вы увидите, что некоторые корректные подходы к решению оказываются недостаточно быстрыми. Для существенного повышения скорости вычислений мы используем структуру данных под названием «хеш-таблица», которую также изучим в деталях.

В завершение главы рассмотрим третью задачу: определим, сколькими способами можно удалить букву из слова, чтобы получить другое слово. В ней будут показаны риски необдуманного использования рассмотренной структуры данных, ведь при освоении чего-то нового всегда хочется сразу начать применять это везде!

Задача 1. Уникальные снежинки

Рассмотрим задачу под номером cco07p2 с сайта DMOJ.

Условие

Дана коллекция снежинок, нужно определить, содержит ли она идентичные снежинки.

Каждая снежинка описывается шестью целыми числами, каждое из которых характеризует длину одного ее луча. Вот пример:

3, 9, 15, 2, 1, 10

При этом значения длин лучей могут повторяться, скажем, вот так:

8, 4, 8, 9, 2, 8

Но как понять, являются ли две снежинки идентичными? Рассмотрим несколько примеров.

Сначала сравним две снежинки:

1, 2, 3, 4, 5, 6

Очевидно, что они идентичны, потому что числа одной совпадают с числами другой, находящимися в соответствующих позициях.

А вот второй пример:

1, 2, 3, 4, 5, 6

4, 5, 6, 1, 2, 3

Эти снежинки тоже идентичны, так как если начать с 1 во второй снежинке и продвигаться вправо, то сперва идут значения 1, 2, 3, после чего происходит возврат в начало и последовательность продолжается значениями 4, 5, 6. Оба этих сегмента вместе формируют снежинку, идентичную первой.

Каждую снежинку можно представить как круг. Тогда два предложенных здесь образца будут идентичными, потому что при правильном выборе начальной точки сопоставления во второй снежинке и следовании по часовой стрелке мы получаем первую снежинку.

Попробуем пример посложнее:

1, 2, 3, 4, 5, 6

3, 2, 1, 6, 5, 4

На основе только что рассмотренных вариантов можно сделать вывод, что эти снежинки не идентичны. Если начать с 1 во второй снежинке и продвигаться по кругу вправо до возвращения к точке отсчета, то мы получим 1, 6, 5, 4, 3, 2. Эта форма далека от 1, 2, 3, 4, 5, 6 первой снежинки.

Тем не менее если начать с 1 во второй снежинке и перемещаться не вправо, а влево, тогда мы получим 1, 2, 3, 4, 5, 6. Перемещение влево от 1 дает 1, 2, 3, после чего происходит переход к правому краю и дальнейшее продвижение по значениям 4, 5, 6.

Таким образом, две снежинки считаются идентичными и в случае, если числа совпадают при продвижении влево от точки отсчета.

Обобщая сказанное, можно заключить, что две снежинки идентичны, если они описываются одинаковыми последовательностями чисел либо если сходство обнаруживается при перемещении по этим последовательностям влево или вправо.

Входные данные

Первая строка входных данных является целым числом n, описывающим количество сравниваемых снежинок. Значение n будет находиться в диапазоне от 1 до 100 000. Каждая из следующих n строк характеризует одну снежинку: содержит шесть целых чисел, каждое из которых может иметь значение в диапазоне от 0 до 10 000 000.

Выходные данные

На выходе должна быть получена одна текстовая строка:

• Если идентичных снежинок не обнаружено, следует вывести:

No two snowflakes are alike (нет одинаковых снежинок).

• Если есть хотя бы две идентичные снежинки, следует вывести:

Twin snowflakes found (найдены одинаковые снежинки).

Время выполнения вычислений ограничено двумя секундами.

Упрощаем задачу

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

Предположим, что мы работаем не со снежинками, состоящими из множества целых чисел, а с отдельными целыми числами. У нас есть коллекция, и нужно узнать, содержит ли она одинаковые числа. Проверить одинаковость двух целых чисел в Си можно с помощью оператора ==. Мы будем тестировать все варианты пар чисел, и если найдем одинаковые числа хотя бы в одной паре, то остановимся и выведем:

Twin integers found (найдены одинаковые числа).

Если мы не обнаружим одинаковых чисел, то вывод будет таким:

No two integers are alike (нет одинаковых чисел).

Теперь создадим функцию identify_identical с двумя вложенными циклами для сравнения пар целых чисел, как показано в листинге 1.1.

Листинг 1.1. Поиск одинаковых целых чисел

void identify_identical(int values[], int n) {

int i, j;

for (i = 0; i < n; i++) {

for (j = i+1; j < n; j++) {❶

if (values[i] == values[j]) {

printf("Twin integers found.\n");

return;

}

printf("No two integers are alike.\n");

}

Мы передаем числа в функцию через массив values. Также мы передаем n, то есть количество чисел в массиве.

Обратите внимание, что мы начинаем внутренний цикл с i + 1, а не с 0 ❶. Если начать с 0, то j будет равняться i и мы будем сравнивать элемент с самим собой, получая ложноположительный результат.

Протестируем identify_identical с помощью небольшой функции main:

int main(void) {

int a[5] = {1, 2, 3, 1, 5};

identify_identical(a, 5);

return 0;

}

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

Решение основной задачи

Теперь попробуем изменить функцию identify_identical для решения задачи со снежинками. В код нужно будет внести два изменения.

1. Нужно работать не с одним, а с шестью целыми числами сразу. Для сравнения хорошо подойдет двумерный массив, в котором каждая строка будет снежинкой с шестью столбцами (по одному для каждого элемента).

2. Как мы выяснили, снежинки могут оказаться одинаковыми в трех случаях. К сожалению, это подразумевает, что для их сравнения уже не получится использовать ==. Необходимо учесть возможности «перемещения вправо» и «перемещения влево» (не говоря уже о том, что == в Си для сравнения массивов не используется). Так что основным изменением имеющегося алгоритма станет правильное сопоставление снежинок.

Для начала напишем две вспомогательные функции: одну для проверки «перемещения вправо» и вторую для проверки «перемещения влево». Каждая из них будет получать параметры двух снежинок и стартовую точку обхода второй снежинки.

Проверка вправо

Заголовок функции для identical_right:

int identical_right(int snow1[], int snow2[], int start)

Чтобы определить, совпадают ли снежинки при «передвижении вправо», можно просканировать snow1 с индекса 0 и snow2 с индекса start. В случае обнаружения разногласия между сопоставляемыми элементами будет возвращаться 0, указывая, что снежинки не идентичны. Если же все сопоставляемые элементы совпадут, возвращаться будет 1. Таким образом, 0 означает false, а 1 — true.

В листинге 1.2 приводится первый вариант кода для этой функции.

Листинг 1.2. Определение идентичности снежинок перемещением вправо (с ошибкой!)

int identical_right(int snow1[], int snow2[],

int start) { //ошибка!

int offset;

for (offset =0; offset < 6; offset++) {

if (snow1[offset] != snow2[start + offset]) ❶

return 0;

}

return 1;

}

К сожалению, этот код не работает нужным образом. Проблема в выражении start + offset ❶. Если start = 4 и offset = 3, тогда start + offset = 7 и мы обращаемся к элементу snow2[7].

Этот код не учитывает, что нам нужно перейти к левой стороне snow2. Если код может использовать ведущий к ошибке индекс 6 или выше, то индекс нужно сбрасывать вычитанием шестерки. Это позволит продолжить с индекса 0 вместо индекса 6, индекса 1 вместо 7 и т.д. Попробуем исправить ошибку в листинге 1.3.

Листинг 1.3. Определение идентичности снежинок перемещением вправо

int identical_right(int snow1[], int snow2[],

int start) {

int offset, snow2_index;

for (offset =0; offset < 6; offset++) {

snow2_index = start + offset;

if (snow2_index >= 6)

snow2_index = snow2_index - 6;

if (snow1[offset] != snow2[snow2_index])

return 0;

}

return 1;

}

Такой вариант работает, но его можно улучшить. Одно из возможных изменений — это использование %, оператора вычисления остатка от деления (mod). Он вычисляет остаток, то есть x % y возвращает остаток от целочисленного деления x на y. Например, 6 % 3 будет равно нулю, так как остатка от операции деления шести на три не будет. Вычисление 6 % 4 даст 2, поскольку в остатке при делении шести на четыре будет два.

Оператор mod можно применить здесь для более простой реализации перехода к началу последовательности чисел. Заметьте, что 0 % 6 даст ноль, 1 % 6 даст один, …, 5 % 6 даст пять. Каждое из этих чисел меньше шести, в связи с чем будет само являться остатком от деления на шесть. Числа от нуля до пяти соответствуют действительным индексам snow, поэтому хорошо, что % их не меняет. А для индекса 6 операция 6 % 6 даст ноль: шесть на шесть делится без остатка, перенося нас к началу последовательности чисел снежинки.

Обновим функцию identical_right с использованием оператора %. В листинге 1.4 показан ее доработанный вариант.

Листинг 1.4. Определение идентичности снежинок перемещением вправо с вычислением остатка

int identical_right(int snow1[], int snow2[], int start) {

int offset;

for (offset =0; offset < 6; offset++) {

if (snow1[offset] != snow2[(start + offset) % 6])

return 0;

}

return 1;

}

Использовать прием с получением остатка или нет — дело ваше. Он сокращает одну строку кода и является шаблоном, который знаком многим программистам. Тем не менее применить его не всегда возможно, даже для задач, требующих сброса индекса, — например, identical_left. Как раз сейчас мы к этому и перейдем.

Проверка влево

Функция identical_left очень похожа на identical_right, но здесь нам нужно сначала перемещаться влево, а затем переходить к правой стороне. При обходе снежинки вправо мы не должны были использовать индекс 6 и выше. На этот раз нужно избегать обращения к индексу -1 и ниже.

К сожалению, в данном случае решение с получением остатка не подойдет. В Cи -1 / 6 дает ноль, оставляя остаток -1, то есть -1 % 6 будет -1. Нам же нужно, чтобы операция -1 % 6 давала пять.

В листинге 1.5 приведен код функции identical_left.

Листинг 1.5. Определение идентичности снежинок перемещением влево

int identical_left(int snow1[], int snow2[], int start) {

int offset, snow2_index;

for (offset =0; offset < 6; offset++) {

snow2_index = start - offset;

if (snow2_index < 0)

snow2_index = snow2_index + 6;

if (snow1[offset] != snow2[snow2_index])

return 0;

}

return 1;

}

Обратите внимание на сходство между этой функцией и функцией из листинга 1.3. Все, что мы изменили, — это выполнили вычитание смещения вместо его добавления и изменили граничную проверку с 6 на -1.

Объединение функций проверки

Используя вспомогательные функции identical_right и identical_left, напишем функцию are_identical, которая будет сообщать, идентичны две снежинки или нет. В листинге 1.6 приведен код для этой функции. Мы проводим сравнение снежинок с перемещениями вправо и влево для каждой возможной стартовой точки в snow2.

Листинг 1.6. Определение идентичности снежинок

int are_identical(int snow1[], int snow2[]) {

int start;

for (start = 0; start < 6; start++) {

if (identical_right(snow1, snow2, start)) ❶

return 1;

if (identical_left(snow1, snow2, start)) ❷

return 1;

}

return 0;

}

Вначале мы сравниваем snow1 и snow2, перемещаясь вправо по snow2 ❶. В случае их идентичности возвращается 1 (true). Далее идет проверка перемещением влево ❷.

Здесь есть смысл приостановиться и протестировать функцию are_identical на примере нескольких пар снежинок. Выполните это самостоятельно, прежде чем продолжать.

Решение 1: последовательное сравнение

Когда нам нужно сравнить две снежинки, мы применяем вместо оператора == функцию are_identical. Теперь их сопоставление стало таким же простым, как сравнение двух целых чисел.

Давайте перепишем функцию identify_identical из листинга 1.1 так, чтобы она использовала новую are_identical из листинга 1.6. Мы будем сравнивать пары снежинок и получать одно из двух сообщений, в зависимости от результата проверки их идентичности. Код приведен в листинге 1.7.

Листинг 1.7. Поиск идентичных снежинок

void identify_identical(int snowflakes[][6], int n) {

int i, j;

for (i = 0; i < n; i++) {

for (j = i+1; j < n; j++) {

if (are_identical(snowflakes[i], snowflakes[j])) {

printf("Twin snowflakes found.\n");

return;

}

printf("No two snowflakes are alike.\n");

}

Функция identify_identical для снежинок почти полностью совпадает с ее версией для целых чисел из листинга 1.1. Все, что мы сделали, — это заменили == на функцию, сравнивающую снежинки.

Считывание входных данных

Текущее решение пока не закончено. Нужно еще написать код для считывания снежинок из стандартного потока ввода. Сперва вернемся к описанию задачи в начале главы. Нужно считать строку с целым числом n, указывающим общее число снежинок, после чего считать каждую из n строк как отдельную снежинку.

В листинге 1.8 приведена функция main, которая обрабатывает входные данные и затем вызывает identify_identical (листинг 1.7).

Листинг 1.8. Функция main для Решения 1

#define SIZE 100000

int main(void) {

static int snowflakes[SIZE][6]; ❶

int n, i, j;

scanf("%d", &n);

for (i = 0; i < n; i++)

for (j = 0; j < 6; j++)

scanf("%d", &snowflakes[i][j]);

identify_identical(snowflakes, n);

return 0;

}

Обратите внимание, что массив snowflakes теперь стал статическим ❶. Дело в том, что он огромен, и, если не сделать его статическим, размер необходимого пространства просто превысит объем доступной для данной функции памяти. С помощью ключевого слова static массив помещается в отдельную область памяти, где его размер уже не вызовет сложностей. Тем не менее эту возможность нужно использовать осторожно. Стандартные локальные переменные инициализируются при каждом вызове функции, а статические сохраняют значение, полученное от предыдущего вызова функции (см. «Ключевое слово static» на с. 21).

Также заметьте, что созданный массив может содержать до 100000 снежинок ❶. Вас может обеспокоить такая растрата памяти. Что, если на входе окажется всего несколько снежинок? В конкурсных задачах считается нормальным жестко прописывать требования памяти для максимального количества входных данных, так как ваше решение наверняка будут проверять методом стресс-тестирования.

Концовка функции проста. Мы считываем количество снежинок с помощью scanf и используем это число для управления количеством итераций цикла for. В каждой итерации перебор происходит шесть раз, по разу для каждого целого числа. Далее вызывается identify_identical, которая выводит результат.

Объединив функцию main с другими ранее написанными функциями, мы получаем завершенную программу, которую можно отправлять на проверку. Попробуйте… и вы получите ошибку «Time-Limit Exceeded» (превышен лимит времени). Похоже, здесь еще есть над чем поработать.

Выявление проблемы

Наше первое решение оказалось слишком медленным, и мы получили ошибку «Time-Limit Exceeded». Проблема кроется в двух вложенных циклах for, которые сравнивают все снежинки между собой. В результате, когда число n оказывается большим, выполняется огромное число операций сравнения.

Давайте определим, сколько же таких операций выполняет наша программа. Поскольку мы сравниваем каждую пару снежинок, можно переформулировать этот вопрос в отношении именно пар. Например, если даны четыре снежинки 1, 2, 3 и 4, то наша схема выполняет шесть сравнений: снежинок 1 и 2, 1 и 3, 1 и 4, 2 и 3, 2 и 4, а также 3 и 4. Каждая пара формируется выбором одной из n снежинок в качестве первой и одной из оставшихся n –1 снежинок в качестве второй.

Для каждого из n решений для первой снежинки есть n – 1 решений для второй. В общей сложности это дает n(n – 1) решений. Но формула n(n – 1) удваивает фактическое количество сравнений снежинок, то есть, к примеру, включает и сравнение 1 с 2, и сравнение 2 с 1. Наше же решение сравнивает их только один раз, поэтому мы можем добавить в формулу делитель 2, получив n(n – 1)/2 сравнений для n снежинок.

На первый взгляд такое вычисление не выглядит медленным, но давайте подставим в n(n – 1)/2 разные значения n. Если взять 10, получится 10(9)/2 = 45. С выполнением 45 сравнений любой компьютер справится за считанные миллисекунды. Что насчет 100? Теперь получается 4950: тоже никаких проблем. Выходит, что для небольших значений n все работает хорошо, но условие задачи говорит, что количество снежинок может достигать 100 000. Давайте подставим в формулу n(n – 1)/2 это значение. Теперь получается 4 999 950 000 операций сравнения. Если выполнить тест для 100 000 снежинок на обычном ноутбуке, то вычисление может занять до четырех минут. А по условиям задачи необходимо уложиться в 2 секунды. В качестве ориентира можно считать, что современный компьютер способен выполнять в секунду около 30 миллионов операций. Это значит, что попытка уложить 4 миллиарда сравнений в 2 секунды, безусловно, обречена на провал.

Если раскрыть скобки в n(n – 1)/2, получится n2/2 – n/2. Самая большая степень здесь — это квадрат. Поэтому создатели алгоритма и назвали его O(n2), или алгоритмом с квадратичным временем. O(n2) произносится как «О-большое от n в квадрате» и является показателем скорости, с которой количество работы растет по отношению к размеру задачи. Краткая информация об «О-большом» приведена в приложении А.

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

Сортировка снежинок

В Cи есть библиотечная функция qsort, позволяющая легко упорядочить массив. Главное, что нам потребуется, — это функция сравнения, которая получает ссылки на два сортируемых элемента и возвращает отрицательное целое число, если первый элемент меньше второго, 0, если они равны, и положительное целое число, если первый больше второго. Можно использовать are_identical для определения, являются ли две снежинки одинаковыми, и если да, то возвращать 0.

Как при этом определить, что одна снежинка больше или меньше другой? Нужно просто принять соответствующее правило. Например, можно установить, что «меньшей» снежинкой считается та, чей первый отличающийся элемент меньше, чем соответствующий элемент другой снежинки. Это реализуется в листинге 1.9.

Листинг 1.9. Функция сравнения для упорядочивания

int compare(const void *first, const void *second) {

int i;

const int *snowflake1 = first;

const int *snowflake2 = second;

if (are_identical(snowflake1, snowflake2))

return 0;

for (i = 0; i < 6; i++)

if (snowflake1[i] < snowflake2[i])

return -1;

return 1;

}

К сожалению, упорядочивание таким образом не поможет решить проблему. Ниже приведен тестовый пример с четырьмя снежинками, который наверняка будет решен с ошибкой:

3 4 5 6 1 2

2 3 4 5 6 7

4 5 6 7 8 9

1 2 3 4 5 6

Первая и четвертая снежинки идентичны, но выводится сообщение «No two snowflakes are alike». Что же не так?

Вот два факта, которые qsort выявит в процессе выполнения:

1. Снежинка 4 меньше снежинки 2.

2. Снежинка 2 меньше снежинки 1.

Исходя из этого, qsort заключает, что снежинка 4 меньше снежинки 1, и непосредственно их не сравнивает. Здесь она опирается на транзитивное свойство: если a меньше b и b меньше c, то однозначно a должно быть меньше c. Кажется, что наши определения «меньше» и «больше» имеют смысл.

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

Как правило, при обработке данных группировка схожих значений оказывается эффективной. К тому же хорошие алгоритмы сортировки выполняются быстро — однозначно быстрее O(n2), но в нашем случае сортировку применить не получится.

Решение 2: сокращение числа вычислений

Сравнение всех пар снежинок и попытка их упорядочивания оказались слишком трудоемкими вариантами решения. Поэтому мы постараемся избежать сравнения тех снежинок, различие которых очевидно. Например, дано две снежинки:

1, 2, 3, 4, 5, 6

82, 100, 3, 1, 2, 999

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

Числа во второй снежинке существенно отличаются от чисел первой. Для выявления очевидного отличия снежинок без их прямого сравнения можно предложить сопоставление их первых элементов, так как 1 сильно отличается от 82. Теперь рассмотрим такие снежинки:

3, 1, 2, 999, 82, 100

82, 100, 3, 1, 2, 999

Они оказываются идентичными несмотря на то, что 3 сильно отличается от 82.

Быстро проверить, могут ли две снежинки быть идентичными, можно на основе суммы их элементов. При сложении значений приведенных выше образцов снежинок для 1, 2, 3, 4, 5, 6 мы получаем значение 21, а для 82, 100, 3, 1, 2, 299 значение 1187. Таким образом, мы говорим, что код для первой снежинки равен 21, а для второй — 1187.

Далее мы будем помещать «снежинки 21» в одну корзину, а «снежинки 1187» в другую и никогда не станем сравнивать снежинки из этих корзин между собой. Такой сортировке можно подвергнуть каждую снежинку: суммировать ее элементы, получить код x и затем сохранить ее вместе с другими снежинками, имеющими код x.

Конечно же, обнаружение двух снежинок с кодом 21 не будет означать, что они идентичны. Например, 1, 2, 3, 4, 5, 6 и 16, 1, 1, 1, 1, 1 имеют код 21, но при этом очевидно не идентичны.

Это нормально, так как наше правило «суммирования» предназначено для отсеивания снежинок, которые точно не могут быть идентичными. Это позволяет избежать сравнения всех пар — приема, ставшего причиной неэффективности решения 1, — и сопоставлять только те из них, которые не были отфильтрованы.

В решении 1 мы последовательно сохраняли каждую снежинку в массиве: первую в индексе 0, вторую в индексе 1 и т.д. Здесь же стратегия сохранения изменится: расположение снежинок в массиве будет определяться кодами их сумм. Это значит, что для каждой снежинки мы будем вычислять код и использовать его в качестве индекса, определяющего место ее хранения.

Здесь потребуется ответить на два вопроса:

1. Как вычислять код каждой снежинки?

2. Что делать, если коды нескольких снежинок будут совпадать?

Начнем с вычисления кода.

Вычисление кода суммы

На первый взгляд вычисление кода выглядит простым. Можно просто складывать все числа каждой снежинки:

int code(int snowflake[]) {

return (snowflake[0] + snowflake[1] + snowflake[2]

+ snowflake[3] + snowflake[4] + snowflake[5]);

}

Такой вариант отлично подойдет для многих снежинок, таких как 1, 2, 3, 4, 5, 6 и 82, 100, 3, 1, 2, 999. Но рассмотрите снежинку с огромными значениями лучей, например:

1000000, 2000000, 3000000, 4000000, 5000000, 6000000

Здесь значение кода суммы составит 21 000 000. Если мы планируем использовать его в качестве индекса, то потребуется объявить массив размером 21 миллион элементов, что будет вопиющей тратой памяти.

Наша цель — придерживаться массива, имеющего место под 100 000 элементов. Поэтому код снежинки должен соответствовать диапазону между 0 и 99 999 (минимальный и максимальный индексы массива). Один из способов выполнения этого условия — использование уже знакомого нам оператора %. Вычисление остатка неотрицательного целого числа x даст целое число между 0 и x – 1. Какой бы ни была сумма длин лучей снежинки, если мы вычислим ее остаток по модулю 100 000, то получим допустимый индекс массива.

Но у этого метода есть и недостаток: взятие остатка приведет к вероятности получения большего числа снежинок с одинаковым кодом. Например, суммы для 1, 1, 1, 1, 1, 1 и 100001, 1, 1, 1, 1, 1 будут разными — 6 и 100006, но остаток по модулю 100 000 в обоих случаях равен 6. Этот риск допустим: мы просто понадеемся, что такие ситуации будут редкими, а при их возникновении выполним парное сравнение.

Листинг 1.10 вычисляет код суммы снежинки и его остаток по модулю.

Листинг 1.10. Вычисление кода снежинки

#define SIZE 100000

int code(int snowflake[]) {

return (snowflake[0] + snowflake[1] + snowflake[2]

+ snowflake[3] + snowflake[4] + snowflake[5]) % SIZE;

}

Коллизии кодов снежинок

В решении 1 для сохранения снежинки в индексе i массива snowflakes мы использовали следующий фрагмент:

for (j = 0; j < 6; j++)

scanf("%d", &snowflakes[i][j]);

Этот вариант работал, так как в каждой строке двумерного массива сохранялась только одна снежинка.

Теперь же нам нужно разобраться с коллизией типа 1, 1, 1, 1, 1, 1 и 100001, 1, 1, 1, 1, 1, когда из-за одинакового остатка по модулю две снежинки будут сохраняться в одном индексе массива. Это значит, что каждый элемент массива будет уже не одной снежинкой, а коллекцией из некоторого числа снежинок.

Для сохранения элементов в одном индексе можно использовать связный список, структуру данных, связывающую каждый элемент со следующим. В нашем случае каждый элемент в массиве будет указывать на первую снежинку в связном списке. К остальным снежинкам можно будет обращаться через указатели next.

Рассмотрим типичную реализацию связного списка. Каждый узел snowflake_node будет содержать снежинку и указатель на следующий компонент-снежинку. Для сбора этих двух компонентов узла мы используем структуру (struct). Также мы задействуем ключевое слово typedef, что позволит в дальнейшем использовать snowflake_node вместо полной инструкции struct snowflake_node:

typedef struct snowflake_node {

int snowflake[6];

struct snowflake_node *next;

} snowflake_node;

Нам придется обновить функции main и identify_identical, так как ранее они использовали массивы.