零度空间

程序?人生! ——D调 QQ:24859
posts - 11, comments - 6, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

约瑟夫问题

Posted on 2006-02-27 17:18 D调 阅读(944) 评论(0)  编辑  收藏 所属分类: JAVA

编号为1,2,3,......,n的n个人按顺时针方向围坐一圈,开始选一正整数m,从第一人开始,按顺时针方向自1开始顺序报数,报到m时此人出列,从他在顺时针方向的下一个人开始从1报数,如此下去,直至剩一个人,求出个人的编号
public class Exercise
{
 public static void main(String args[])
    {  
int i, j, n, m;

  if(args.length != 2)  //处理参数数目不正确情况
  {

   System.out.println("Please Input a number!");
   return;
  }

  n = Integer.parseInt(args[0]);
  m = Integer.parseInt(args[1]);

  if (n <= 0 || m <= 0)
  {
   System.out.println("Paramter Error!");
   return;
  }

  int a[] = new int[n];

  for (i = 0; i < n; i++) a[i] = i + 1;

  int k = 1;   //标识处理第k个离开的人
  i = -1;    //数组下标,下一个为0,即第一个人

  while (true)
  {

   //在圈中数m个人
   for (j = 0; j < m;)
   {
    i = (i + 1) % n;
    if (a[i] != 0)   //a[i]不为0表示还没有离开
    {
     j++;
    }
   }

   if (k == n) break;  //k等于n表示只剩下一个人了

   a[i] = 0;   //表示该人离开
   k++;

  }

  System.out.println("No." + a[i] + " is the winner!");
 }
 }


只有注册用户登录后才能发表评论。


网站导航: