| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1106 人关注过本帖
标题:[求助]一个关于链表的编程题的解法.
只看楼主 加入收藏
icelake
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2007-1-17
收藏
 问题点数:0 回复次数:8 
[求助]一个关于链表的编程题的解法.
10个小孩围坐一圈,依次编号,指定从第s个小孩开始报数(从1-n报数),报到n的小孩出列,然后依次重复下去,直到所有小孩出列,求小孩出列的顺序?(用C++中的链表编)请教,谢谢!
搜索更多相关主题的帖子: 链表 解法 小孩 出列 
2007-01-17 19:00
song4
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:38
帖 子:1533
专家分:4
注 册:2006-3-25
收藏
得分:0 
N年了
链表好实现吧

嵌入式 ARM 单片机 驱动 RT操作系统 J2ME LINUX  Symbian C C++ 数据结构 JAVA Oracle 设计模式 软件工程 JSP
2007-01-18 08:45
jishuai
Rank: 1
等 级:新手上路
帖 子:97
专家分:0
注 册:2006-12-15
收藏
得分:0 

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


2007-01-18 13:41
dragonfly
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:1024
专家分:0
注 册:2006-3-20
收藏
得分:0 
链表的最末一个指向第一个,就成了圆的了,每次向下找第n个,删除(但要把断点接上,让被删除的上一个指向被删除的下一个)...

2007-01-18 14:21
icelake
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2007-1-17
收藏
得分:0 
[讨论]链表

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


2007-01-18 16:50
icelake
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2007-1-17
收藏
得分:0 
[讨论]链表
具体点,用C++编哦!

2007-01-18 17:00
olivezhang
Rank: 1
等 级:新手上路
帖 子:223
专家分:0
注 册:2005-9-14
收藏
得分:0 

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


谷底深深行 ,峰顶漫漫步......@_@
2007-01-19 17:59
olivezhang
Rank: 1
等 级:新手上路
帖 子:223
专家分:0
注 册:2005-9-14
收藏
得分:0 

抱歉,有的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;
}


谷底深深行 ,峰顶漫漫步......@_@
2007-01-19 18:00
icelake
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2007-1-17
收藏
得分:0 

谢谢


2007-01-19 18:13
快速回复:[求助]一个关于链表的编程题的解法.
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031220 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved