Решение задачи Джозефуса с помощью циклического массива

• Номер работы:
  140279
• Раздел:
  Все работы   →   Курсовые проекты - сложные   →   Информатика, Вычислительная техника, телекоммуникации
• Год подготовки:
  04.01.2010
• Куда сдавалась:
  Орловский Государственный Технический Университет
• Объем работы:
  30 стр.
• Содержание:
  Введение
  Постановка задачи
  Рекуррентные соотношения
  Замкнутая формула
  Переборное решение
  Способ первый
  Способ второй
  Пример
  Решение на основе двоичного представления n
  Реализации
  Реализация на языке С++
  Реализация на Java
  Обоснование выбора метода решения задачи
  Описание пользовательского интерфейса
  Описание результатов работы программы
  Сравнительный анализ алгоритмов
  Заключение
  Список использованной литературы
  Приложение А
  
• Выдержка из работы:
  Введение
  Темой курсового проекта является достаточно известная математическая задача, имеющая исторический подтекст. Другими словами эта задача называется задачей Иосифа Флавия или считалкой Джозефуса.
  Идея задачи имеет легендарные корни. Галилейскую крепость Массада защищал отряд из сорока одного сикария. Отряд был блокирован и окружен превосходящими силами римлян, но не пожелал сдаваться в плен.
  Воины - сикарии стали в круг и договорились о том, что каждые два воина будут убивать третьего. И так до тех пор, пока не погибнут все. Последний воин должен был совершить самоубийство, несмотря на то, что это является тяжким грехом. Но тот, кто, в конце концов, останется последним, должен будет совершить самоубийство.
  Отрядом сикариев командовал Иосиф Флавий. Согласно легенды он быстро рассчитал, где нужно стать ему и его другу, чтобы остаться последними живыми в этой цепочке. Правда, не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам.
  В настоящее время эта задача формулируется следующим образом: имеется отряд из n воинов и убивают каждого m-го. Требуется определить такой номер k начальной позиции воина, который должен будет остаться последним.
  Существует множество реализаций этого алгоритма на различных языках программирования. Алгоритм решения задачи обоснован математическими методами.
  Ниже будут рассмотрены некоторые методы решения задачи Джозефуса и проведен сравнительный анализ реализаций возможных решений.
  
  Постановка задачи
  Древняя легендарная постановка задачи:
  Существует отряд из n воинов где убивают каждого m-го. Требуется определить такой номер k начальной позиции воина, который должен будет остаться последним.
  Современная математическая постановка задачи:
  Имеется массив из n элементов, удаляется каждый m-й элемент массива. Необходимо определить такой номер k элемента массива, который после удаления каждого m-го останется последним.
  Рассмотрим некоторые математические соотношения, необходимые для решения этой задачи.
  
  Рекуррентные соотношения
  Как следует из постановки задачи, необходимо определить номер k в последовательности из n членов, удаляя каждый m-й член последовательности, пока не останется один.
  В том случае, если известно решение задачи для некоторого числа членов последовательности , то его можно использовать для решения задачи с на единицу большим числом членов последовательности. Для m = 2 имеем
  
  .
  Для m = 3 имеем:
  ..............................
  Список использованной литературы
  1. М. А. Алексеев Задача Иосифа Флавия // Империя Математики. — 2001. — № 2. — С. 22—28.
  2. Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7
  
  ..............................