约瑟夫算法之问题解决（文字游戏：录入N个数，在录入M个点，从N个数中的M个点开始删除）

清疚 2021-09-01 10:37 198阅读 0赞

### 约瑟夫算法问题解决 ###

*  提出问题
 *   *  模拟实现
     *  代码实现

# 提出问题 #

文字游戏：录入N个数，然后再录入M点，从N个数里面数第M个点的数删除，然后从删除的下一位继续，数到M点再删除，然后以删除的下一个数开始，一直到删除剩余最后一位；

## 模拟实现 ##

举个例子：N=1，2，3，4，5;  
M=3;  
result=4;  
第一轮：去掉了数字 3 组成了新数组：1,2,4,5  
第二轮：去掉了数字 1 组成了新数组：2,4,5  
第三轮：去掉了数字5 组成了新数组：2,4  
第四轮：去掉了数字 2 组成了新数组：4；

## 代码实现 ##

public class yuesefuTest {
    	public static void main(String[] args) {
    		int[] list = new int[] {1,2,3,4,5};
    		int length = list.length;
    		System.out.println(LastRemaining_Solution(5, 3));
    		System.out.println(LastRemaining_Solution2(5, 3));
    		System.out.println(LastRemaining_Solution3(5, 3));
    	}
     
    	//模拟游戏验证
    	public static int LastRemaining_Solution(int n, int m) {
    		if (m <= 0 || n <= 0) return -1;
    			LinkedList<Integer> list = new LinkedList<Integer>();
    			for (int i = 0; i < n; i++) {
    				list.add(i);
    			}
    		int loc = 0;
    		while (list.size() > 1) {
    			loc = (loc + m - 1) % list.size();
    			list.remove(loc);
    		}
    		return list.get(0);
    	}
    	
    	//递推公式推导（循环法）
    	public static int LastRemaining_Solution2(int n, int m) {
    		if (m <= 0 || n <= 0) return -1;
    			int result = 0;
    			for(int i = 2; i <= n; i++) {
    				result = (result + m) % i;
    			}
    		return result;
    	}
    	
    	//递推公式推导（递归法）
    	public static int LastRemaining_Solution3(int n, int m) {
    		if (m <= 0 || n <= 0) return -1;
    			if(n == 1) {
    				return 0;
    			}else {
    				return (LastRemaining_Solution3(n - 1, m) + m) % n;
    			}
    	}
    }