问题描述:
N个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。请按退出顺序输出每个退出人的原序号。
本例可以使用两种方法实现:模拟法和数学推导法。其中模拟法又可以分为数组模拟和链表模拟,二者的时间复杂度都是O(n*p)。数学法的时间复杂度是O(n)
以下是模拟法的两种实现:
链表模拟法:按退出的先后顺序输出人的编号
import java.util.Scanner; class Node//构造链表节点 { int data; Node next; } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int p = scanner.nextInt(); Node list = new Node(); list.data = 1; Node temp = list; for (int i = 2; i <= n; i++)// 构造链表 { Node node = new Node(); node.data = i; temp.next = node; temp = temp.next; } temp.next = list; temp = temp.next; Node r = new Node(); while (temp.next != temp) { for (int j = 1; j < p; j++) { r = temp; temp = temp.next; } r.next = temp.next;//删除temp System.out.print(temp.data+" "); temp = r.next; } System.out.print(temp.data); } } }
数组模拟法:按退出的顺序输出
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int p = scanner.nextInt(); int[] a = new int[n + 1]; for (int i = 1; i <= n; i++) a[i] = i; int count = 0; int count1 = 0;// 记录输出的次数 for (int i = 1; i <= n; i++) { if (a[i] != 0) count++; if (count == p) { count1++; if (count1 == n)//最后一个输出没有空格且需要换行 { System.out.println(a[i]); break; } else { System.out.print(a[i] + " "); a[i] = 0; count = 0; } } if (i == n)//到最后一个数从头开始循环 i = 0; } } } }
数学方法:找出最后一个退出的人
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()) { int n = scanner.nextInt(); int p = scanner.nextInt(); int k = 1; for(int i = 1;i<=n;i++) { k = (k+p-1)%i+1; } System.out.println(k); } } }