使用向量解决 Josephus 问题
Solving the Josephus Problem using a vector
编辑:我似乎至少已经解决了错误,并更新了代码。然而,数学似乎仍然没有解决。有什么想法吗?
简而言之,我正在尝试用 C++ 编写一个程序,它会提示用户输入初始圈子中的人数,然后告诉他们如果 k(被处决前统计到的人数)= 3.
我有我认为正确的想法,但如果我输入 k 和其他任何东西一样,我会得到错误 "Debug Assertion Failed" 和 "Expression: vector erase iterator outside range"大于 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;
}
您只需检查 if (idx > circle.size())
,然后继续调用 circle.erase (circle.begin()+(idx));
。 idx == circle.size()
.
时此调用不安全
@Pradhan 已经为您提供了原始错误的解决方案(idx >= circle.size()
而不是 idx >= circle.size()
。
为什么结果仍然不正确:
当你擦除一个元素时,你必须调整你的索引来补偿它(减去 1)。否则索引对应于向量中的下一个元素,因此实际上你总是每 4 个人执行一次,而不是每 3 个人执行一次。
这是我的代码版本:
#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));
}
编辑:我似乎至少已经解决了错误,并更新了代码。然而,数学似乎仍然没有解决。有什么想法吗?
简而言之,我正在尝试用 C++ 编写一个程序,它会提示用户输入初始圈子中的人数,然后告诉他们如果 k(被处决前统计到的人数)= 3.
我有我认为正确的想法,但如果我输入 k 和其他任何东西一样,我会得到错误 "Debug Assertion Failed" 和 "Expression: vector erase iterator outside range"大于 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;
}
您只需检查 if (idx > circle.size())
,然后继续调用 circle.erase (circle.begin()+(idx));
。 idx == circle.size()
.
@Pradhan 已经为您提供了原始错误的解决方案(idx >= circle.size()
而不是 idx >= circle.size()
。
为什么结果仍然不正确:
当你擦除一个元素时,你必须调整你的索引来补偿它(减去 1)。否则索引对应于向量中的下一个元素,因此实际上你总是每 4 个人执行一次,而不是每 3 个人执行一次。
这是我的代码版本:
#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));
}