网站建设制作做网站优化推广公司,做生物学的网站,谷歌安装器,WordPress 评论列表折叠/*** 约瑟夫问题* 设编号为 1#xff0c;2#xff0c;… n 的 n 个人围坐一圈#xff0c;* 约定编号为 k(1kn)的人从 1 开始报数#xff0c;* 数到 m 的那个人出列#xff0c;* 它的下一位又从 1 开始报数#xff0c;数到 m 的那个人又出列#xff0c;* 依次类推…/*** 约瑟夫问题* 设编号为 12… n 的 n 个人围坐一圈* 约定编号为 k(1kn)的人从 1 开始报数* 数到 m 的那个人出列* 它的下一位又从 1 开始报数数到 m 的那个人又出列* 依次类推直到所有人出列为止* 由此 产生一个出队编号的序列。*/public class JosephuDemo {public static void main(String[] args) {CircleSingleLinkedList circle new CircleSingleLinkedList();int n 5;circle.build(n);circle.show();int[] order circle.orderOutOfCircle(3, 2, n);System.out.println(Arrays.toString(order));}}class CircleSingleLinkedList {private Node first;// 构建约瑟夫环public void build(int n) {if (n 1) {System.out.println(输入的值不正确);return;}Node cur null; // 辅助指针用来帮助构建环形链表for (int i 1; i n; i) {Node node new Node(i);if (i 1) {first node;first.next first;cur first;} else {cur.next node;node.next first;cur node;}}}/*** 返回约瑟夫环问题的出环顺序* param start 从第几个开始数* param count 数几下* param n 最初环中有多少个* return*/public int[] orderOutOfCircle(int start, int count, int n) {if (first null || start n) throw new InvalidParameterException(参数有误);int[] res new int[n];int index 0;Node helper first;// 让helper指向环形链表的最后那个node// helper 指向了最后的node则终止循环while (helper.next ! first) {helper helper.next;}// 小孩报数前先让first和helper移动start-1次for (int i 0; i start - 1; i) {first first.next;helper helper.next;}// 小孩报数时让first和helper指针同时移动count - 1次然后出圈// 这时说明环中只剩下一个nodewhile (first ! helper) {// 让first和helper同时移动count - 1次for (int i 0; i count - 1; i) {first first.next;helper helper.next;}// 这时first指向的小孩就是要出圈的小孩res[index] first.value;first first.next;helper.next first;}res[index] first.value; // 最后留在圈中的小孩也要加入进结果return res;}// 遍历当前环形链表public void show() {if (first null) {System.out.println(链表为空);return;}Node cur first;while (true) {System.out.print(cur.value );if (cur.next first) break;cur cur.next;}}}参考: 韩顺平老师的数据结构
