《数据结构》课程常见问题
----单元 26 求解约瑟夫
1.求解约瑟夫问题?
解析:
问题描述:使用代表头节点的循环单链表解决此问题。设有 n 个人围坐在一张圆桌周围,现从某个人
开始从 1 报数,数到 m 的人离开。接着从出列的下一个人开始重新从 1 开始报数,数到 m 的人又出列,
如此下去直到所有的人都出列为止。求出他们的出列序列。
问题分析:例如,当 n=8,m=4 时,若从第一个人开始报数(设从 1 开始编号),则得到的序列是:
4,8,5,2,1,3,7,6。
算法:
void Josephus ( int n, int m,int s )
{ //生成表头节点,空单循环链表
LNode * HL = new LNode ;
HL -> next = HL ;
int i ;
//生成含有 n 个节点的、节点值依次为 1,2……,n 的带表头节点的循环单链表
For ( i = n ; i>=1; i-- )
{ LNode * newptr = new LNode;
Newptr -> data = i ;
newptr -> next = HL -> next ;
HL -> next = newptr ;
}
//从表头开始顺序查找出第 s 个节点,对应第一个开始报数的人
LNode * ap = HL, *cp = HL ->next ;
for ( i= 1; i<s; i++ ) {
ap = cp;
cp = cp->next;
if ( cp = = HL ) { ap = HL; cp = HL->next ; }
}
//依次使 n-1 个人出列
for ( i=1; i<n; i++ ) {
//顺序查找出待出列的人,即为循环结束后 cp 所指向的节点
for ( int j=1; j<m ;j++) {
ap = cp ;
cp = cp->next ;
if ( cp ==HL) { ap = HL; cp = HL->next ; }
}
//输出 cp 节点的值,即出列的人
cout << cp->data <<” “ ;
//从单链表中删除 cp 节点
ap -> next = cp -> next ;