Hardcore
08-10-2010, 15:18
Задача Иосифа Флавия или считалка Джозефуса — известная математическая задача с историческим подтекстом.
Задача в своей основе имеет легенду. Отряд из 41-го сикария, защищавший галилейскую крепость Массада, не пожелал сдаваться в плен блокировавшим его превосходящим силам римлян. Сикарии стали в круг и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. Самоубийство — тяжкий грех, но тот, кто в конце концов останется последним, должен будет его совершить. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно стать ему и его другу, чтобы остаться последними. Но не для того, чтобы убить друг-друга, а чтобы сдать крепость римлянам. В современной формулировке задачи участвует n воинов и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который должен будет остаться последним.
К примеру Если есть10 людей то выживает только 4-ый.
Как можно написать алгаритм?
Задача в своей основе имеет легенду. Отряд из 41-го сикария, защищавший галилейскую крепость Массада, не пожелал сдаваться в плен блокировавшим его превосходящим силам римлян. Сикарии стали в круг и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. Самоубийство — тяжкий грех, но тот, кто в конце концов останется последним, должен будет его совершить. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно стать ему и его другу, чтобы остаться последними. Но не для того, чтобы убить друг-друга, а чтобы сдать крепость римлянам. В современной формулировке задачи участвует n воинов и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который должен будет остаться последним.
К примеру Если есть10 людей то выживает только 4-ый.
Как можно написать алгаритм?