Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
1.3 ЗАДАЧА ИОСИФА ФЛАВИЯПоследний из наших предварительных примеров представляет собой один из вариантов античной задачи, носящей имя Иосифа Флавия — известного историка первого века. Существует легенда, что Иосиф выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф, наряду с одним из своих единомышленников, счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. В нашем варианте мы начнем с того, что выстроим в круг только один человек. Вот, к примеру, исходное расположение при
Порядок исключения Мы только что выяснили, что
Придется вернуться к табличке и попробовать сделать лучшее предположение. Итак, допустим, что первоначально имеется
и следующий проход будет начинаться с номера 3. Это все равно, как если бы мы начинали с
Теперь можно быстро продвигаться к большим
Аналогично, Ну, а как насчет нечетного случая? Оказывается, что в случае
Опять получили почти первоначальную ситуацию с
Объединение этих уравнений с
Вместо получения Наше рекуррентное соотношение дает возможность очень быстро составить таблицу первых значений
Вот
(Заметим, что если Теперь надо доказать (1.9). Как и прежде, мы будем использовать индукцию, но на этот раз — индукцию по
на основании (1.8) и индуктивного предположения; это как раз то, что нам надо. Аналогичное доказательство проходит и в нечетном случае, когда
В любом случае индукция выполнена и справедливость (1.9) установлена. С целью иллюстрации решения (1.9), вычислим Теперь, когда самое трудное позади (решена задача), осмотримся немного: решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач. Раз уж нами освоена некая техника, поучительно присмотреться к ней повнимательнее и выяснить, что еще можно получить с ее помощью. Поэтому в оставшейся части данного раздела мы изучим решение (1.9) и исследуем некоторые обобщения рекуррентного соотношения (1.8). Эти исследования выявят определенную структуру, которая лежит в основе всех таких задач. Степени 2 играли важную роль в нашем поиске решения, так что естественно обратиться к двоичным представлениям величин
т. е.
где каждое
(Последнее следует из того, что
т. е., на программистском жаргоне, Если мы начинаем Многократное применение
аналогично,
Странно, но факт. Давайте ненадолго вернемся к нашему первоначальному предположению, что
Если число решений уравнения
Обратите внимание на крайний правый столбец. Это двоичные числа, циклический сдвиг которых на одну позицию влево дает тот же самый результат, что и обычный сдвиг на одну позицию вправо (деление пополам). Отлично, мы достаточно основательно разобрались с функцией
(В нашем первоначальном рекуррентном соотношении было
Похоже, что коэффициенты при
разделяя зависимость от
Здесь, как обычно, Нельзя сказать, что так уж трудно доказать (1.13) и (1.14) по индукции, но подобные действия бестолковы и малоценны. К счастью, существует лучший способ действия, если выбрать отдельные значения и затем скомбинировать их. Продемонстрируем этот способ на примере частного случая
Достаточно ясно (доказывается индукцией по Затем воспользуемся рекуррентным соотношением (1.11) и решением (1.13) в обратном порядке, начав с простой функции
следовательно, значения
Эти уравнения справедливы при всех И теперь, в сущности, блюдо готово! Мы показали, что функции
Наши предположения, сделанные в (1.14), подтверждаются немедленно, поскольку мы можем решить эти уравнения, получая Изложенный подход иллюстрирует исключительно полезный репертуарный метод решения рекуррентных уравнений. Сначала мы подбираем величины общих параметров, для которых мы знаем решение, — это обеспечивает нас репертуаром разрешимых частных решений. Затем, комбинируя частные решения, мы получаем общее решение. При этом необходимо столько независимых частных решений, сколько имеется независимых параметров (в нашем случае их было три — для Мы знаем, что первоначальная
А допускает ли обобщенная Конечно, почему же нет? Обобщенную рекуррентность (1.11) можно переписать как
если положить
Предположим, что теперь мы расширили систему счисления с основанием 2, так что в ней допустимы произвольные цифры, а не только 0 и 1. Предыдущий вывод означает, что
Чудесно. Мы смогли бы заметить это обстоятельство гораздо раньше, если бы составили табл. (1.12) в ином виде:
Например, при
как и прежде. Свойство циклического сдвига сохраняется, поскольку каждый набор двоичных цифр
Итак, изменение системы счисления привело нас к компактному решению (1.16) обобщенной рекуррентности (1.15). Если нам, право, неймется — можно обобщить ее еще больше. Рекуррентность
совпадает с предыдущей за одним исключением: мы начинаем с чисел по основанию
Предположим, к примеру, что вследствие некоторого благоприятного стечения обстоятельств нами получено рекуррентное соотношение
и, допустим, мы хотим вычислить
Итак, Иосиф и иудейская война привели нас к довольно интересным обобщенным возвратным соотношениям.
|
1 |
Оглавление
|