黑马程序员技术交流社区

标题: C#解决奔猪问题（智力面试题） [打印本页]

作者: 曾家伟 时间: 2012-10-8 12:58
标题: C#解决奔猪问题（智力面试题）
38只猪要选出3只跑得最快的但场地只答应6只同时赛跑。
问：在没有计时器的情况下怎样可以用最快、最好的方法选出最快的3只猪
假设每只猪速度一定且不受体力影响。

【解析】把猪分成7组，前六组每组6只，第七组2只。七组分别标记为a、b、c、d、e、f、g。
1~6步：让前六组先跑，每组第一名留下设为a1、b1、c1、d1、e1、f1并把每组的第一名好标记如aMax、bMax等。
7让每组第一名共六只赛跑，把前三名留下，假设分别为max1、max2、max3。
8将前面的三只猪和第七组的两只猪一起进行赛跑选出最快的三只猪即为这38只猪中最快的三只猪
代码：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _01三十八只猪
{
class Program
{
      /*38只猪要选出3只跑得最快的但场地只答应6只同时赛跑。
      * 问在没有计时器的情况下怎样可以用最快、最好的方法选出最快的3只猪
      * 假设每只猪速度一定且不受体力影响。*/
      static void Main(string[] args)
      {
         //将38只猪分成7组
         int[] a = { 1, 2, 3, 4, 5, 6 };
         int[] b = { 7, 8, 9, 10, 11, 12 };
         int[] c = { 13, 14, 15, 16, 17, 18 };
         int[] d = { 19, 20, 21, 22, 23, 24 };
         int[] e = { 25, 26, 27, 28, 29, 30 };
         int[] f = { 31, 32, 33, 34, 35, 36 };
         int[] g = { 37, 38 };

         //用来标记前6组中每组最快的那只
         int aMax = a[0], bMax = b[0], cMax = c[0], dMax = d[0], eMax=e[0],fMax = f[0];

         //让前六组比赛，将每组速度最快的存入aMax ……fMax
         for (int i = 0; i < 6; i++)
         {
            if (aMax < a[i])
                  aMax = a[i];
            if (bMax < b[i])
                  bMax = b[i];
            if (cMax < c[i])
                  cMax = c[i];
            if (dMax < d[i])
                  dMax = d[i];
            if (eMax < e[i])
                  eMax = e[i];
            if (fMax < f[i])
                  fMax = f[i];
         }

         //得到前六组中每组最大的一只，存入数组
         int[] arrMax = { aMax, bMax, cMax, dMax, eMax, fMax };

         //排序用来寻找前三名
         int temp;
         for (int i = 0; i < 6; i++)
            for (int j = 0; j < 5 - i;j++ )
            {
                  if (arrMax[j] < arrMax[j + 1])
                  {
                     temp = arrMax[j];
                     arrMax[j] = arrMax[j + 1];
                     arrMax[j + 1] = temp;
                  }
            }

         //将前三名和g组两只猪存入数组
         int[] lastMax = { arrMax[0], arrMax[1], arrMax[2], g[0], g[1] };

         //排序寻找最终的前三名
         for (int i = 0; i < 5; i++)
            for (int j = 0; j < 4 - i; j++)
            {
                  if (lastMax[j] < lastMax[j + 1])
                  {
                     temp = lastMax[j];
                     lastMax[j] = lastMax[j + 1];
                     lastMax[j + 1] = temp;
                  }
            }
         //最终前三名标志
         int max1 = lastMax[0], max2 = lastMax[1], max3 = lastMax[2];
         //输出前三名
         Console.WriteLine("第一名为{0} 第二名为{1} 第三名为{2}",max1,max2,max3);
         Console.ReadKey();
      }
}
}

作者: 许庭洲 时间: 2012-10-8 14:32
值得学习ing!

作者: 蔡嘉 时间: 2012-10-8 15:14
楼主，解析的似乎有点问题？根据题目要求，第七步时，如果第一组的前三名就是跑的最快的猪呢？显然，把前六组的第一名分组赛跑是不合理的。
这样解析是否合理些：前六组的所有前三名共十八头猪，分为三组。再次淘汰后，三组猪的前三名共有9头猪。然后9+2=11，把11头猪分为两组，各取前三名。最后，剩下6头猪了，让这6头决出前三名。

作者: 曾家伟 时间: 2012-10-8 15:42

蔡嘉发表于 2012-10-8 15:14
楼主，解析的似乎有点问题？根据题目要求，第七步时，如果第一组的前三名就是跑的最快的猪呢？显然，把前六 ...

你的方式是最正确的，但是也是最慢的！要想用最好最快的方式必须用我这种方法！取权衡。

作者: 蔡嘉 时间: 2012-10-8 15:58

曾家伟发表于 2012-10-8 15:42
你的方式是最正确的，但是也是最慢的！要想用最好最快的方式必须用我这种方法！取权衡。 ...

应该没有最好的方法，只有符合项目实际的方法是合适的方法。编程不就是为了解决实际需求吗？如果脱离了实际，“最好最快”也是没用的。

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

黑马程序员IT技术论坛 X3.2