约瑟夫环

r囧r小猫 2021-12-20 04:29 320阅读 0赞

编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一 开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那 个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如 此下去，直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。 \*/ /\*第一行输入两个整数，依次表示人数n和初始化密码m，以空格间隔。 第二行依次输入n个整数，分别表示n个人的密码，以空格间隔。 \*/ /\*按出列次序输出每个人的编号，以空格间隔。

代码如下：

#include <stdio.h>
    #include<stdlib.h>
    typedef struct stu{
    	int data;
    	struct stu *next;
    	int password;
    }st;
    
    st *init_list()
    {
    	st *head;
    	head=(st *)malloc(sizeof(int));
    	head->next=NULL;
    }
    st *create(int n)
    {
    	st *head,*p,*r,*s;
    	int i,x;
    	head=init_list();
    	r=head;
    	for(i=1;i<=n;i++)
    	{
    		s=(st *)malloc(sizeof(int));
    		s->data=i;
    		scanf("%d",&x);
    		s->password=x;
    		s->next=r->next;
    		r->next=s;
    		r=s;
    	}
    	 r->next=head->next;
    	return head;
    }
    void deal(int n,int m,st *head)
    {
     int icount=1,count=0;	
     st *p=head->next->next,*pre=head->next,*r,*tmp=head->next;
     free(head);
     while(1)
     {
     	if(pre->next==tmp)
     	 {r=pre; break;}
     	 else	{pre=pre->next;}
     }
     pre=pre->next;
     	while(1)
     	{   count++;
     	if(count%m==0)
     	{  	r->next=pre->next;
     		printf("%d ",pre->data);
            count=0;
            m=pre->password;
            free(pre);
            pre=r->next;
            icount++;
        }
        if(count%m)
    	{
    	pre=pre->next;;
        r=r->next;
    	}
    	if(icount-1==n) break;	
    	 }
    	 return ;
    
    /*
     while(1)
     {
     	icount++;
    	if(icount%m==0)
    	{   
    		pre->next=p->next;
    		printf("%d ",p->data);
    		icount=1;
    		m=p->password;
    		free(p);
    		p=pre->next;
    		count++;
    	}  
     	if(icount%m)
     	{
     	pre=pre->next;
    	p=p->next;	
    	}
    	if(count==n) break;
     }*/	
    		
    } 
    main()
    {
    	int n,m;
    	st *head;
    	scanf("%d %d",&n,&m);
    	//getchar();
    	head=create(n);
    	deal(n,m,head);
    }

转载于:https://www.cnblogs.com/cstdio1/p/11083353.html