黑马程序员技术交流社区

标题: 一道以约瑟夫环为模型的问题 [打印本页]
作者: 人在旅途~东营    时间: 2015-6-2 20:03
标题: 一道以约瑟夫环为模型的问题
今天看了一道题,差点没吐了,总算明白了,跟大家分享下
由n个小孩围成一个首尾相连的圈报数。
*从第k个人开始，从1开始报数，报到m的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的k,m和n，求出最后出圈的小孩.
  1. package com.itcast.cyclink;

  3. public class Test1 {
  4.         public static void main(String[] args) {
  5.                 CycLink cycLink = new CycLink();
  6.                 cycLink.setLen(100);
  7.                 cycLink.createLink();
  8.                 cycLink.setK(1);
  9.                 cycLink.setM(14);
  10.                 //cycLink.show();
  11.                 cycLink.play();
  12.                
  13.         }

  15. }

  17. class Child{
  18.         int no;
  19.         Child nextChild = null;
  20.         public Child(int no){
  21. //                给一个编号
  22.                 this.no = no;
  23.         }
  24.        
  25. }
  26. //环形链表
  27. class CycLink{
  28.        
  29. //        先定义一个指向链表第一个小孩的引用
  30. //        第一个小孩是不能动的
  31.         Child firstchild = null;
  32.         Child temp = null;
  33.         int len = 0;//表示共有几个小孩
  34.         int k = 0;
  35.         int m = 0;
  36.        
  37.        
  38. //        设置链表大小
  39.         public void setLen(int len){
  40.                 this.len= len;
  41.         }
  42. //        设置从第几个人开始数数
  43.         public void setK(int k){
  44.                 this.k = k;
  45.         }
  46.         //        设置数m下
  47.         public void setM(int m){
  48.                 this.m = m;
  49.         }
  50.         //开始play
  51.         public void play(){
  52. //                首先找到跑龙套的人
  53.                 Child temp = this.firstchild;               
  54. //                1.先找到开始数数的人
  55.                 for (int i = 1; i < k; i++) {
  56.                         temp = temp.nextChild;
  57.                 }
  58.                 while(this.len!=1){
  59.                        
  60. //                2.数m下
  61.                         for (int j = 1; j < m; j++) {
  62.                                
  63.                                 temp = temp.nextChild;
  64.                         }
  65. //                找到要出圈的前一个人
  66.                         Child temp2 = temp;
  67.                         while (temp2.nextChild!=temp) {
  68.                                 temp2 = temp2.nextChild;
  69.                                
  70.                         }
  71. //                3.将数到m的小孩退出圈
  72.                         temp2.nextChild=temp.nextChild;
  73. //                让temp指向下一个数数小孩
  74.                         temp = temp.nextChild;
  75.                         this.len--;
  76.                        
  77.                 }
  78. //                最后一个小孩
  79.                 System.out.println("最后出圈的小孩是:"+temp.no);
  80.                
  81.         }
  82. //        初始化环形链表
  83.         public void createLink(){
  84.                 for (int i = 1; i <= len; i++) {
  85.                         if (i==1) {
  86. //                                创建第一个小孩
  87.                                 Child ch = new Child(i);
  88.                                 this.firstchild = ch;
  89.                                 this.temp = ch;
  90.                        
  91.                         }else {
  92. //                                创建最后一个小孩
  93.                                 if (i==len) {
  94. //                                        继续创建小孩
  95.                                         Child ch = new Child(i);
  96.                                         temp.nextChild = ch;
  97.                                         temp=ch;
  98.                                         temp.nextChild = this.firstchild;
  99.                                 }else {
  100. //                                        继续创建小孩
  101.                                         Child ch = new Child(i);
  102.                                         temp.nextChild=ch;
  103.                                         temp = ch;
  104.                                 }
  105.                         }
  106.                        
  107.                 }
  108.         }
  109. //        打印环形链表
  110.         public void show(){
  111. //                定义一个跑龙套
  112.                 Child temp = this.firstchild;
  113.                 do {
  114.                         System.out.print(temp.no);
  115.                         temp=temp.nextChild;
  116.                 } while (temp != this.firstchild );
  117.         }
  118. }
复制代码
作者: 石头888    时间: 2015-6-2 20:18
学习学习！



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2