Разбор задачи "Число в последовательности"
Запись от diagon размещена 10.03.2012 в 10:23
Показов 59954
Комментарии 3
|
Пока не знаю, какая польза мне будет от этого мини-блога, но все-же попробую его завести. Изредка буду постить сюда разборы каких-либо олимпиадных задач, либо что-нибудь еще. Для начала хочу выложить разбор понравившейся мне задачи с acmp.ru "Число в последовательности". Ссылка на задачу - http://acmp.ru/index.asp?main=task&id_task=464 Условие:
Решать будем с помощью рекурсии. Сразу замечу, что индекс первого члена последовательности будем считать равным единице. Для начала заметим, что последовательность можно разбить на уровни: 0) 0 1) 01 2) 0112 3) 01121220 Рассмотрим 3 уровень: 0112|1220 Допустим, мы хотим найти седьмое число в последовательности. Заметим, что можно найти третье число в последовательности и увеличить его, так как седьмое число является увеличенным третьим. А вместо третьего числа можно найти первое, которое уже известно. Это и есть основная идея решения. Теперь к деталям. Допустим, мы знаем текущий уровень последовательности(для седьмого и восьмого числа этот уровень равен 3, для девятого - 4). Для того, чтобы найти число с индексом n, нам нужно найти индекс числа, из которого это число было образовано. В случае с n=7, этот индекс будет равен 3. Осталось решить вопрос, как найти этот индекс для общего случая. Мы имеем последовательность длиной length. Разобьем эту последовательность на 2 равные части. Для примера можно взять 3 уровень последовательности - 0112|1220. Число с индексом n находится в правой части последовательности, число, индекс которого нужно найти - в левой. Несложно заметить, что индекс будет равен (n - length / 2). Теперь найдем длину последовательности. Очевидно, она равна 2^level, где level - уровень последовательности. Осталось разобраться с уровнем последовательности. Его можно найти через логарифм по основанию 2. К сожалению, в c++ нету стандартной функции log2, однако ее можно написать самостоятельно:
Итак, исходный код нашей рекурсивной функции.
| |||||||||||
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 3
Комментарии
-
Залез по ссылке. Условия задачи не увидел (может для этогорегистрация нужна). Таких приколов всё равно не понимаю. Условие задачи состоит из одного абзаца (скорее всего). Какая проблема закатать текст задачи в блог и не напрягать людей хождением по другим сайтам (где ещё ргеистрация требуется, сайт может в дауне быть, а то и вообще там задачу похерят)?Запись от Evg размещена 12.03.2012 в 14:26 
-
Да, извиняюсь, ссылку кривую привел, уже поправил.
Ну, регистрации для чтения условия там не требуется, да и лично мне удобнее смотреть условие сразу на acmp.ru, однако все же добавил его в пост. Просто потому, что лично мне стало лень тыкать на ссылки из-за редиректа. Возможно, я не один такой.Запись от diagon размещена 14.03.2012 в 18:22
-
В условие задачи надо включить ограничение по времени и памяти (что критично, ибо влияет на выбор алгоритма решения).
Запись от Evg размещена 14.03.2012 в 21:09
