题目描述:M个人围成一个圈,从第一个人开始报数1,报到N的人退出,下一个人继续从1开始报数,最后剩下的一个人的胜利者,求该胜利者。
分析:使用C++标准库bitset,每个人对应一位,然后开始报数,当报到N时将该位置为0.从下一位继续开始报数。
//M个人,报到N的退出。
-
//M个人,报到N的退出。
-
void JosephRing(int M ,int N)
-
{
-
assert(M > 0 && N > 0);
-
int i = 0;
-
int num = 0;//报数号。
-
std::bitset<M> bit;
-
bit.set(); //所有的人都在圈中,所有位都除初始化为1.
-
//当bit中只有一个人时退出。
-
for (;bit.count() > 1;++i)
-
{
-
//只有在圈中的人才报数。
-
if(bit.test(i % M))
-
{
-
++num;
-
-
}
-
if (num == N)
-
{
-
bit.reset(i);
-
num = 0;
-
}
-
}
-
}
阅读(1301) | 评论(0) | 转发(0) |