一个C++约瑟夫环的问题一群人围坐一圈,每人一个密码,一开始人选一个正整数作为报数上线M,丛第一个人开始顺时针方向自1开始报数,报道M停止,报出M的人出列,将他的密码作为新的M,丛他在顺

Question

一个C++约瑟夫环的问题
一群人围坐一圈,每人一个密码,一开始人选一个正整数作为报数上线M,丛第一个人开始顺时针方向自1开始报数,报道M停止,报出M的人出列,将他的密码作为新的M,丛他在顺时针方向的下一个人开始重新从1开始报数,如此下去直到所有人全部出列为止.
初值M=20；人数N=7；密码依次为3 1 7 2 4 8 4；
出列顺序为6 1 4 7 2 3 5

Answer 1

#include
#include
/*结构体*/
struct node
{
int num,secret;
struct node *next;
};
/*建造循环链表,并返回头指针*/
node *creatlinklist(int m)
{
node *head,*p,*q;
head=p=(node *)malloc(sizeof(node));
int j;
printf("输入第1个密码:");
scanf("%d",&j);
p->secret=j;
p->num=1;
for(int i=2;isecret=j;
q->num=i;
p->next=q;
p=q;
};
p->next=head;
return(head);
};
/*按规则实现排列*/
/*第一种方法 找到一个打印一个*/
/*void fun(node *H,int K,int M)
{
int i,j;
node *p;
for(j=1;jnext->secret;
printf("%d\t",p->next->num);
p->next=p->next->next;
H=p->next;
};
for(i=1,p=H;inext);
printf("%d\t",p->num);
printf("%d\t",p->next->num);
printf("\n");
};*/
/*第二种方法 把循环链表按规则变成单链表*/
void fun(node *H,int K,int M)
{
node *p,*q,*nhead;
int i,e;
/*按规则找到第一个节点,并将其作为新链表头结点nhead ,尾节点q*/
for(i=1,p=H;inext);
nhead=q=p->next;
K=q->secret;
p->next=p->next->next;
/*按规则找到剩下的节点并用尾插法连到新链表尾节点后*/
for(e=1;enext;inext);
K=p->next->secret;
q->next=p->next;
q=p->next;
p->next=p->next->next;
};
for(i=1,p=p->next;inext);
q->next=p;
/*输出序列*/
printf("输出密码序列:\n");
for(p=nhead,i=1;inext)
{
int j=p->secret;
printf("%d\t",j);
};
printf("\n输出顺序序列:\n");
for(p=nhead,i=1;inext)
{
int j=p->num;
printf("%d\t",j);
};
printf("\n");
};
/*主程序*/
void main()
{
int n,k;
node *h;
printf("输入节点数n:");
scanf("%d",&n);
printf("输入k值:");
scanf("%d",&k);
h=creatlinklist(n);
fun(h,k,n);
}