题意描述：1，……，n这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里面删除第m个数字。求这个圆圈中最后剩下的一个数字
解题思路一：模拟一个环，然后每次删除第m个数字
解题思路二：上述思路可行，但明显时间复杂度O(mn)。因此还是希望找找删除数字有什么规律。 递归公式： 0 , n = 1 f(n,m)= { [f(n-1,m)+m] % n , n > 1
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class LastNumberInCircle { //解题思路一：模拟一个环，然后每次删除第m个数字，暴力破解 private static int LastRemaining(int n, int m) { if(n < 1 || m < 1) return -1; List<Integer> list = new ArrayList<Integer>(); for(int i=0; i<n; i++)//list中添加1-n个编号 list.add(i+1); int index = -1;//需要淘汰的编号 while(list.size()>1){//循环结束的条件是环内只有1人 index = (index + m) % list.size(); System.out.println(list.get(index)); list.remove(index--); } return list.get(0); } //解题思路二：上述思路可行，但明显时间复杂度O(mn)。因此还是希望找找删除数字有什么规律。 //递归公式： 0 , n = 1 // f(n,m)= { // [f(n-1,m)+m] % n , n > 1 private static int LastRemaining2(int n, int m){ if(n < 1 || m < 1) return -1; int last = 0; for(int i=2; i<=n; i++) last = (last + m) % i; return last+1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int m = sc.nextInt(); System.out.println(LastRemaining(n, m) + "\t" + LastRemaining2(n, m)); } } }
