рекуррентный рекуррентный

Сначала я напомню проблему Иосифа Флавия.

У нас в кругу собралось n человек. Палач будет обрабатывать круг следующим образом:

1. Палач начинает с человека на позиции i = 1
2. Находясь в позиции i, он щадит i, но убивает человека, следующего за i
3. Он выполняет это до тех пор, пока в живых не останется только один человек.

Быстро взглянув на эту процедуру, мы можем увидеть, что каждый человек в ровном положении будет убит в первом проходе. Когда все «четные» мертвы, кто оставшиеся люди? Ну, это зависит от четности n.

Если n четно (скажем, n = 2i), то оставшихся людей 1,3,5,...,2i-1. Оставшаяся проблема — это круг из i человек вместо n. Давайте введем отображение map_even между позицией в «новом» круге и исходной позицией в кругу из n человек.

карта_четный(x) = 2.x - 1

Это означает, что человек на позиции x в новом круге был на позиции 2.x - 1 в исходном. Если положение выжившего в новом круге равно J(i), то положение, которое должен занять кто-то, чтобы выжить в кругу из n = 2.i человек, равно

map_четный(J(i)) = 2.J(i) - 1

У нас есть первое правило рекурсии:

Для любого целого числа n :
J(2.n) = 2.J(n) - 1

Но если n нечетно (n = 2.j + 1), то первый запуск заканчивается убийством всех «четных», а палач находится на позиции n. n последователей равно 1 ... Таким образом, следующим будет убит 1. Выживших 3,5,..,2j+1 и палач действует так, как если бы у нас был круг из j человек. Отображение немного отличается от четного случая:

карта_{нечетная}(x) = 2.x + 1

3 — это новая 1, 5 — это новая 2 и так далее…

Если позиция выжившего в кругу из j человек равна J(j), то человек, который хочет выжить в кругу из n = 2j+1, должен занять позицию J(2j+1):

J(2j+1) = map_{нечетное}(J(j)) = 2.J(j) + 1

Нарисовано второе рекурсивное отношение:

Для любого целого числа n имеем:
J(2.n + 1) = 2.J(n) + 1

Теперь мы можем вычислять J(n) для ЛЮБОГО целого числа n, используя 2 рекурсивных соотношения. Но если мы посмотрим немного дальше, мы можем сделать это лучше...

Как следствие, для каждого n = 2^k мы имеем J(n) = 1. Хорошо, но для других чисел? Если вы запишете первые результаты (скажем, до n = 20), вы увидите, что последовательность кажется псевдопериодической:
1 2 3 4 5 6 7 8 9 10 11
1 1 3 1 3 5 7 1 3 5 7

Начиная со степени двойки, кажется, что позиция увеличивается на 2 на каждом шаге до следующей степени двойки, где мы снова начинаем с 1... Поскольку для заданного целого числа n существует единственное целое число m(n), такое что

2^m(n) ≤ n ‹ 2^m(n)+1

Пусть s(n) будет целым числом, таким что n = 2^m(n) + s(n) (я называю это "s" для "сдвига"). Математический перевод нашего наблюдения состоит в том, что J(n) = 1 + 2.s(n)

Докажем это с помощью сильной индукции.
При n = 1 имеем J(1) = 1 = 1 + 2.0 = 1 + 2.s(1)
При n = 2 имеем J(2) = 1 = 1 + 2,0 = 1 + 2.s(2)

Предполагая J(k) = 1 + 2.s(k) для любого k такого, что k ∈ [1,n], докажем, что J(n+1) = 1 + 2.s(n+1).

Имеем n = 2^m(n+1) + s(n+1). Очевидно, что 2^m(n) четно (за исключением тривиального случая, когда n = 1), поэтому четность n передается s(n).

Если s(n+1) четно, то мы обозначаем s(n+1) = 2j. У нас есть

J(n+1) = 2.J((n+1)/2) - 1 = 2.J(2^m(n+1)-1 + j) - 1

Поскольку утверждение верно для любого k ∈ [1,n], оно верно для 1 ≤ k = (n+1)/2 ‹ n и, таким образом:

J(n+1) = 2.(2j + 1) - 1 = 2.s(n+1) + 1

Точно так же мы можем решить нечетный случай. Формула установлена ​​для любого целого числа n:

J(n) = 2.s(n) + 1, где m(n), s(n) ∈ ℕ — уникальные целые числа такие, что
2^m(n) ≤ n ‹ 2 ^m(n)+1 и s(n) = n - 2^m(n)
Другими словами: m(n) = ⌊ln ₂(n)⌋ и s(n) = n - 2^{⌊ln₂(n)⌋}

Начните с нескольких простых примеров, сделайте предположение, а затем используйте индукцию, чтобы (опровергнуть) ваше предположение.

Рассмотрим n = некоторая степень числа 2.

J (2 ^ 0) = 1 (дано)

J(2^1) = 2J(2^0) - 1 = 1

J(2^2) = 2J(2^1) - 1 = 1

Хорошо, предположим, что J(n) = 1 для всех n >= 1.

Базовый случай: J(1) = 1, что верно по определению.

Индуктивный шаг: предположим, что J(k) = 1 для некоторого произвольного k. Тогда J(2k) = 2J(k) - 1 = 1.

Следовательно, по индукции J (n) = 1 для всех n (при условии, что деление округляется до целых чисел).

J(n)=2*J(n/2)-1

J(n)-1=2*J(n/2)-2

J(n)-1=2*(J(n/2)-1)

T(n)=2*T(n/2), где T(n)=J(n)-1

T(n)=2^log2(n)*T(1)

J(n)=2^log2(n)*(J(1)-1)+1