Задача Иосифа с++ с помощью циклического связного списка проблема со связью во 2 очереди?

Question

[Alon Mix]

Проблема возникает во 2 очереди. К примеру войнов 10, интервал 2 и после 9 война идет 1(что неправильно)

#include <iostream>
using namespace std;
 
struct Node
{
    int m_item;
    Node *m_next;
    Node(int item, Node *next) { m_item = item, m_next = next; }
};
 
int main()
{
    cout << "Voin: "; 
    int NumberOfElements = 0;
    cin >> NumberOfElements; 
    cout << "M: "; //  интервал
    int interval;
    cin >> interval; // ввод интервала
    Node *first = new Node(1, 0);
    first->m_next = first;
    Node *tmp = first;
    cout << "Deleted elements:" << endl;
    for (int i = 2; i <= NumberOfElements; ++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;
 
        cout << tmp->m_item << endl;
        delete deleteNode;
    }
    cout << "Last warrior:" << tmp->m_item << endl;
}

Answer 1

[Wataru]

Надо же выводить удаляемый элемент, да? Вы же выводите предыдущий. Ну и, раз первый всегда удаляется в начале, надо перед вашим циклом его вручную удалить. Может быть проще, если вы сделаете двусвязный список и напишите функцию, которая удаляет элемент и возвращает следующий. Лучше будет использовать цикл do while в решении - удаляете элемент и сдвигаетесь. Потом проверка на сколько осталось элементов... Ну или for можно использовать - вы же знаете, сколько удалений будет из n войнов.

Comments

[Alon Mix]

проблема в том, что нужно односвязный циклический сделать

[Wataru]

Alon Mix, Можно и с односвязным, но тогда вам надо поддерживать 2 указателя - текущий и предыдущий элементы. Удобно будет сделать 2 функции - перейти к следующему элементу и удалить текущий и перейти к следующему. Вторая функция не сдвигает предыдущий указатель.