这是个约瑟夫问题,给你个例程作参考吧:
题目:
//猴子选大王: 有M个猴子围成一圈,每个有一个编号,编号从1到M。打算从中选出
//一个大王。经过协商,决定选大王的规则如下:从第一个开始,每隔N个,数到的
//猴子出圈,最后剩下来的就是大王。
/*
* name : FindKingOfMonkey
* desc : Find the king from nMonkeyNum monkeys.
* in : nMonkeyNum - All monkeys' numbers.
nCount - Every time we count nCount monkeys.
* out : --
* ret : The ring of monkey.
*/
int FindKingOfMonkey(int nMonkeyNum, int nCount);
实现:
//----------------------------------------------------------------------------*
int ari::FindKingOfMonkey(int nMonkeyNum, int nCount)
{
struct Monkey
{
int nNextMonkey; //Point to the next monkey.
int nNotOutFlg; //Flag of monkey whether is out. 1 - not out,
//0 - out.
};
struct Monkey *pMonkeyLink = new struct Monkey[nMonkeyNum + 1];
assert(NULL != pMonkeyLink);
int i, j, k;
i = j = k = 0;
for (i=1; i<=nMonkeyNum; i++)
{ //The element 0 is not used. ºï×Ó×ÜÊýΪnMonkeyNum, 0ºÅÔªËØûÓÐʹÓÃ.
pMonkeyLink[i].nNextMonkey = i + 1; //Point to next monkey.
pMonkeyLink[i].nNotOutFlg = 1; //At beginning, all monkeys are not
//out.
}
pMonkeyLink[nMonkeyNum].nNextMonkey = 1; //The last pointer point to the
//first monkey. Now we have
//constructed circulation of link.
int nOutCount = 1; //The counter of monkey who is out.
int nIndexOfMonkey = nMonkeyNum; //Ö¸ÏòÒѾ´¦ÀíÍê±ÏµÄÊý×éÔªËØ£¬´Ó
//pMonkeyLink[nIndexOfMonkey]Ö¸ÏòµÄºï×Ó¿ª
//ʼ¼ÆÊý, ´ËΪ´ÓµÚÒ»Ö»ºï×Ó¿ªÊ¼Êý.
//Let nMonkeyNum monkeys out, and only left the king.
for (nOutCount=1; nOutCount<nMonkeyNum; nOutCount++)
{
for (k=0; k<nCount; )
{
//È¡³öÏÂÒ»ºï×ÓµÄË÷ÒýϱêÖµ.
nIndexOfMonkey = pMonkeyLink[nIndexOfMonkey].nNextMonkey;
//Êý¾¹ýÁ˵ĺï×ÓÊý.Èç¹ûnNotOutflg == 0, ±íʾ¸Ãºï×ÓÒѾ³öȦ.Ìø¹ý¸Ã
//ºï×Ó.
k += pMonkeyLink[nIndexOfMonkey].nNotOutFlg;
}
pMonkeyLink[nIndexOfMonkey].nNotOutFlg = 0; //The monkey at
//nIndexOfMonkey is out.
}
int nKingOfMonkey = 0;
//Find the king of monkey whose nNotOutFlg == 1.
for (i=1; i<=nMonkeyNum; i++)
{
if (1 == pMonkeyLink[i].nNotOutFlg)
{
nKingOfMonkey = i;
break;
}
}
delete [] pMonkeyLink;
return nKingOfMonkey;
}
抱歉,有的comment乱码,重新整理:
实现:
//----------------------------------------------------------------------------*
int ari::FindKingOfMonkey(int nMonkeyNum, int nCount)
{
struct Monkey
{
int nNextMonkey; //Point to the next monkey.
int nNotOutFlg; //Flag of monkey whether is out. 1 - not out,
//0 - out.
};
struct Monkey *pMonkeyLink = new struct Monkey[nMonkeyNum + 1];
assert(NULL != pMonkeyLink);
int i, j, k;
i = j = k = 0;
for (i=1; i<=nMonkeyNum; i++)
{ //The element 0 is not used. 猴子总数为nMonkeyNum, 0号元素没有使用.
pMonkeyLink[i].nNextMonkey = i + 1; //Point to next monkey.
pMonkeyLink[i].nNotOutFlg = 1; //At beginning, all monkeys are not
//out.
}
pMonkeyLink[nMonkeyNum].nNextMonkey = 1; //The last pointer point to the
//first monkey. Now we have
//constructed circulation of link.
int nOutCount = 1; //The counter of monkey who is out.
int nIndexOfMonkey = nMonkeyNum; //指向已经处理完毕的数组元素,从
//pMonkeyLink[nIndexOfMonkey]指向的猴子开
//始计数, 此为从第一只猴子开始数.
//Let nMonkeyNum monkeys out, and only left the king.
for (nOutCount=1; nOutCount<nMonkeyNum; nOutCount++)
{
for (k=0; k<nCount; )
{
//取出下一猴子的索引下标值.
nIndexOfMonkey = pMonkeyLink[nIndexOfMonkey].nNextMonkey;
//数经过了的猴子数.如果nNotOutflg == 0, 表示该猴子已经出圈.跳过该
//猴子.
k += pMonkeyLink[nIndexOfMonkey].nNotOutFlg;
}
pMonkeyLink[nIndexOfMonkey].nNotOutFlg = 0; //The monkey at
//nIndexOfMonkey is out.
}
int nKingOfMonkey = 0;
//Find the king of monkey whose nNotOutFlg == 1.
for (i=1; i<=nMonkeyNum; i++)
{
if (1 == pMonkeyLink[i].nNotOutFlg)
{
nKingOfMonkey = i;
break;
}
}
delete [] pMonkeyLink;
return nKingOfMonkey;
}