Question

求高手帮忙解释一下下面的josephus问题程序（C++）：

int main()
{
int i,j,n,m,mPrime, numLeft;
list<int> L;
list<int>::iterator iter;
cout << "enter N(# of people) & M(# of passes before elimination):";
cin >> n >> m;
numLeft = n;
mPrime = m % n;
for( i = 1; i <= n; i++ )
L.push_back(i);
iter = L.begin();
//Pass the potato
for( i = 0; i < n; i++ )
{
mPrime = mPrime % numLeft;
if( mPrime <= numLeft/2 )
for( j = 0; j< mPrime; j++ )
{
iter++;
if( iter == L.end() )
iter = L.begin();
}
else
for( j = 0; j < mPrime; j++ )
{
if( iter == L.begin() )
iter = --L.end();
else
iter--;
}
cout << *iter << " ";
iter = L.erase(iter);
if(iter == L.end() )
iter = L.begin();
}
cout << endl;
return 0;
}
为什么mPrime <= numLeft/2时正着数，mPrime > numLeft/2时倒着数，同时为什么numLeft没有变化（此处是否有问题）？

Answer 1

你这个numLeft就是等于你输入的n，从来没改变过值，怎么会有变化？
另外STL里有rbegin和rend就是从后往前数的，不用你自己--L.end()

追问

你好，谢谢你的回答，这个程序是书上的程序，我没有看懂，那么numLeft既然没有用，是不是就可以直接删去这个变量，是不是这本书在此处有问题？另外mPrime numLeft/2时倒着遍历是程序解决问题的算法，我不懂这里，和STL里的rbegin和rend应该没有关系吧？

追答

什么书啊……没改变过值也不等于没有用啊，不能删掉。我的意思是正着数可以用begin()和end()倒着数用rbegin()和rend()，你这个书上的代码写的很不规范。
这里正着数和倒着数是为了效率，都正着数也行的。如果是在后一半里，那倒着数肯定快啊。

追问

谢谢你的回答！书是数据结构与算法分析C++描述 Mark Allen Weiss写的