约瑟夫环-(数组、循环链表、数学)

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

约瑟夫环运作如下：

1、一群人围在一起坐成环状（如：N）

2、从某个编号开始报数（如：S）

3、数到某个数（如：M）的时候，此人出列，下一个人重新报数

4、一直循环，直到所有人出列  ，约瑟夫环结束

模拟过程，求出最后的人。

把数组看成一个环，从第s个元素开始按m-1间隔删除元素，重复过程，直到元素全部去掉。

  

   

    

     

    
    

     

      void Josephus(int a[],int n,int m,int s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j;
     
    
   

    

     

    
    

     
 int k=n;
     
    
   

    

     

    
    

     
 for(i=0;i<n;i++)a[i]=i+1;//编号
     
    
   

    

     

    
    

     

       i=(s+n-1)%n;
     
    
   

    

     

    
    

     
 while(k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=1;j<m;j++)i=(i+1)%k;//依次报数，头尾相连
     
    
   

    

     

    
    

     
 printf("%d\n",a[i]);//出局
     
    
   

    

     

    
    

     
 for(j=i+1;j<k;j++)a[j-1]=a[j];//删除本节点
     
    
   

    

     

    
    

     

       k--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 //模拟结束，最后输出的就是留下的人
     
    
   

    

     

    
    

     

      }
     
    
  
 

可以用带头单循环链表来求解：

也是一样的，只是实现不同，给出核心代码：

  

   

    

     

    
    

     
 while(k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 for(j=1;j<m;j++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       pr=p;
     
    
   

    

     

    
    

     

       p=p->link;
     
    
   

    

     

    
    

     
 if(p==head)//头结点跳过
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       pr=p;
     
    
   

    

     

    
    

     

       p=p->link;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       k--;
     
    
   

    

     

    
    

     
 //打印
     
    
   

    

     

    
    

     

       pr->link=p->link;//删结点
     
    
   

    

     

    
    

     
 free(p);
     
    
   

    

     

    
    

     

       p=pr->link;//从下一个继续
     
    
   

    

     

    
    

     

       }
     
    
  
 

双向循环链表也可以解，和单链表类似，只是不需要保持前趋指针。

数学可解：

效率最高

  

   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int check_last_del(int n,int m)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i = 1;
     
    
   

    

     

    
    

     
	int ret = 0;
     
    
   

    

     

    
    

     
	for (i = 2; i<=n;i++)
     
    
   

    

     

    
    

     

       ret = (ret + m) %i;
     
    
   

    

     

    
    

     
	return ret+1;//因为ret是从0到n-1，最后别忘了加1。
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/82980735