В качестве хобби, я решаю олимпиадные задачки по программированию. Это помогает отвлечься от повседневных проблем, позволяя на часок другой уйти от мира в собственный астрал. Мой мозг, благодаря этому хобби, находится в постоянной спортивной форме.Я решил, что неплохо было бы поделиться с Вами алгоритмами, размышления, результатами, а также получить качественную критику моих путей решения задач.
Будем брать задачу, разбирать ее по частям, анализировать, выдумывать различные пути решения, выбирать лучший, а потом нести на суд «великих судей». Для многих, по моему мнению, такой час разгрузки будет очень полезным, а кому-то просто будет интересно посоревноваться и придумать свой алгоритм.
Задачи я буду брать с сайта http://uva.onlinejudge.org/, где располагается достаточно большая коллекция задач на любой вкус, и там же можно проверить свое решение. Выбирать буду случайным образом и всегда доводить начатое до финального решения, которое ознаменуется оценкой «Accepted» (Принято). Для решения этих задач нам потребуется знание одного из языков программирования: c, c++, java, pascal, а также терпение, логика и базовое знание английского языка, т.к. условия задач мы получаем на английском языке.
Итак, начнем мы с простой задачки из набора «Для новичков» для разминки, чтобы проверить свои способности.
Кратко переведу условие задачи (вольный перевод):
Правительство решило пометить всех людей, чтобы можно было за ними следить. Для этого каждому человеку в левое запястье имплантируется крошечный компьютер. В этом компьютере есть все виды личной информации, а также передатчик для контроля движения.
Каждый компьютер содержит уникальный идентификационный код, состоящий не более чем из 50 символов, построенный из строчных букв английского алфавита (26 букв). Набор символов для кода выбирается бессистемно.
Предположим, что в качестве набора символов было выбрано 3 символа «a», 2 символа «b» и 1 символ «c». При этих условиях можно построить 60 различных идентификационных кодов.
abaabc
abaacb
ababac
Это 3 из возможных кодов, на основе вышеуказанных условий, перечисленные в алфавитном порядке.
Нужно написать программу, помогающую генерировать эти идентификационные коды. Программа должна принимать последовательность символов (не более 50 строчных букв, которые могут повторяться) и печатать следующий идентификационный код в алфавитном порядке, если таковой существует. Если приведенный код последний (в алфавитном порядке) для заданного набора символов, то нужно напечатать «No Successor».
Входные данные будут содержать серию строк, каждая из которых будет представлять идентификационный код. Символ "#" будет означать окончание ввода
Выходные данные должны содержать по одному следующему коду на каждый входной код.
Если на вход подается abaacb, то наша программа должна ответить ababac.
В этом месте, заинтересовавшимся стоит свернуть статью и попробовать самостоятельно решить задачу. Гарантирую, что когда вы получите «Accepted», вы ощутите легкий душевный подъем и получите заряд бодрости.
Очевидно, что это задача из области «перестановок», т.е. ababac — это следующая перестановка в лексикографическом порядке после abaacb. На мой взгляд тут этот алгоритм описан очень неплохо, поэтому особо разбирать мы его не будем. Выпишем для себя основные шаги алгоритма:
- На первом шаге программы, двигаясь с конца массива, сравниваем соседние элементы, если предыдущий (по расположению в массиве) элемент больше следующего, двигаемся дальше, если меньше, останавливаемся и запоминаем его номер (m), этот элемент будет изменен.
- Элементы, стоящие слева от m-го, не изменяем. Среди элементов, стоящих справа, нужно выбрать элемент (k), который должен встать на место m-го. Это минимальный элемент среди тех, которые больше m-го.
- Меняем m-ый и k-ый элементы.
- Осталось упорядочить по возрастанию элементы, стоящие справа от нового m-го элемента, но т.к. они упорядочены по убыванию, достаточно их обернуть.
Главное, что необходимо не забыть учесть это то, что если нам не удалось найти следующую перестановку, то необходимо вернуть «No Successor».
Осталось только оценить, насколько долго будет работать наша программа при наихудших условиях, чтобы не перескочить через лимит времени в 3 секунды. Предположим, что N — это количество символов во входящей последовательности. При наихудших условиях на первом шаге программа должна будет выполнить N сравнений (все элементы расположены в порядке возрастания). На втором шаге ведется поиск минимального — это еще N сравнений. На третьем и четвертом шагах мы меняем N элементов местами, что потребует N операций чтения/записи в массив. В итоге получаем 2N сравнений и N перезаписей. При условии, что N не больше 50 (условие задачи) работа нашего алгоритма займет считанные миллисекунды.
Что же, идем сдавать. Моё решение на C++ можно скачать тут.
Accеpted (0.008). Удачи и вам!
