Josephy 问题: 假设有N个人坐在圆桌周围,从第S个人开始报数,报到M的出列,
然后再从下一个人开始报数,数到M的人出列¨¨¨如此重复,直到所有的人都出
列为止。要求出列的先后顺序输出每个人的信息
# include<stdio.h>
# include<stdlib.h>
typedef int datatype;
typedef struct cnode
{
datatype data;
struct cnode *next;
}clistnode;
typedef clistnode *clinklist;
clinklist head;
void Joseph(int n,int m,int s)
{
int i,j,flag;
clinklist creatclinklist(int); /* 函数申明 :元素前插法创建循环链表,长度限定为N */
void print(clinklist head,int);
clistnode *p,*q,*r,*t;
head=creatclinklist(n);
print(head,n); /* 将循环链表的元素按顺序打印出来 */
q=head;
if(s>n) printf("error!n");
flag=s%n; /* 把指针q移动到第 S个结点,并把它给指针p,尽量减少指针移动的次数! */
for(i=1;i<flag;i++)
q=q->next;
p=q->next;
printf("%d个结点出队的顺序依次是;n",n);
for(i=1;i<=n;i++) /* 把i记为删除的结点个数 */
{
j=1;
flag=m%(n-i+1); /* 把指针p移动到第M个结点,尽量减少指针移动的次数!尽量使每次移动次数
不超过n次!时间复杂度O(n),提高该程序的执行效率! */
if(!flag) /* 不知道该移动几步!特殊处理一些结点! */
{
j=1;
while(j<m)
{
r=p;
p=p->next;
if(p==head)
continue;
j++;
}
}