约瑟夫环

发表于 | 分类于

约瑟夫环

约瑟夫环问题可简化为：
编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。

由题可知，我们需要先构建一个结构体，其中包括了每个人的编号和密码。

1
2
3
4
5
6
typedef struct node
{
	int id;//**编号**
	int pas;//**密码**
	struct node *next; 
 }node,*Lnode;

接下来我的思路是构建一个单向循环链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Lnode create(Lnode L,int n)//用n代表人数
 {
 	L=(Lnode)malloc(sizeof(node));
 	Lnode p,q;
 	p=L;
 	int i=1;
 	while(n>0)
 	{
	    q=(Lnode)malloc(sizeof(node));
 		p->next=q;
 		scanf("%d",&q->pas);//输入每个人的密码
 		q->id=i;
 		p=q;
 		n--;
 		i++;
	 }
	 q->next=L->next;
	 return L;
}

接下来就是实现约瑟夫环，我的思路是若第x个人退出，那么就让指针移动到x-1的位置，然后输出x的编号以后进行删除，令X-1指向X+1。
这个问题还有一些特殊情况需要处理，比如如果刚开始只有一个人，则用if判断以后直接输出编号也就是1就行了，若还剩下两个人，我取巧，直接进行一个奇偶数判定，奇数的话就先输出该节点的编号，偶数就先输出next的编号，然后再输出自身的编号。
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
  int ysf(int m,int n) {
  	Lnode L=create(L,n),p,q;
p=L->next;
int x;
x=n;
if(n==1)
{
	printf("%d",p->id);
	return 0;
}
while(n>1)
{ x=n;
	if(m==1)
	{
		if(n>2)
		{
					for(x=(n-1);x>0;x--)
		{
			p=p->next;
		}
		printf("%d",p->next->id);printf(" ");
		m=p->next->pas;
		q=p->next;
        p->next=q->next;
        free(q) ;
        p=p->next;
        n--;
       }
        else if(n==2){
       	 printf("%d",p->id);printf(" ");
       	 printf("%d",p->next->id);
       	 n--;
	   }
		   		}
	else if(m!=1){	

            if(n==2){
            	if(m%2==1)
       	             {printf("%d",p->id);printf(" ");
       	             printf("%d",p->next->id);
       	             n--;}
       	        else {printf("%d",p->next->id);printf(" ");
				      printf("%d",p->id);
                         n--;}
				   }
	           
		    else{ x=m;
	           for(;x>2;x--)
			    { p=p->next;}	           

            printf("%d",p->next->id);printf(" ");
            m=p->next->pas;
	    	q=p->next;
            p->next=q->next; 
			free(q) ;
			p=p->next;
            n--;
		    }
    	}

以上便是我对约瑟夫环的理解。