темы в памяти.
Лучшая, на мой взгляд, книга по работе с Cи — это второе издание C Programming: A Modern Approach К.Н. Кинга (K. N. King). Даже если вы хорошо знакомы с Cи, все равно рекомендую ее прочесть. Она оказывается отличным помощником, когда особенности этого языка вызывают сложности в понимании кода.
5 Ұнайды
Почему я применил именно умножение на 39 и добавление символа? Дело в том, что такой вариант не вызывал коллизий в тестовых примерах Codeforces. Да, я понимаю, что это неудовлетворительное решение.
3 Ұнайды
Введение
Я предполагаю, что вы знакомы с такими языками, как Cи, C++, Java или Python… и разбираетесь в теме. Тяжело объяснять людям, незнакомым с программированием, почему написание кода для решения задач является настолько захватывающим.
Я также надеюсь, что вы готовы поднять свои навыки программирования на новый уровень. Для меня будет честью помочь вам в этом.
Я мог бы начать с разъяснения всяких изощренных техник, рассказывая о том, какие они полезные, и сравнивая их с другими изощренными техниками. Но я не буду этого делать. Такие знания очень недолго хранятся в памяти, ожидая возможности применения на практике (которая порой так и не появляется).
Вместо этого я на протяжении всей книги буду ставить конкретные трудные задачи. Надеюсь, что вы не сможете справиться с ними сразу, используя знакомые вам подходы. Вы — программист. Вам нужно решать задачи. Пришло время освоить хитрые техники. Книга построена на постановке сложных задач с их последующим решением, при этом вы будете пополнять имеющиеся у вас знания.
Здесь вы не увидите типичных задачек из учебников, не будете искать оптимальный путь умножения последовательности матриц или вычисления чисел Фибоначчи. Я обещаю, что вы не будете решать и головоломку ханойской башни. Существует множество прекрасных учебников, где все это прописано, но я подозреваю, что немногих из вас такие головоломки действительно мотивируют.
Мой подход предполагает использование задач, которые вы ранее вряд ли встречали. Каждый год тысячи людей участвуют в соревнованиях по программированию, и для этих соревнований постоянно требуются новые задачи, чтобы оценивать реальные навыки участников, а не способность быстрее всех переделывать старое на новый лад или гуглить решение. Эти задачи удивительны, они базируются на классических подходах, но вносят в них изменения и интересный контекст, подталкивая людей к поиску новых решений. В таких задачах заключается практически безграничный объем знаний по программированию и вычислениям.
Начнем с основ. Структура данных — это способ организации данных для быстрого выполнения нужных операций. Алгоритм — это последовательность шагов при решении задачи. Иногда можно создать быстрый алгоритм без применения сложных структур данных. В других же случаях правильно подобранная структура может существенно ускорить решение. Моя задача — не сделать из вас участника соревнований по программированию, хотя это было бы хорошим бонусом, а научить работать со структурами данных и алгоритмами на примерах интересно поданных задач спортивного программирования. Пишите мне об успехах в своем обучении. Пишите также, если материалы этой книги заставят вас улыбнуться.
2 Ұнайды
, в главе 5 изучается алгоритм Дейкстры. Если вы поищете информацию о нем в Google, то узнаете, что он используется для поиска кратчайших путей.
Общее решение основной задачи можно выстроить из вторичных решений ее подзадач? Используйте рекурсию! Эти подзадачи пересекаются? Ускорьте алгоритм с помощью мемоизации!
Ваш алгоритм выполняет повторяющийся поиск или минимальные вычисления? Ускорьте его с помощью хеш-таблицы или min-кучи соответственно.
Структура данных — это способ организации данных для быстрого выполнения нужных операций. Алгоритм — это последовательность шагов при решении задачи.
Нет нужды заниматься парсингом входных данных до момента, пока мы не будем готовы решить всю задачу.
Ключевые
Обратите внимание, что массив snowflakes теперь стал статическим ❶. Дело в том, что он огромен, и, если не сделать его статическим, размер необходимого пространства просто превысит объем доступной для данной функции памяти. С помощью ключевого слова static массив помещается в отдельную область памяти, где его размер уже не вызовет сложностей.