Как научиться решать олимпиадные задачи по программированию
Школьник об олимпиадном программировании / Хабр
Здравствуй, Хабр!
Пишет тебе девятиклассник, призер регионального этапа всероссийской олимпиады по информатике. В последнее время я стал замечать, что у хабражителей повысился интерес к олимпиадам по программированию. Как их активный участник я постараюсь ответить на все вопросы, рассказать о своем пути, привести примеры реальных, запомнившихся мне задач.
Об обучении
Учусь я в школе с углубленным изучением физики, математики и информатики.
Что же это за школа, как в ней учиться и как в нее поступить?
Отбор проходит в два этапа. Первый — экзамен по физике и математике. После него некоторые счастливчики попадают на собеседование, где от них требуется решить несколько олимпиадных задач по математике. И только после этого самые умные и удачливые становятся учениками.
Учиться очень тяжело и сложно. Учителя требуют идеального знания чуть ли не всех предметов. На родительском собрании сказали: «В начале обучения абсолютно все ученики скатываются до двоек, даже отличники. Те, кто начинают реально учиться — получают хорошие оценки. Остальные отсеиваются». У меня больше всего было проблем с русским языком и литературой, как бы это ни было странно.
Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.
Задачи
Посмотрим на совершенно типичную задачу для начинающих программистов-олимпиадников
Пятью пять — двадцать пять!
(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Вася и Петя учатся в школе в одном классе. Недавно Петя поведал Васе о хитром способе возведения в квадрат натуральных чисел, оканчивающихся на цифру 5. Теперь Вася может с легкостью возводить в квадрат двузначные (и даже некоторые трехзначные) числа, оканчивающиеся на 5. Способ заключается в следующем: для возведения в квадрат числа, оканчивающегося на 5 достаточно умножить число, полученное из исходного вычеркиванием последней пятерки на следующее по порядку число, затем остается лишь приписать «25» к получившемуся результату справа. Например, для того, чтобы возвести число 125 в квадрат достаточно 12 умножить на 13 и приписать 25, т.е. приписывая к числу 12*13=156 число 25, получаем результат 15625, т.е. 1252=15625. Напишите программу, возводящую число, оканчивающееся на 5, в квадрат для того, чтобы Вася смог проверить свои навыки.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число А, оканчивающееся на цифру 5, не превышающее 4*10^5.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно натуральное число — A2 без лидирующих нулей.
Примеры:
INPUT.TXT
5
75
4255
OUTPUT.TXT
25
5625
18105025
Требования
От олимпиадника требуется написать программу на одном из принимаемых языков (обычно этот набор состоит из Pascal (сам пишу, никогда проблем не было), Delphi, C++, Java, Visual Basic, в последнее время добавляют C#, Python). После этого исходный файл отправляется в систему-песочницу, где он компилируется и выполняется на группе тестов. За каждый тест участник олимпиады получает некоторый балл, которые потом складываются. После олимпиады результаты становятся видны всем. Чем больше суммарный балл — тем выше место.
Стоит отметить, что обычно проверяющими системами плохо обрабатывается управляемый код (Java, C#). Мой друг лично на региональном этапе получил на трех из четырех задач 0 баллов из-за ошибки во время выполнения (писал на C#), хотя проверялось все нормально. Что делать в таком случае не понял ни я, ни он; на апелляции жюри просто пожали плечами.
Риски
На чем можно проиграть? Существуют 7 типов ошибок:
Скрытый текстWrong answer
Неверный ответ. Результат работы программы не совпадает с ответом жюри
Неверный формат вывода или алгоритмическая ошибка в программе
Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе
Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла
Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main
Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти
Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата
Олимпиады
Как проходит всероссийская олимпиада по информатике?
Я прошел всего 5 этапов: 8-9 классы в школе, 8-11 классы в школе, муниципальный этап, дистанционный тур региональной олимпиады, региональная олимпиада. Далее идет всероссийский тур, но я на него, к сожалению, не попал. Сейчас я расскажу про те задачи, которые мне очень понравились.
Этап среди старшеклассников
Во время тура среди 8-11 классов была задача «Полиномиальные хэш функции» условие которой было записано на двух страницах формата A5. В этом условии была приведена краткая информация о хэш функциях, их истории, была предложена одна такая функция. Задача заключалась в её вычислении для массива входных данных. Нас испугало очень страшное название, сложная терминология, запись суммы её значком (тот который выглядит как буква E) и в результате её мало кто вообще начал решать. Условие сейчас найти, к сожалению, не смогу.
Муниципальный этап
Муниципальный этап получился просто убийственным по сложности.
Вот задача оттуда
Б. Бобр
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
Формат входных данных:
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 – соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число – расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево. Известно, что деревьев гарантированно хватает, чтобы построить все объекты (N>=M*L)
Формат выходных данных:
Для каждого тестового блока в отдельной строке необходимо вывести единственное число — сумму координат мест, в которых необходимо возвести объекты, чтобы суммарное расстояние, на которое потребуется перенести деревья для строительства, было минимальным, указав три точных знака после десятичного разделителя.
Пример входных и выходных данных:
Входные данные
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
1
2
Выходные данные
7.300
1.000
Решить задачу, если объект один достаточно просто. Но когда объектов больше — приходится применять достаточно сложный раздел программирования, «Динамическое программирование». Учитель, который вел у нас факультатив признался в том, что он плохо представляет как решить эту задачу (совместными усилиями мы вывели значение, которое нужно минимализировать, просто построив несколько графиков, даже не спрашивайте что это за значение — я его благополучно забыл).
В результате задачу на полный балл решил лишь один участник олимпиады.
А. Альбатрос
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Альбатрос может совершать длительные перелеты, преодолевая длинные расстояния над просторами океана. Орнитологи решили определить, сколько километров может пролететь альбатрос, не посещая сушу. Для этого флотилия плавучих исследовательских лабораторий рассредоточилась по океану и записала данные об изучаемой особи, к которой прикреплена радиометка. Ученые фиксируют момент времени и текущие координаты того места, где они обнаружили альбатроса.
Напишите программу, определяющую расстояние, которое преодолел альбатрос в течение эксперимента, если считать, что в зоне наблюдений наша планета представляет собой идеальный шар радиусом 6366,197 километров.
Формат входных данных:
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится единственное целое положительное число 2<=N<=1000, количество записей о появлении альбатроса. В каждой из следующих N строчек записаны по двенадцать целых неотрицательных чисел (0<=d1<=90, 0<=m1<=90, 0<=s1<=90, 0<=d2<=90, 0<=m2<=90, 0<=s2<=90, 0<=h<=23, 0<=mt<=59, 0<=sec<=59, 1<=dd<=31, 1<=mm<=12, 2000<=yy<=2012) – соответственно градусы минуты и секунды северной широты, градусы, минуты и секунды западной долготы того места, где плавучая исследовательская лаборатория заметила альбатроса; время в формате часы, минуты, секунды и дата наблюдения в формате день, месяц, год.
Формат выходных данных:
Для каждого из тестовых блоков в отдельной строке необходимо вывести единственное целое число – расстояние, которое преодолел альбатрос, округленное до ближайшего четного целого числа.
Пример входных и выходных данных:
Входные данные
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Выходные данные
4
2
Достаточно простая задача: необходимо отсортировать значения по дате появления Альбатроса, вычислить длину каждой дуги между двумя точками, а потом их все сложить. В решении принимается допущение, которое позволяет использовать теорему Пифагора.
Но почему же решение было пересмотрено? Взглянем на диапазон минут и секунд.
0<=m1<=90, 0<=s1<=90
Вы, наверное, наивно предположили, что в одном градусе 60 минут? Или что в одной минуте 60 секунд? Ха-ха! Тут же явно написано «90».
Тесты были составлены именно с учетом перевода: в одном градусе 60 минут, в одной минуте 60 секунд. Это безобразие было успешно оспорено нашими учителями.
Самое обидное, что даже пример получился неправильный
В результате задачу не решил, по-моему, вообще никто.
Полный текст муниципального этапа можно найти тут.
Дистанционный тур
Задачи дистанционного тура были гораздо интереснее. Мне запомнились две задачи.
Вот перваяГ. Герой дня
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
Медиахолдинг «Пермь Великая» отслеживает сообщения блоггеров Пермского края и каждый день пытается выяснить, кто является наиболее популярным в записях для того чтобы включить этого человека в традиционную рубрику «Герой дня».
Для каждой записи, попавшей в список отслеживания, известно количество просмотров и те персоналии, которые в ней упоминаются. Напишите программу, определяющую человека, для которого суммарное количество просмотров для записей, где он упоминается, максимально.
Формат входных данных:
В первой строке входных данных приводится единственное целое число 1
Формат выходных данных:
В единственной строке выходных данных необходимо вывести имя и фамилию человека, записи с упоминанием которого набрали больше всего просмотров. Если таких людей несколько нужно вывести того, кто идет раньше других по алфавиту.
Примеры входных и выходных данных:
Входные данные
1
100500 John Travolta John Lennon
5
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Выходные данные
John Lennon
Arnold Schwarzenegger
Именно после этой задачи мне пришла идея «словаря», тип данных с удобным поиском по людям. Если кому интересно — напишу в комментариях, можете спросить в ЛС, но чувствую что это тот еще велосипед.
Необходимо составить список из людей с общим количеством просмотров (посмотрите на человека с идентификатором Arnold Schwarzenegger, требуется длинная арифметика), а затем просто выбрать нужного человека из нашего списка. Чтобы упростить алгоритм наши одиннадцатиклассники использовали хэш-функцию для имени (сумма всех ASCII номеров символов в имени), что существенно ускорило работу программы, коллизии получились небольшими.
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.
Достаточно простой алгоритм сжатия (не помню как называется). Мне было интересно реализовать. Я решил эту задачу созданием массива из слов, добавлял туда первое слово. Затем считывал каждое следующее слово, проверял, нет ли его в массиве. Если оно было — записывал в выходной поток номер слова, иначе — добавлял в массив, записывал номер.
В принципе, мое решение не получило полный балл.
Полный текст заданий можно найти здесь.
На дистанционном туре я занял 1 место среди девятиклассников.
Региональный этап
На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.
На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.
Подготовка
Как же я готовился?
Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.
Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?
- Существуют системы подготовки школьников к олимпиадам по программированию, на них есть тестовая система и куча условий с решениями. Насколько я понимаю, на всех таких системах нужна регистрация. Я готовился при помощи двух:
- acmp.ru Есть достаточно много задач разной сложности, так же интересен раздел «Курс олимпиадника»
- http://acm.timus.ru/ Куча задач с самых разных олимпиад, некоторые на английском. В разделе http://acm.timus.ru/offline у нас проводился дистанционный и региональный этапы.
- Существуют онлайн олимпиады, я участвовал лишь в одной: NetOI от украинцев. Отзыв такой: ХАРДКОР!!! Дальше второго тура не прошел. Код нужно писать ужасно оптимально (я так не умею), для каждого теста индивидуальные условия (удвоенное время программы жюри).
Что же дальше?
Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.
Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя — выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.
В фото для топика было использовано фото с www.psu.ru
Олимпиада по математике x Соревновательное программирование
Я бы сказал, что тренировка по задачам МО, вероятно, не самый эффективный способ практики. Несколько мыслей по этому поводу:
Во-первых, я считаю справедливым сказать, что уровень математических знаний, которых ожидают от соревновательного программирования, существенно выше, чем уровень, на котором тестируется большинство других тем. Вероятной причиной этого является то, что многие конкурентоспособные программисты начинали с математических олимпиад - я потратил пять лет на подготовку к математическим олимпиадам, прежде чем я когда-либо услышал о соревнованиях по программированию, например, и продолжал делать это еще четыре года, прежде чем наконец переключиться на на соревнования по программированию полностью в начале этого года.
Тем не менее, соревновательное программирование обычно основывается на относительно небольшом подмножестве материала, тестируемого на математических олимпиадах. Например, геометрия в стиле олимпиад почти никогда не встречается, а функциональные уравнения обычно не имеют отношения к соревнованиям по программированию. Большинство тем по алгебре также обычно не проверяются на уровне олимпиад. Комбинаторике и теории чисел уделяется большое внимание на соревнованиях по программированию, хотя даже в этом случае стиль задачи обычно отличается от типа задач, которые возникают на олимпиадах по математике.(Кстати, AtCoder предоставляет основные исключения из этого правила - я помню, что в прошлом у них были некоторые проблемы с синтетической геометрией, и я помню недавний ABC, связанный с проблемой полиномиальной интерполяции.)
В результате я подумайте, что если вы собираетесь выполнять задачи, вы, вероятно, извлечете больше пользы из решения задач по математике на соревнованиях по программированию, чем на олимпиадах по математике. (Это также имеет интуитивный смысл - они будут ближе к тому, что вы увидите на реальных соревнованиях по программированию.Однако может случиться так, что если у вас нет большого математического образования, вы захотите найти ресурсы, чтобы подробно изучить математическую теорию.
Я лично рекомендую Intermediate Counting and Probability в качестве источника по комбинаторике. Задачи теории чисел, как правило, не требуют большого опыта в контексте соревновательного программирования и обычно сводятся к модульной арифметике, но разделы до 3.2 (плюс, возможно, 5.1) в этой книге могут быть полезны. Включенные задачи, вероятно, немного сложнее, чем NT, которая возникает на соревнованиях по программированию.
.Как решать проблемы программирования
Прямо перед праздником я сказал, что вам лучше научиться решать задачи программирования.
На этот раз я попытаюсь дать вам несколько хороших инструментов, которые помогут вам научиться решать проблемы программирования. (На самом деле именно проблемы типа алгоритма.)
Типичные ошибки
Когда большинство программистов сталкиваются с проблемой программирования на собеседовании, они делают несколько ключевых ошибок.Самая серьезная из них - неправильное распределение времени.
Если вы слышали поговорку «дважды отмерь и один раз отрежь», то, вероятно, вам знакома идея заранее потратить время на то, чтобы убедиться, что что-то сделано правильно, вместо того, чтобы сразу приступить к делу.
Самая распространенная ошибка, которую я вижу, проводя интервью или наблюдая за тем, как кто-то пытается решить проблему программирования, заключается в том, что они пытаются начать писать код как можно скорее.
Вы должны противостоять этому побуждению.
Вы действительно хотите убедиться, что у вас достаточно времени, чтобы полностью разобраться в проблеме, прежде чем пытаться ее решить.
Еще одна большая ошибка - попытка перерешить решение на первой итерации. Будьте проще, не пытайтесь фантазировать.
Простой набор шагов
Я собираюсь дать вам простой набор шагов, которые вы можете использовать для решения любой задачи программирования типа алгоритма.
- Прочтите задачу полностью дважды.
- Решите проблему вручную, используя 3 набора образцов данных.
- Оптимизация ручных шагов.
- Напишите шаги вручную в виде комментариев или псевдокода.
- Замените комментарии или псевдокод реальным кодом.
- Оптимизируйте реальный код.
До 70% нашего времени следует тратить на шаги 1–3.
Давайте посмотрим на каждый шаг.
Прочтите задачу полностью дважды
Это самый важный шаг. Вы даже можете прочитать задачу 3 или 4 раза.
Вы хотите убедиться, что полностью понимаете проблему.Хорошая проверка - можете ли вы объяснить проблему кому-то другому.
Я не могу переоценить важность этого шага!
Если вы не понимаете проблему, вы не можете ее решить. Не бойтесь тратить здесь время, потому что чем лучше вы поймете проблему, тем легче будет ее решить.
Если вам приводятся какие-либо примеры вместе с проблемой, убедитесь, что вы проработали эти примеры и понимаете, почему ответы верны для каждого из них.
Решить проблему вручную
Я собираюсь рассказать вам, пожалуй, самый большой секрет программирования.«Ничего нельзя автоматизировать, чего нельзя сделать вручную!»
Программирование автоматизируется просто и понятно. У вас может быть возможность пропустить ручные шаги и сразу перейти к коду, но есть ручной процесс, который является основой любого кода, который вы пишете.
Очень важно сначала решить проблему вручную, чтобы вы знали, что собираетесь автоматизировать, иначе вы просто набрасываете код.Что, хотя и может быть забавным, заставит вас выглядеть идиотом на собеседовании по программированию и, вероятно, заставит вас сильно вспотеть.
Я рекомендую вам решить проблему как минимум с тремя различными входами, чтобы убедиться, что вы действительно понимаете свое решение и что оно будет работать более чем в одном случае.
Если возможно, я часто использую метод математической индукции. Используя этот подход, я мог бы попытаться решить сначала 1, затем 2, а затем n.
Также не забывайте искать угловые и крайние случаи и делать любые примеры для тех случаев, о которых вы только можете подумать.
Очень важно, когда вы решаете проблему вручную, вы понимаете, что ваш мозг на самом деле делает для решения проблемы. Возможно, вам придется записать все, что вы обычно храните в голове. Вы хотите быть в курсе каждого шага, их легко замалчивать.
Давайте посмотрим на очень простой пример, перевернув строку.
Если я дам вам строку «Зебра» и попрошу перевернуть ее, большинство людей выполнят следующие действия вручную.
- Напишите «Зебра».
- Начните новое слово и поставьте «а» в качестве первой буквы. (Почему -> потому что это последняя буква, мы хотим начать здесь)
- Введите «r» как вторую букву. (Почему -> потому что это следующая буква в обратном направлении от последней буквы, которую мы скопировали)
- Введите «b» в качестве третьей буквы. (Почему -> то же, что и выше)
- и т. Д.
Обратите внимание, как я записываю каждый маленький шаг и почему.
Оптимизация ручного решения
Люди часто не осознают, насколько ценен этот шаг.Намного легче перестроить и реконструировать идею или алгоритм в голове, чем в коде.
Попытка оптимизировать фактическое решение или упростить его, когда оно все еще находится в наиболее легко податливом состоянии, стоит того.
Что вы хотите здесь сделать, так это выяснить, есть ли другой способ более легкого решения проблемы, или есть некоторые шаги, которые вы можете сократить или упростить.
Давайте посмотрим на наш пример разворота строки и посмотрим, сможем ли мы упростить шаги.
Мы должны сразу понять, что здесь мы можем использовать цикл, чтобы уменьшить количество шагов, выполняемых вручную. Наша повторяющаяся причина для большинства наших шагов говорит нам, что мы делаем одно и то же снова и снова для каждого шага, только с разными данными.
- Напишите «Зебра».
- Начните с последней буквы в слове и создайте новое пустое слово.
- Добавить текущую букву к новому слову
- Если есть предыдущая буква, сделайте предыдущую букву текущей и начните с 3.
Посмотрите, насколько мы близки к написанию кода. У вас должно возникнуть желание написать для этого код. Это хорошо, это говорит о том, что вы хорошо решили и упростили задачу. Написание кода теперь должно стать очень простым.
Написать псевдокод или комментарий
Много раз вы можете пропустить этот шаг, если вы действительно хорошо разбираетесь в проблеме или ваши предыдущие шаги уже создали достаточно подробное описание решения, чтобы его кодирование уже было переводом 1 к 1.
Если вы новичок или боретесь с подобными проблемами, я все равно не тороплюсь и сделаю этот шаг.
Здесь мы хотим зафиксировать все шаги, которые мы создали, и теперь либо поместить их в наш редактор в виде комментариев, либо записать их как псевдокод, который мы можем преобразовать в реальный код.
Делая это, мы можем точно знать, как будет выглядеть структура кода, который мы собираемся написать, что делает работу по заполнению фактического кода позже тривиальной.
Давайте посмотрим на некоторый псевдокод для обращения строки.
// NewWord = «»
// Цикл назад по слову для обратного
// Новое слово + = CurrentLetter
// Вернуть NewWord
Довольно просто, но главное, что мы здесь сделали, - обрисовали структуру кода, который мы напишем для решения проблемы.
Заменить комментарии реальным кодом
На данном этапе этот шаг должен быть чрезвычайно простым. Если вы выполнили все остальные шаги, этот шаг вообще не предполагает решения проблем.
Все, что мы здесь делаем, это берем каждый комментарий и преобразуем его в реальную строку кода.
Если взять переворот строки, мы можем получить что-то вроде этого.
1 за 1 перевод комментариев, которые мы создали выше для реального кода.
Если у вас здесь проблемы, обычно есть две возможные причины:
- Вы не разбили задачу на достаточно маленькие шаги
- Вы недостаточно хорошо знаете свой язык программирования, чтобы выполнить преобразование.
Если вы недостаточно подробно разобрали проблему, попробуйте вернуться ко второму шагу и проявите как можно более дотошность.Записывайте каждый шаг. Я знаю, что это больно, но сделай это, поверьте, это того стоит.
Если вы недостаточно хорошо знаете свой язык программирования, чтобы выполнять перевод, возможно, вам придется освежить здесь некоторые базовые конструкции. На любом языке, на котором вы ожидаете, что он сможет решать проблемы типа алгоритма, вы должны знать, как делать следующие вещи:
- Создать список
- Сортировка списка или массива
- Создать карту или словарь
- Перебирать список или словарь
- Разобрать строки
- Преобразование из строки в int, int в строку и т. Д.
Если вы не знаете, как все это делать.Прекратите то, что вы делаете сейчас, и изучите их. Это не очень длинный список, и преимущества будут значительными.
Оптимизировать реальный код
Иногда в этом шаге нет необходимости, но стоит взглянуть на свой код и выяснить, можно ли вырезать несколько строк или сделать что-нибудь попроще.
Это также хорошее место, чтобы убедиться, что все ваши переменные имеют длинные значимые имена. Я не могу не подчеркнуть, насколько важно иметь хорошие имена для ваших переменных и методов, чтобы помочь человеку, оценивающему ваш код, понять, что вы пытаетесь сделать.Это особенно важно, если вы ошиблись!
Я не буду давать оптимизацию для нашего тривиального примера переворота строки, но здесь я советую не усложнять задачу. Просто постарайтесь в основном упростить свой код и избавиться от дублирования.
Несколько заключительных советов
Если вы следуете этому шаблону для решения проблемы типа алгоритма, вы должны очень хорошо справляться с программированием собеседований, но ключ к этому - уверенность в этом процессе.
Единственный способ обрести уверенность в этом процессе - это практиковать его.Требуется большая вера, чтобы поверить в то, что потратить 70% своих 30 минут на решение проблемы, просто думая о проблеме и не писать код, - это правильный подход, поэтому убедитесь, что у вас есть такая вера, когда она вам нужна.
Я уже говорил об использовании TopCoder, чтобы стать лучшим программистом, и до сих пор рекомендую его. Codility.com - еще один отличный сайт, с которым я недавно познакомился.
Есть один важный шаг, который я не включил в схему выше, потому что я не хотел усложнять процесс больше, чем нужно.
Часто вы обнаружите, что проблема сама по себе включает в себя несколько больших шагов или является очень сложной. В таких случаях вам нужно будет попытаться найти способ сократить проблему пополам, а затем следовать описанному выше процессу для каждой половины.
Этот метод решения проблемы называется «разделяй и властвуй» и весьма эффективен. Хороший способ узнать, где разделить проблему пополам, - это подумать о том, какая часть проблемы, если она вам уже дана, упростит решение остальной части.
Интервью по программированию - это всего лишь одна битва в большой войне: маркетинг себя. Чтобы получить полную информацию, взгляните на мой курс: «Как продвигать себя в качестве разработчика программного обеспечения».
.Как решать задачи в исчислении
Как решать задачи в исчислении
Опубликовано: 20 сентября 2012 г., университетская математикаТеги: математика, решение задач
Считается, что математические задачи труднее всего решить, словесные задачи продолжают пугать учащихся по всем математическим дисциплинам. Этот новый заголовок из серии «Мировые проблемы» раз и навсегда демистифицирует эти сложные проблемы, показывая даже самым боязливым математикам простые, пошаговые советы и приемы.В разделе «Как решать мировые проблемы в исчислении» рассматриваются важные концепции математического анализа и предлагаются решенные задачи и пошаговые решения. Когда студенты овладеют основными подходами к решению математических задач со словами, они будут уверенно применять эти новые математические принципы даже к самым сложным сложным задачам. Каждая глава содержит введение в тип проблемы, определения, связанные теоремы и формулы. Темы варьируются от жизненно важного обзора до исчисления до традиционных материалов первого курса по исчислению.Примеры задач с решениями и глава из 50 задач идеально подходят для самопроверки. Полностью объясненные примеры с пошаговыми решениями.
Как решать задачи со словами в исчислении - Евгений Дон. Бени Дон
Нравится:
Нравится Загрузка ...
