с++ / Задача Иосифа Флавия

Задача Иосифа (циклический список)

Описание задачи:
http://ru.wikipedia.org/wiki/Задача Иосифа


Решение (Перебором от http://cppalgorithms.blogspot.ru ) :

#include <iostream>
using namespace std;

class Node   //Узел связного списка
{
public:
int m_item;
Node *m_next;

Node(int item, Node *next){m_item = item, m_next = next;}
};

int main()
{
cout << "Enter number of people: ";
int numberOfPeople = 0;
cin >> numberOfPeople;

cout << "Enter interval: ";
int interval;
cin >> interval;

Node *first =new Node(1, 0); //Создаем первый узел. m_item содержит номер
first->m_next = first;       //и зацикливаем его на себя

Node *tmp = first;  //Указатель с которым будем работать в дальнейшем

for (int i = 2; i <= numberOfPeople; ++i)  //Создаем циклический список
{
tmp->m_next = new Node(i, first);
tmp = tmp->m_next;
}
while (tmp != tmp->m_next)    //Удаляем элемент через интервал
{
for (int i = 1; i < interval; ++i)
{
tmp = tmp->m_next;
}
Node *deleteNode = tmp->m_next;
tmp->m_next = tmp->m_next->m_next;

delete deleteNode;
}

cout << tmp->m_item << endl;  //Выводим оставшийся
}

/////////////////////////////////////////////////

Простая рекурсивная реализация (в 1-индексации):

int joseph (int n, int k) {
 return n>1 ? (joseph (n-1, k) + k - 1) % n + 1 : 1;
}

Нерекурсивная форма:

int joseph (int n, int k) {
 int res = 0;
 for (int i=1; i<=n; ++i)
  res = (res + k) % i;
 return res + 1;
}