标题: [求助]一个关于链表的编程题的解法. [打印本页] 作者: 顺其自然 时间: 2009-11-4 02:07 标题: [求助]一个关于链表的编程题的解法. 10个小孩围坐一圈，依次编号，指定从第s个小孩开始报数（从1-n报数），报到n的小孩出列，然后依次重复下去，直到所有小孩出列，求小孩出列的顺序？（用C++中的链表编）请教，谢谢！作者: lala 时间: 2009-11-4 02:07
N年了
链表好实现吧作者: 我只在乎你 时间: 2009-11-4 02:07
看看数据结构里面的链表嘛
自己应该可以写出来的啊作者: CHLOE 时间: 2009-11-4 02:07
链表的最末一个指向第一个,就成了圆的了,每次向下找第n个,删除(但要把断点接上,让被删除的上一个指向被删除的下一个)...作者: 駃旒_鎏蒗瀦 时间: 2009-11-4 02:07
数据结构还没学，怎么做，麻烦指导一下。 qq451127649感谢!!作者: 1OOOO 时间: 2009-11-4 02:07
具体点，用C++编哦！作者: 炫夜 时间: 2009-11-4 02:07
这是个约瑟夫问题，给你个例程作参考吧：
题目：
//猴子选大王: 有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. o?×ó×üêy?anMonkeyNum, 0o??a????óDê1ó?.
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; //???òò??-′|àííê±?μ?êy×é?a??￡?′ó
//pMonkeyLink[nIndexOfMonkey]???òμ?o?×ó?a
//ê???êy, ′??a′óμúò???o?×ó?aê?êy.
//Let nMonkeyNum monkeys out, and only left the king.
for (nOutCount=1; nOutCount<nMonkeyNum; nOutCount++)
{
for (k=0; k<nCount; )
{
//è?3???ò?o?×óμ??÷òy??±ê?μ.
nIndexOfMonkey = pMonkeyLink[nIndexOfMonkey].nNextMonkey;
//êy?-1yá?μ?o?×óêy.è?1?nNotOutflg == 0, ±íê???o?×óò??-3?è|.ì?1y??
//o?×ó.
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;
}