В информатике и математике , то проблема Флавия (или Флавий перестановка ) теоретическая проблема , связанная с определенной считалкой .
Люди стоят в кругу и ждут казни. Подсчет начинается в указанной точке круга и продолжается по кругу в указанном направлении. После того, как указанное количество людей пропущено, выполняется следующий человек. Процедура повторяется с оставшимися людьми, начиная со следующего человека, идя в том же направлении и пропуская такое же количество людей, пока не останется только один человек, и его освободят.
Проблема - учитывая количество людей, начальную точку, направление и количество, которое нужно пропустить - состоит в том, чтобы выбрать позицию в начальном круге, чтобы избежать казни.
История
Проблема названа в честь Флавия Иосифа , еврейского историка, жившего в I веке. Согласно рассказу Иосифа Флавия об осаде Йодфата , он и его 40 солдат были пойманы в пещере римскими солдатами . Они предпочли самоубийство поимке и остановились на серийном методе совершения самоубийства путем жеребьевки. Иосиф заявляет, что по счастливой случайности или, возможно, благодаря руке Бога, он и еще один человек оставались до конца и сдались римлянам, а не покончили с собой. Это история, приведенная в книге 3, главе 8, части 7 книги Иосифа Флавия « Иудейская война» ( пишет о себе от третьего лица ):
Однако в этом крайнем бедственном положении он не лишился своей обычной проницательности; но, доверившись провидению Божьему, он подверг свою жизнь опасности [следующим образом]: «А теперь, - сказал он, - раз уж между вами решено, что вы умрете, давайте, давайте совершим наши взаимные действия». смерть к определению по жребию. Тот, кому выпадает жребий первым, пусть будет убит тем, у кого есть второй жребий, и таким образом удача будет распространяться через всех нас; и никто из нас не погибнет от своей собственной правой руки, ибо было бы несправедливо, если бы, когда остальные ушли, кто-то покаялся и спасся ». Это предложение показалось им очень справедливым; и когда он уговорил их определить это дело по жребию, он вытянул один из жребий и для себя. Тот, у кого был первый жребий, обнажил шею тому, у кого был следующий, предполагая, что генерал умрет среди них немедленно; ибо они думали, что смерть, если Иосиф мог умереть с ними, слаще жизни; тем не менее, он остался с другим напоследок, должны ли мы сказать, что это произошло случайно, или по провидению Божьему. И так как он очень не желал, чтобы его осудила жребий, или, если бы он был оставлен до последнего, пропитать свою правую руку кровью своих соотечественников, он убедил его поверить в свою верность ему и остаться в живых. как и он сам.
- Иосиф Флавий , стр. 579, Войны евреев, Книга III, гл. 8, абз.7
Детали механизма, использованного в этом подвиге, довольно расплывчаты. Согласно Джеймсу Дауди и Майклу Мэйсу, [2] в 1612 году Клод Гаспар Баше де Мезириак предложил особый механизм расстановки людей по кругу и подсчета по тройкам для определения порядка исключения. [3] Эта история часто повторяется, и конкретные детали значительно различаются от источника к источнику. Например, у Исраэля Натана Герштейна и Ирвинга Каплански (1974) Иосиф и 39 товарищей стоят в кругу, а каждый седьмой исключен. [4] История проблемы можно найти в SL Зэбелл в письме к редактору по Фибоначчи Quarterly . [5]
У Иосифа был сообщник; тогда проблема заключалась в том, чтобы найти места двух последних оставшихся в живых (чей заговор обеспечил их выживание). Утверждается, что он поставил себя и другого мужчину на 31-е и 16-е места соответственно (для k = 3 ниже). [6]
Варианты и обобщения
Средневековая версия проблемы Иосифа включает 15 турок и 15 христиан на борту корабля в шторм, который затонет, если половина пассажиров не будет выброшена за борт. Все 30 стоят в кругу, и каждого девятого бросить в море. Христианам нужно определиться, где им стоять, чтобы бросить только турок. [7] В других версиях роли турок и христиан меняются местами.
Грэхем, Кнут и Паташник 1989 , стр. 8 опишите и изучите «стандартный» вариант: определите, где стоит последний выживший, если есть n человек, чтобы начать, и каждый второй человек ( k = 2 ниже) выбывает.
Обобщение этой проблемы состоит в следующем. Предполагается, что каждый m- й человек будет казнен из группы размера n , в которой p- й человек является оставшимся в живых. Если в круг добавлено x человек, то оставшийся в живых находится в p + mx -й позиции, если это меньше или равно n + x . Если x - наименьшее значение, для которого ( p + mx )> ( n + x ) , то оставшийся в живых находится в позиции ( p + mx ) - ( n + x ) . [8]
Решение
В следующих, обозначает количество людей в начальном круге, а обозначает счет для каждого шага, то есть люди пропускаются и -го выполнено. Люди в круге пронумерованы от к , исходное положение и подсчет является инклюзивным .
k = 2
Проблема решается явно, когда будет убит каждый второй человек, т.е. . (В более общем случае, решение описано ниже.) Решение выражается рекурсивно. Позволять обозначают положение выжившего, когда изначально люди (и ). В первый раз по кругу все четные люди умирают. Во второй раз по кругу умирает новый 2-й человек, затем новый 4-й и т. Д .; это как если бы не было первого раза по кругу.
Если исходное количество людей было четным, то человек, занимающий позицию во второй раз по кругу был изначально на позиции (для каждого выбора ). Позволять. Человек в Кто теперь выживет, изначально занимал позицию . Это дает повторение
Если первоначальное количество людей было нечетным, то можно представить, что человек 1 умирает в конце первого раза по кругу. Опять же, во второй раз по кругу умирает новый 2-й человек, затем новый 4-й и т. Д. В этом случае человек в позиции изначально был на позиции . Это дает повторение
Когда значения сведены в таблицу а также возникает закономерность: OEIS : A006257
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |
1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
Это говорит о том, что - возрастающая нечетная последовательность, которая перезапускается с всякий раз, когда индекс n является степенью 2. Следовательно, если m и l выбраны так, что а также , тогда . Понятно, что значения в таблице удовлетворяют этому уравнению. Или можно подумать, что после люди мертвы есть только люди, и это идет в й человек. Этот человек должен быть оставшимся в живых. Так. Ниже приводится доказательство по индукции.
Теорема: если а также , тогда .
Доказательство: сильная индукция используется на. Базовый случайправда. Отдельно рассматриваются случаи, когда даже и когда странно.
Если четно, тогда выберите а также такой, что а также . Обратите внимание, что. где второе равенство следует из предположения индукции.
Если нечетно, тогда выберите а также такой, что а также . Обратите внимание, что. где второе равенство следует из предположения индукции. Это завершает доказательство.
можно решить, чтобы получить явное выражение для :
Самая элегантная форма ответа включает двоичное представление размера. : может быть получен однобитным циклическим сдвигом влево сам. Если представлен в двоичном виде как , то решение дается формулой . Доказательство этого следует из представления в виде или из приведенного выше выражения для .
Реализация: если n обозначает количество людей, безопасное положение задается функцией, где а также .
Теперь, если число представлено в двоичном формате, первый бит обозначает а остальные биты будут обозначать . Например, когда n = 41, его двоичное представление будет
п = 1 0 1 0 0 1
2 м = 1 0 0 0 0 0
л = 0 1 0 0 1
/ ** * * @param n количество людей, стоящих в круге * @ вернуть безопасную позицию, которая переживет казнь * f (N) = 2L + 1, где N = 2 ^ M + L и 0 <= L < 2 ^ M * / public int getSafePosition ( int n ) { // найти значение L для уравнения int valueOfL = n - Integer . highOneBit ( n ); int safePosition = 2 * значениеOfL + 1 ;return safePosition ; }
Побитовое
Самый простой способ найти безопасную позицию - использовать побитовые операторы. В этом подходе сдвиг самого старшего бита набора n в младший бит вернет безопасную позицию. [9] Введите положительное целое число.
п = 1 0 1 0 0 1
п = 0 1 0 0 1 1
/ ** * * @param n (41) количество людей, стоящих в круге * @ вернуть безопасную позицию, которая переживет казнь * ~ Integer.highestOneBit (n * 2) * Умножьте n на 2, получите первый набор bit и возьмите его дополнение * ((n << 1) | 1) * Left Shift n и переверните последний бит * ~ Integer.highestOneBit (n * 2) & ((n << 1) | 1) * Побитовое И до биты копирования существуют в обоих операндах. * / public int getSafePosition ( int n ) { return ~ Integer . highOneBit ( n * 2 ) & (( n << 1 ) | 1 ); }
k = 3
В 1997 году Лоренц Хальбайзен и Норберт Хунгербюлер обнаружили закрытый бланк для дела. . Они показали, что существует некая постоянная
которые могут быть вычислены с произвольной точностью. Учитывая эту константу, выберите быть наибольшим целым таким, что (это будет либо или же ). Тогда последний выживший
- если еще округляется
для всех .
В качестве примера вычислений Хальбайзен и Хунгербюлер приводят (что на самом деле является исходной формулировкой проблемы Иосифа Флавия). Они вычисляют:
- и поэтому
- (обратите внимание, что это округлено в меньшую сторону)
Это можно проверить, посмотрев на каждый последующий проход по числам. через :
Общий случай
Динамическое программирование используется для решения этой проблемы в общем случае, выполняя первый шаг, а затем используя решение оставшейся проблемы. Когда индекс начинается с единицы, то человек в смены от первого лица на позиции , где n - общее количество человек. Позволятьобозначают положение выжившего. После-й человек убит, круг остается, и следующий счет начинается с человека, номер которого в исходной задаче был . Положение выжившего в оставшемся круге будет если подсчет начинается в ; сдвигая это, чтобы учесть тот факт, что отправной точкой являетсядает повторение [10]
который принимает более простой вид
если позиции пронумерованы от к вместо.
У этого подхода есть время работы , но для маленьких и большой есть другой подход. Второй подход также использует динамическое программирование, но имеет время выполнения.. Он основан на рассмотрении убийства k -го, 2-го, k-го , ...,-й человек как на один шаг, потом меняя нумерацию. [ необходима цитата ]
Этот улучшенный подход принимает форму
Рекомендации
Цитаты
- ^ Проблема Иосифа Флавия . Решение задачи Иосифа Флавия в Розеттском коде , написанном на языке Фёрмулу. Вики по Fōrmulæ . Проверено 19 сентября 2019 года.
- ^ Dowdy & Mays 1989 , стр. 125.
- ^ Баш 1612 , стр. 174.
- ^ Херстейн & Капланский 1974 , стр. 121-126.
- ^ Зэбелл 1976 , стр. 48, 51.
- ^ Роуз Болл 1905 , стр. 19.
- ^ Newman 1988 , стр. 2403-2405.
- ↑ Робинсон, 1960 , стр. 47–52.
- ^ «Проблема Иосифа с использованием побитовой операции (Java)» . GitHub . 7 января 2018 . Проверено 7 января 2018 года .
- ↑ Park & Teixeira 2018 , стр. 1-7.
Источники
- Баше, CG (1612). Problemes Plaisants ed Delectables qui se font par les Nombres (на французском языке).
- Graham, RL; Knuth, DE ; Паташник О. (1989). Конкретная математика: фундамент компьютерных наук . Эддисон Уэсли. ISBN 978-0-201-14236-5.
- Herstein, IN; Капланский, И. (1974). Вопросы математические . Харпер и Роу.
- Иосиф Флавий (б. Произведения Флавия Иосифа: в трех томах; с иллюстрациями . Перевод Уильяма Уистона. Лондон: Джордж Рутледж и сыновья.
- Ньюман, младший (1988). Мир математики . 4 . Темпус.
- Пак, Чан Ву; Тейшейра, Рикардо (2018). «Серийная казнь Иосифа Проблема». Корейский J. Math . 26 (1): 1–7. DOI : 10,11568 / kjm.2018.26.1.1 .
- Робинсон, WJ (1960). «Проблема Иосифа Флавия». Математика. Вестник . 44 (347): 47–52. DOI : 10.2307 / 3608532 . JSTOR 3608532 .
- Роуз Болл, WW (1905). Математические развлечения и эссе (2-е изд.). Лондон: Макмиллан.
- Забелл, SL (1976). «Письмо в редакцию» (PDF) . Ежеквартальный отчет Фибоначчи . 14 : 48–51.
дальнейшее чтение
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Глава 14: Расширение структур данных». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. п. 318. ISBN 0-262-03293-7.
- Дауди, Джеймс; Мэйс, Майкл Э. (1989). «Перестановки Иосифа Флавия» . Журнал комбинаторной математики и комбинаторных вычислений . 6 : 125–130.
- Halbeisen, L .; Хунгербюлер, Н. (1997). «Проблема Иосифа» . J. Théor. Nombres Bordeaux . 9 (2): 303–318. DOI : 10,5802 / jtnb.204 .
- Якобчик, Ф. (1973). «Об обобщенной проблеме Иосифа Флавия». Glasow Math. Дж . 14 (2): 168–173. DOI : 10.1017 / S0017089500001919 .
- Ллойд, Эррол Л. (1983). «Алгоритм O (n logm) для проблемы Иосифа Флавия». J. Algor . 4 (3): 262–270. DOI : 10.1016 / 0196-6774 (83) 90025-1 .
- Одлызко, Андрей М .; Уилф, Герберт С. (1991). «Функциональная итерация и проблема Иосифа Флавия». Glasgow Math. Дж . 33 (2): 235–240. DOI : 10.1017 / S0017089500008272 .
- Раски, Фрэнк; Уильямс, Аарон (2010). «Проблема кошачьего Иосифа». Лект. Нет. Комп. Sci . Конспект лекций по информатике. 6099 : 343–354. Bibcode : 2010LNCS.6099..343R . DOI : 10.1007 / 978-3-642-13122-6_33 . ISBN 978-3-642-13121-9. FUN2010
- Раски, Фрэнк; Уильямс, Аарон (2012). «Проблема кошачьего Иосифа». Теория вычисл. Системы . 50 : 20–34. DOI : 10.1007 / s00224-011-9343-6 . S2CID 2273820 .
- Салливан, Шон; Инско, Эрик (2018). «Вариант проблемы Кошачьего Иосифа». arXiv : 1803.11340 [ math.CO ].
- Шамс-Барах, Армин (2002). «Формулировка расширенной проблемы Иосифа Флавия» (PDF) . Архивировано из оригинального (PDF) 30.07.2018.
- Терио, Николя (2001). «Обобщение проблемы Иосифа Флавия». Util. Математика. (58): 161–173.CiteSeer x : 10.1.1.164.2015
- Вудхаус, Дэвид (1973). «Расширенная проблема Иосифа Флавия». Преподобный Мат. Hisp.-амер . 33 (4): 207–218.
Внешние ссылки
- Игра Иосифа Флавия (Java-апплет) в разорванном состоянии, позволяющая выбирать каждого n- го из 50 (максимум).
- Вайсштейн, Эрик В. «Проблема Иосифа» . MathWorld .
- Проблема Иосифа Флавия - Numberphile на YouTube