Задача Иосифа Флавия: различия между версиями

11 байт добавлено ,  1 месяц назад
м
→‎Пример: орфография
м (→‎История: орфография, пунктуация)
м (→‎Пример: орфография)
 
| [[Файл:Program1.GIF|400]]
|-
! Рис 1. Круг из 10-ти солдат, в котором
|-
! должен «умереть» каждый второй
! Рис. 5 — 1-й этап при количестве солдат в круге 2n
|}
Наблюдается аналогичная ситуация и при 2n- − 1 — солдатах на входе (рис.6). Однако вводится поправка- уменьшение на единицу и увеличение F(n) в 2 раза.
 
{| class="wikitable"
|}
 
Из чего можно вывести формулу F(2n) = 2* F(n)  1 (для всех n > 1).
Рассмотрим случай № 2, приняв во внимание тот факт, что на вход подаются 2n + 1 число солдат (то есть нечетное количество солдат). После проведения 1-го этапа «исключения» солдат из круга получится нечто, приведенное на рис.7.
{| class="wikitable"
! Рис. 7 — 1-й этап при количестве солдат в круге 2n + 1
|}
Из чего можно вывести формулу F(2n +1) = 2* F(n) + 1 (для всех n > 1).
Сведем все рассмотренные ситуации и запишем все случаи в виде системы, позволяющей определить значение функции F(n) — для любых значений n:
{| class="wikitable"
Выведенные выше формулы могут быть применены и для решения исходной задачи — Иосифа Флавия.
А именно:
F(2^<sup>m</sup> + k) = 2k + 1; для любого m любого k.
 
=== Представление решения для случая убийства каждого 2-го через двоичную запись ===