c++ - 使用 vector 解决 Josephus 问题

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() 时，此调用不安全。