黑马程序员技术交流社区

标题: java解决百度面试题—蚂蚁爬木杆问题 [打印本页]
作者: as604049322    时间: 2015-3-17 00:25
标题: java解决百度面试题—蚂蚁爬木杆问题

[code]package com.itheima;
/**
* 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，
* 它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。 假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
*
* 分析： 当两只蚂蚁都掉头以后，我们把 a 蚂蚁看成 b 蚂蚁，把 b 蚂蚁看成 a 蚂蚁，
* 若不考虑它们的名字a，b，其实这和两只蚂蚁“擦肩而过”有什么区别呢？ 也就是说，蚂蚁的碰撞根本不会影响“宏观”上五只蚂蚁的运动情况。
*
* @author 旋风铭
*
*/
public class AntOfTime {
作者: as604049322    时间: 2015-3-17 00:27
  1. package com.itheima;

  3. /**
  4. * 有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
  5. * 木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，
  6. * 它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。 假设蚂蚁们每秒钟可以走一厘米的距离。
  7. * 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。
  8. *
  9. * 分析： 当两只蚂蚁都掉头以后，我们把 a 蚂蚁看成 b 蚂蚁，把 b 蚂蚁看成 a 蚂蚁，
  10. * 若不考虑它们的名字a，b，其实这和两只蚂蚁“擦肩而过”有什么区别呢？ 也就是说，蚂蚁的碰撞根本不会影响“宏观”上五只蚂蚁的运动情况。
  11. *
  12. * @author 旋风铭
  13. *
  14. */
  15. public class AntOfTime {
  16.         public static void main(String[] args) {
  17.                 int[] ant;
  18.                 int time;
  19.                 boolean[] left = { true, true, true, true, true };// 五只蚂蚁的方向是否向左
  20.                 boolean[] stillin;// 五只蚂蚁是否还在木杆上
  21.                 int mintime = 10000;
  22.                 int maxTime = 0;
  23.                 String minStr = null;
  24.                 String maxStr = null;
  25.                 String str = null;
  26.                 for (int i = 1; i < Math.pow(2, 5); i++) {
  27.                         //初始化
  28.                         time = 0;
  29.                         ant = new int[] { 3, 7, 11, 17, 23 };// 五只蚂蚁的位置
  30.                         stillin = new boolean[] { true, true, true, true, true };// 五只蚂蚁是否还在木杆上
  31.                        
  32.                         //产生代表蚂蚁方向的文本，（0代表向左，1代表向右）
  33.                         str = Integer.toBinaryString(i);
  34.                         str = str.replaceAll("([01]+)", "0000$1");
  35.                         str = str.replaceAll("0*([01]{5})", "$1");
  36.                        
  37.                         //下面的while循环模拟了五只蚂蚁从初始状态到全部离开木杆的全过程
  38.                         while (true) {
  39.                                 //str的五个字符分别代表了五只蚂蚁的运动方向
  40.                                 if (str.charAt(0) == '0')
  41.                                         ant[0]--;
  42.                                 else
  43.                                         ant[0]++;
  44.                                 if (str.charAt(1) == '0')
  45.                                         ant[1]--;
  46.                                 else
  47.                                         ant[1]++;
  48.                                 if (str.charAt(2) == '0')
  49.                                         ant[2]--;
  50.                                 else
  51.                                         ant[2]++;
  52.                                 if (str.charAt(3) == '0')
  53.                                         ant[3]--;
  54.                                 else
  55.                                         ant[3]++;
  56.                                 if (str.charAt(4) == '0')
  57.                                         ant[4]--;
  58.                                 else
  59.                                         ant[4]++;
  60.                                 //此时运动完成，耗时1秒
  61.                                 time++;
  62.                                
  63.                                 //判断蚂蚁是否已经离开木杆并记录
  64.                                 if (ant[0] <= 0 || ant[0] >= 27)
  65.                                         stillin[0] = false;
  66.                                 if (ant[1] <= 0 || ant[1] >= 27)
  67.                                         stillin[1] = false;
  68.                                 if (ant[2] <= 0 || ant[2] >= 27)
  69.                                         stillin[2] = false;
  70.                                 if (ant[3] <= 0 || ant[3] >= 27)
  71.                                         stillin[3] = false;
  72.                                 if (ant[4] <= 0 || ant[4] >= 27)
  73.                                         stillin[4] = false;
  74.                                
  75.                                 //如果全部都已经离开木杆则退出循环
  76.                                 boolean flag = false;
  77.                                 for (int j = 0; j < stillin.length; j++) {
  78.                                         flag = flag || stillin[j];
  79.                                 }
  80.                                 if (!flag)
  81.                                         break;
  82.                         }
  83.                        
  84.                         //获得该状态下蚂蚁全部离开所需要的时间
  85.                         if (maxTime < time) {
  86.                                 maxTime = time;
  87.                                 maxStr = str;
  88.                         }
  89.                         if (mintime > time) {
  90.                                 mintime = time;
  91.                                 minStr = str;
  92.                         }
  93.                 }
  94.                 System.out.println("最短时间:" + mintime + ",str=" + minStr);
  95.                 System.out.println("最长时间:" + maxTime + ",str=" + maxStr);

  97.         }
  98. }
复制代码




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