在百度贴吧看到的问题，基础问题是这样的：有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁。
他们只会朝前走或掉头，但不会后退。木杆很细，不能允许两只蚂蚁同时通过。
当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走。假设蚂蚁们每秒钟可以走1厘米的距离。
开始时，蚂蚁的头朝向左还是右是任意的。求所有蚂蚁都离开木杆的最小时间和最大时间。

我的解答是这样的，求优化。我写了一个蚂蚁的类，并且在Main方法中用数组遍历他们，但是总是感觉代码很无力。不够简洁。下面是main方法：

1. static void Main(string[] args)
   
2.         {
   
3.             //我只求出最短时间，而且是给定初始值，想求一个方法，可以随机初始值，且可以同时求出最大最小值
   
4.             Ant[] ant = new Ant[5];//初始化
   
5.             ant[0]=new Ant(3,-1);
   
6.             ant[1]=new Ant(7,-1);
   
7.             ant[2]=new Ant(11,-1);
   
8.             ant[3]=new Ant(17,1);
   
9.             ant[4]=new Ant(23,1);
   
10.             while (true)
    
11.             {
    
12.                 bool[] b = new bool[ant.Length];//判断是否结束行走
    
13.                 for (int i = 0; i < ant.Length; i++)
    
14.                 {
    
15.                     ant.walk();
    
16.                     b = (ant[0].position == 0) || (ant[0].position == 27);
    
17.                 }
    
18.                 if (b[0] && b[1] && b[2] && b[3] && b[4])
    
19.                 {
    
20.                     break;
    
21.                 }
    
22.                 for (int j = 0; j < ant.Length - 1; j++)//判断是否碰面
    
23.                 {
    
24.                     if (ant[j].position > ant[j + 1].position)
    
25.                     {
    
26.                         ant[j].back();
    
27.                         ant[j + 1].back();
    
28.                     }
    
29.                 }
    
30.             }
    
31.             Console.WriteLine("蚂蚁总共走过了{0}", ant[0].time);
    
32.             Console.ReadKey();
    
33.         }
    

复制代码

下面是简单的Ant类：

1. class Ant
   
2.     {
   
3.         public double position;//位置
   
4.         public double direction;//方向
   
5.         public double time;
   
6.         public Ant(double pos, double dir)
   
7.         {
   
8.             position = pos;
   
9.             direction = dir;
   
10.         }
    
11.         public void walk()
    
12.         {
    
13.             if ((position > 0) && (position < 27))
    
14.             {
    
15.                 position = position + direction;
    
16.             }
    
17.             time = time + 1;
    
18. }

复制代码

已经给出确定数值了,没戏要那么麻烦吧...

1. namespace _蚂蚁爬杆问题
   
2. {
   
3.     class Program
   
4.     {
   
5.         /// <summary>
   
6.         ///有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁。
   
7.         ///他们只会朝前走或掉头，但不会后退。木杆很细，不能允许两只蚂蚁同时通过。
   
8.         ///当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走。假设蚂蚁们每秒钟可以走1厘米的距离。
   
9.         ///开始时，蚂蚁的头朝向左还是右是任意的。求所有蚂蚁都离开木杆的最小时间和最大时间。
   
10.         /// </summary>
    
11.         /// <param name="args"></param>
    
12.         static void Main(string[] args)
    
13.         {
    
14.             //不难观察.3,7,11,17,23均为奇数,其两两相差均为偶数.
    
15.             //所以使用的数据类型只需使用int即可.
    
16.             //定义木杆的总长度
    
17.             int total=27;
    
18.             //定义至左至右每一只蚂蚁所在的位置
    
19.             int first=3;
    
20.             int second=7;
    
21.             int third=11;
    
22.             int fourth=17;
    
23.             int fifth=23;
    
24.             //计算最小时间
    
25.             //不难看出,3,7,11,17,23均为质数.所以蚂蚁走过的最小时间,即为蚂蚁之间相遇次数为0时.
    
26.             //所以蚂蚁离开的最小时间就是第三只蚂蚁离开木杆的最小时间.
    
27.             //[蚂蚁们每秒钟可以走1厘米的距离。]即蚂蚁爬过的距离与时间相等.
    
28.             //(很明显可以看出是第三只,想排一下其他四只也无所谓.)
    
29.             int min=Math.Min(third,total-third);
    
30.             Console.WriteLine("蚂蚁离开木杆的最小时间为{0}秒.",min);
    
31.             //计算最大时间
    
32.             //[木杆很细，不能允许两只蚂蚁同时通过。当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走。]
    
33.             //可以这样想,如果不考虑木杆的宽度与蚂蚁的身份,两只蚂蚁相遇后掉头与继续向前爬没有区别.
    
34.             //因为蚂蚁的长度不再考虑范围之内,就当它们相遇后会灵魂交换,该向左还向左,该向右还向右.
    
35.             //所以,最大时间即为[五只蚂蚁一直爬(不掉头)]最后一只蚂蚁离开木杆的时间.
    
36.             //先求每一只蚂蚁离开木杆的最大时间
    
37.             first = Math.Max(first, total - first);
    
38.             second = Math.Max(second, total - second);
    
39.             third = Math.Max(third, total - third);
    
40.             fourth = Math.Max(fourth, total - fourth);
    
41.             fifth = Math.Max(fifth, total - fifth);
    
42.             //求出5数中最大的值,就是最大的时间.不想用别的方法了,数也不多,无脑排吧.
    
43.             int max1 = Math.Max(first, second);
    
44.             int max2 = Math.Max(third, fourth);
    
45.             int max = Math.Max(max1, max2);
    
46.             max = Math.Max(max, fifth);
    
47.             Console.WriteLine("蚂蚁离开木杆的最大时间为{0}秒.", max);
    
48.             Console.ReadKey();
    
49.         }
    
50.     }
    
51. }

复制代码

确实是我考虑的不够多，我只考虑了最小时间的问题，没有考虑碰面与不碰面的问题，

但是我觉得这个问题还可以继续优化，比方说随机数列，这个是其一。
其二是如果求爬行距离和折返次数用单纯的数组就难以完成了。其三是如果每个蚂蚁的速度如果不同，碰面的论断就不成立了。

不过你能考虑到碰面的问题确实比我想的多，那我就结了这个帖子了。但求继续优化，比如说随机数的问题。（包括优化问题本身）

这已经不是优化的问题了..
1)先说随机数列,你所说的随机数列是不是说蚂蚁的位置随机..
题目所求最小时间和最大时间,很明显,无论是最小时间还是最大时间,都是由最后一只走出木杆的蚂蚁来确定,其他蚂蚁不用考虑.木杆有27cm,我们假设木杆上爬满了28只蚂蚁(0~28),那么最小时间为14秒,最大时间为27秒.由此可见,题目所求的时间根本不是由蚂蚁的数量来决定的,是由其中一只蚂蚁所处的位置与木杆的长度来决定的.

zhl406893081 发表于 2014-3-12 19:35
这已经不是优化的问题了..
1)先说随机数列,你所说的随机数列是不是说蚂蚁的位置随机..
题目所求最小时间和 ...

确实如果每只蚂蚁都一样的话你的解非常精确，但是如果蚂蚁的速度不一样，且蚂蚁的位置随机的话用单纯数学分析就很难完成(我不是说不可以完成)。这个题确实出的有问题，但是我还是希望和大家一起把这个题的内涵挖掘出来。

刚才没打完就发了,不好意思啊.
1)先说随机数列,你所说的随机数列是不是说蚂蚁的位置随机..
题目所求最小时间和最大时间,很明显,无论是最小时间还是最大时间,都是由最后一只走出木杆的蚂蚁来确定,其他蚂蚁不用考虑.木杆有27cm,我们假设木杆上爬满了26只蚂蚁(1~26),那么最小时间为14秒,最大时间为27秒.由此可见,题目所求的时间根本不是由蚂蚁的数量来决定的,是由其中一只蚂蚁所处的位置与木杆的长度来决定的.

假设木杆长度为n,蚂蚁的个数为m(m<=n-1),那么最小时间的最好情况为m秒,最坏情况为(n+1)/2.最大时间的最坏情况为n秒,最大时间的最好情况为(n+1)/2秒.

2)求爬行距离和碰头次数

爬行距离好求,位置相加加即可求得,即每只蚂蚁max(位置,木杆总长-位置)相累加就是爬过的总距离.

碰头也好说,5个数,每个数不是++就是--,每次循环过后相邻的两个数作比较,如果相同,则记录次数+1,之后++变成--(--变成++).

3)速度问题

你要说速度就变成追击问题了...这个没想法,我认为速度必须相同,速度如果不一样这个问题是要出错的,最中间蚂蚁速度趋于无穷大,其他蚂蚁速度趋于无穷小,这题做不完啦.

这题要改只能是让用户输入木杆的长度以及蚂蚁的位置,输入的数字统统除以2,最后比大小,最大的数可以算出最小时间,最小的数可以算出最大时间.

无论如何还是感谢你的回答，希望在黑马当中可以碰到你。首先距离问题可以通过时间乘以速度来解决，其次我想说速度问题是可以解决的（当然速度不能是无穷大）。速度不一致的时候，碰面好说，依旧像原来一样双方掉头，而追击的时候，前面的蚂蚁保持原来方向，后面的蚂蚁掉头。只是求解的方法大约需要某个大神了。等我申请完黑马的入学我会回来研究这个问题的。

不谢,我也是在努力考13期.