Решение проблемы Иосифа с помощью вектора

Question

РЕДАКТИРОВАТЬ: Я, кажется, разобрался с ошибками, по крайней мере, и обновил код. Тем не менее, математика все еще не работает. Есть идеи?

Короче говоря, я пытаюсь написать программу на C++, которая будет запрашивать у пользователя количество людей в начальном круге, а затем сообщать им, в каком положении они должны стоять, чтобы выжить, если k (число людей, которых считали перед исполнением) = 3.

У меня есть то, что я считаю правильной идеей, но я получаю сообщение об ошибке "Ошибка отладки утверждения" и "Выражение: итератор стирания вектора вне диапазона", если я ввожу k как что-либо отличное от 1, 2 или 5.

// ConsoleApplication2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    int n;//size of the circle
    vector <int> circle; //the circle itself

    //ask for how many people are in the circle
    cin >> n;

    //fill the circle with 1,2,3...n
    for (int idx = 0; idx < n; idx++)
    {
        circle.push_back (idx+1);
    }


    //cout << "The size of the circle is " << circle.size() << ".\nThe highest number is " << circle[n-1] << "."; //test to make sure numbers are being assigned properly to each vector element


    for (int count = 0, idx = 0; circle.size() > 1; idx++,count++)
    {
        //if the position (idx) is greater than the size of the circle, go back to the beginning of the circle and start counting again
        if (idx >= circle.size())
        {
            idx = 0;
        }

        //every time the counter reaches three, that person is executed
        if (count == 3)
        {
            circle.erase (circle.begin()+(idx));
            count = 0;
        }
    }

    cout << "The place to stand to win the hand is position #" << circle.front() << ".\n";

    return 0;
}

Answer 1

Вы проверяете только if (idx > circle.size()) а затем идти вперед и позвонить circle.erase (circle.begin()+(idx));, Этот звонок не является безопасным, когда idx == circle.size(),

Answer 2

@Pradhan уже дал вам решение вашей первоначальной ошибки (idx >= circle.size() вместо idx >= circle.size(),

Почему результат все еще не верен:
Когда вы стираете элемент, вы должны откорректировать свой индекс, чтобы компенсировать его (вычтите 1). В противном случае индекс соответствует следующему элементу в векторе, поэтому фактически вы всегда выполняете каждого четвертого человека, а не каждого третьего.

Вот моя версия кода:

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main(){         
    int n;
    cin >> n;

    //fill the circle with 1,2,3...n
    vector <int> circle(n);
    std::iota(std::begin(circle), std::end(circle),1);

    int idx = -1;
    while (circle.size() > 1) {
        //advance by threee
        idx = (idx + 3) % circle.size();

        //execute Person 
        circle.erase(circle.begin() + (idx));

        //readjust to compensate for missing element
        --idx;
    }
    cout << "The place to stand to win the hand is position #" << circle.front() << ".\n";
}

Конечно, вы можете переписать цикл

    int idx = 0;
    while (circle.size() > 1) {
        //advance by three
        idx = (idx + 2) % circle.size();

        //execute Person 
        circle.erase(circle.begin() + (idx));           
    }