[求助]求个思路

新郎

一群小孩围成一个圈，任意假定一个数M，从第一个小孩起，顺时针方向数，每次数到第M个小孩时，该小孩就离开，小孩不断的离开，圈子不断缩小，最后，剩下的小孩便是胜利者，那么，究竟谁是胜利者？



小弟刚学C++，望各位大哥大姐可以给我点思路，我实在是想不出来了，又没人教我。看书又看不懂

‖蠻忝謃☆

这题的答案好像任何书上都有啊，至少十年前俺用谭浩强叔叔的书学C的时候就是标准习题。
随便设个数组，循环链表之类的，每数一次删掉一个数就可以了。

X~iao~ping

程序代码：

#define NEED_MORE_ROUND -2
// return -2 if need mor eround,
// return -1 if error.
int RoundWinner(int intChildNum, int intCounterNum)
{
int intCount;
static int intCurrentPosition = 0;
static vector<int> vecSequence;
if (intChildNum <= 0 || intCounterNum <= 0)
return -1;
if (intChildNum == 1)
return 1;
// initialize sequence.
if (vecSequence.size() == 0)
{
for (intCount = 0; intCount < intChildNum; intCount++)
vecSequence.push_back(intCount);
}
intCurrentPosition = (intCurrentPosition+intCounterNum-1) % vecSequence.size();
cout << "number " << (vecSequence[intCurrentPosition]+1) << "is out" << endl;
vecSequence.erase(vecSequence.begin() + intCurrentPosition);
if (vecSequence.size() > 1)
return NEED_MORE_ROUND;
return vecSequence[0];
}

int main(int argc, char* argv[])
{
int intResult;
while ((intResult = RoundWinner(6, 5)) == NEED_MORE_ROUND)
;
cout << "Winner is number " << intResult+1 << endl;
}

森林的眼泪

约瑟夫问题！数据结构的课本上关于顺序表的的一个例子，楼上的给的太多了。
#include<iostream.h>
const int n=8; //n个小孩
const int m=4; //1－m报数
void josephus()
{
int p[n]; //建立顺序表
int i,j,t;
for(i=0;i<n;i++)
p[i]=i+1;
t=0; //首次报数的起始位置
for (i=n;i>0;i--) //i是顺序表的长度
{
t=(t+m-1)%i; //t为出列位置
cout<<p[t]<<" "; //p[t]出列
for(j=t+1;j<i;j++)
p[j-1]=p[j]; //后面的元素依次前移
}
}
void main()
{
josephus();
}

地瓜

补充一下，针对楼主的问题，最后输出的那个当然就是胜利者了。即p[0]。

ヤforget♀戀

按照楼主的意思,好象每次都是从第一个开始数,那最后应该是第二个小孩.

liu

楼主说的是“任意假定一个数M”所以还是用动态的数据机构比较好。

(のkisδ≒雪

皋阳的算法比较让人易懂 思路比较清晰
佩服啊