[求助]一个关于链表的编程题的解法. - C++

顺其自然

电梯直达

1^#

发表于 2009-11-4 02:07:11 | 只看该作者回帖奖励

|倒序浏览 |阅读模式

10个小孩围坐一圈，依次编号，指定从第s个小孩开始报数（从1-n报数），报到n的小孩出列，然后依次重复下去，直到所有小孩出列，求小孩出列的顺序？（用C++中的链表编）请教，谢谢！

收藏0

使用道具举报

lala

2^#

发表于 2009-11-4 02:07:11 | 只看该作者

N年了
链表好实现吧

回复支持反对

使用道具举报

我只在乎你

3^#

发表于 2009-11-4 02:07:12 | 只看该作者

看看数据结构里面的链表嘛
自己应该可以写出来的啊

回复支持反对

使用道具举报

CHLOE

4^#

发表于 2009-11-4 02:07:13 | 只看该作者

链表的最末一个指向第一个,就成了圆的了,每次向下找第n个,删除(但要把断点接上,让被删除的上一个指向被删除的下一个)...

回复支持反对

使用道具举报

駃旒_鎏蒗瀦

5^#

发表于 2009-11-4 02:07:14 | 只看该作者

数据结构还没学，怎么做，麻烦指导一下。 qq451127649感谢!!

回复支持反对

使用道具举报

1OOOO

6^#

发表于 2009-11-4 02:07:15 | 只看该作者

具体点，用C++编哦！

回复支持反对

使用道具举报

炫夜

7^#

发表于 2009-11-4 02:07:16 | 只看该作者

这是个约瑟夫问题，给你个例程作参考吧：
题目：
//猴子选大王: 有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;
}

回复支持反对

使用道具举报

		自动登录	找回密码
密码			注册