约瑟夫问题公式及代码实现

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。（也有丢手绢问题）

• 首先A开始报数，他报1。侥幸逃过一劫。
• 然后轮到B报数，他报2。非常惨，他被杀了
• C接着从1开始报数
• 接着轮到A报数，他报2。也被杀死了。
• 最终胜利者是C

链表实现

链表是模拟整个游戏过程，缺点是当数很大时，几乎是没有办法在短时间内出结果。

  

   

    

     

    
    

     

      import java.util.*
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public int lastRemaing_Solution(int n,int m){
     
    
   

    

     

    
    

     
    if(n==0 ||m==0){
     
    
   

    

     

    
    

     
        return -1;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          ListNode<Integer> list=new ListNode<>();
     
    
   

    

     

    
    

     
    for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     

              list.add(i);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int removeIndex=0;
     
    
   

    

     

    
    

     
    while(list.size()!=1){
     
    
   

    

     

    
    

     

              removeIndex=(removeIdex+m-1)%list.size();
     
    
   

    

     

    
    

     

              list.remove(removeIndex);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return list.get(0);
     
    
   

    

     

    
    

     

      }
     
    
  
 

数组实现

公式的推导如下面博主的链接：https://blog.csdn.net/u011500062/article/details/72855826

  

   

    

     

    
    

     

      import java.util.*
     
    
   

    

     

    
    

     

      public class soulution{
     
    
   

    

     

    
    

     
    public int removeLast_Solutiion(int n,int m){
     
    
   

    

     

    
    

     
        if(n==0||m==0){
     
    
   

    

     

    
    

     
            return -1;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        int last=0;
     
    
   

    

     

    
    

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

    

     

    
    

     

                  last=(last+m)%i;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return last+1;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/113036148