黑马程序员技术交流社区

标题: 关于约瑟夫环的题目 [打印本页]
作者: popoluno    时间: 2013-7-9 14:20
标题: 关于约瑟夫环的题目
100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
求解法，详细的解释，网上摘抄的请远走！
作者: 李仕勇    时间: 2013-7-9 15:07
  1.   int KnSkyint,jici=0;
  2.             for (int  t =1;  t <= 100;t ++) //一到一百个人的位置循环
  3.             {
  4.                 if (jici == 0)
  5.                 {
  6.                     KnSkyint = t;    //如果计次是零  那么就证明报数在1到14以内  q且   14的倍数为零
  7.                 }
  8.                 else
  9.                 {
  10.                     KnSkyint = t - 14 * jici;   //计次不等于零  那么报的数就相当于现在所报数人员的的位置减去14的倍数
  11.                 }
  12.                 for (int d = 1; d <=Convert.ToInt32(100/14); d++)   //看现在报数人员是否是14的倍数
  13.                 {
  14.                     if (t == d * 14)
  15.                     {

  17.                      
  18.                         jici = d;  //如果是14的倍数  那么记录下现在是14的几倍
  19.                     
  20.                     }
  21.                 }
  22.               
  23.               
  24.             }
  25.             return KnSkyint;
复制代码
作者: 高腾    时间: 2013-7-9 17:16
  1. Console.Write("请输入总人数：");
  2.             int m = Convert.ToInt32(Console.ReadLine());

  4.             Console.Write("请输入数到几移除：");
  5.             int n = Convert.ToInt32(Console.ReadLine());

  7.             List<int> li = new List<int>();
  8.             for (int i = 1; i <= m; i++)
  9.             {
  10.                 li.Add(i);
  11.             }

  13.             int count = 0;
  14.             int lastPeople;
  15.             while (true)
  16.             {
  17.                 int isDel = 0;
  18.                 lastPeople = 0;
  19.                 for (int i = 0; i < li.Count + isDel; i++)
  20.                 {
  21.                     count++;
  22.                     if (count % n == 0)
  23.                     {
  24.                         lastPeople = li.Count - i - 1;
  25.                         li.Remove(li[i - isDel]);
  26.                         isDel++;
  27.                         if (i == 0)
  28.                         {
  29.                             lastPeople = li.Count - 1;
  30.                         }
  31.                         else
  32.                         {
  33.                             lastPeople = n - 1 - lastPeople - 1;
  34.                         }
  35.                     }
  36.                 }
  37.                 if (li.Count < n)
  38.                 {
  39.                     break;
  40.                 }
  41.             }

  43.             Console.WriteLine("剩余的人为：");
  44.             foreach (int i in li)
  45.             {
  46.                 Console.Write("{0}\t", i);
  47.             }

  49.             if (li.Count == 1)
  50.             {
  51.                 Console.Write("最后一个人为：{0}", li[0]);
  52.             }
  53.             else
  54.             {
  55.                 Console.Write("最后一个人为：{0}", li[lastPeople]);
  56.             }

  58.             Console.ReadKey();
复制代码
作者: wanghuailin1030    时间: 2013-7-9 21:06
我是在视频面试是碰到的这道题，已经贴过帖子，问过人。下面是得到的三种方法，我只理解了第一种。要是让我写，我也就只能写出第一种。
          //1、用数组来实现
        //static void Main(string[] args)
        //{
            //int[] a = new int[100];
            //int count = 0, turn = 0;
            //for (int i = 0; i < 100; )
            //{
            //    if (a != 1)
            //    {
            //        count += 1;
            //        if (count % 14 == 0)//是14的倍数则赋值为0
            //        {
            //            a =1;
            //            turn += 1;//计算被赋值0的次数，知道最后一个，结束循环
            //            if (turn == 99) { break; }
            //        }
            //    }
            //    if (i == 99) { i = 0; } else { i++; }//循环完成，将不为0的数组成新数组从新走一遍循环
            //}
            //for (int i = 0; i < 100; i++)
            //{
            //    if (a != 1)
            //    {
            //        Console.WriteLine("{0}", i + 1);
            //    }
            //}
            //Console.ReadKey();
        //}


         //2、运用LIST泛型来实现
        //static void Main(string[] args)
        //{
        //   
        //    List<int> li = new List<int>();
        //    for (int i = 1; i <= 100; i++)//每个泛型赋值
        //    {
        //        li.Add(i);
        //    }
        //    int count = 0;
        //    while (true)
        //    {
        //        int isDel = 0;
        //        for (int i = 0; i < li.Count + isDel; i++)//进行循环，同时保持每次循环减少与增加的总数
        //        {
        //            count++;//无限增长，每14一次判断
        //            if (count % 14 == 0)
        //            {
        //                li.Remove(li[i - isDel]);//满足条件后，每次移除相应的下标。应为移除后i从新排列，所以需要减isDel
        //                isDel++;
        //            }
        //        }
        //        if (li.Count < 2)//每次循环完毕，进行判断查看是否最小。如果不，则将isDel清零，进行移除后新泛型判断
        //        {
        //            break;
        //        }
        //    }
        //    foreach (int i in li)//输出最后的队列
        //    {
        //        Console.Write("{0}\t", i);
        //    }
        //    Console.WriteLine();
        //    Console.Write(li[li.Count - 1]);//输出结果
        //    Console.ReadKey();
        //}


        //3、数学方法
        //public static long Josephus(long n, long m, long start)
        //{ //参数分别为：人数，出圈步长，起使报数位置,
        //    long k = 1;
        //    for (long i = 2; i <= n; i++)
        //        k = (k + m - 1) % i + 1;
        //    return (k + start - 1) % n; //返回最后一人的位置
        //}
        //static void Main(string[] args)
        //{
        //    long t=Josephus(100,14, 1);
        //    Console.WriteLine(t);
        //    Console.ReadKey();
        //}
作者: 潘多拉    时间: 2014-10-8 18:43
面试时还能遇到这种题呢？其实我看不太懂！那正确答案到底是？



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