Условие
Задача Иосифа Флавия
Существует легенда, что Иосиф Флавий - известный историк первого
века - выжил и стал известным благодаря математической одаренности.
В ходе иудейской войны он в составе отряда из 41 иудейского воина
был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили
выстроиться в круг и последовательно убивать каждого третьего из
живых до тех пор, пока не останется ни одного человека.
Однако Иосиф наряду с одним из своих единомышленников счел подобный
конец бессмысленным - он быстро вычислил спасительные места
в порочном круге, на которые поставил себя и своего товарища.
И лишь поэтому мы знаем его историю.
В нашем варианте мы начнем с того,
что выстроим в круг N человек, пронумерованных числами от 1 до N,
и будем исключать каждого k-ого до тех пор, пока не уцелеет только
один человек. (Например, если N=10, k=3, то сначала умрет 3-й,
потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й,
за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)
Задача: определить номер уцелевшего.
Входные данные: числа N и k вводятся из файла INPUT.TXT.
Ограничения: 1<=N<=500, 1<=k<=100.
Выходные данные: Программа должна выдавать номер уцелевшего человека
в файл OUTPUT.TXT.
Пример входного файла:
10 3
Пример выходного файла:
4
Подсказка
Задача Иосифа Флавия очень богата на идеи.
Предполагается, что школьники будут решать ее, моделируя процесс. При этом
есть два подхода: завести массив, где помечать, жив человек или нет.
Бегать по кругу и считать живых. Второй подход: завести массив с номерами
живых людей, и при убивании человека удалять из него человека. При каждом
из подходов, задача является довольно сложной и требует аккуратной
реализации.
Решение
Скачать архив тестов
Источники и прецеденты использования
|
|
|
Курс |
|
предмет |
информатика |
|
Название |
Основы программирования на языке Паскаль |
|
Класс |
8 |
|
Автор |
Матюхин Виктор Александрович |
|
Место проведения |
Московская гимназия на Юго-Западе N1543 |
|
задача |
|
Номер |
131 |
