понедельник, 3 июня 2013 г.

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

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


Решение (Перебором):


#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;  //Выводим оставшийся
}