面试题 | IT-北北报

蚂蚁过桥问题解析

2014/10 27 16:10

最近看了一道面试题,引起了我的兴趣,发现这道题涉及到很多数学知识,于是恶补了一下高中数学,汗,花了一些时间编写了这个动画。

题目

有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细,不能同时通过一只蚂蚁。开始时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最小时间和最大时间。

思路

    • 将木杆看成1至27的坐标, 5只蚂蚁分别在3, 7, 11, 17, 23的位置
    • 创建DirectionEnum{Right: 0,Left: 1}方向枚举
    • 创建Ant类, 蚂蚁可以爬行(go), 掉头(shift), 以及记录是否已经爬出的标记.
  • 创建Control类, 给定蚂蚁的初始方向, Control类可以计算出在这种初始方向下蚂蚁全部爬出需要的时间.
  • 创建执行类, 它给出蚂蚁初始方向的所有组合, 并使用Control执行得到所有时间, 选择最大值和最小值.

蚂蚁的初始方向非左即右,可以用00001, 10000(枚举组合)表示。5只蚂蚁, 2的5次方=32个组合,所以用0-31之间的整数的二进制刚好可以表示蚂蚁的初始方向。比如24(11000)分别与1, 2, 4, 8, 16相与,结果不为0,则蚂蚁方向向右,可得第4、5只蚂蚁方向向右。

Demo

动画演示:http://www.itbbb.com/my/ant.html

蚂蚁过桥问题,itbbb.com

蚂蚁过桥问题,itbbb.com

Javascript代码

在Demo页查看源代码即可获得



无觅相关文章插件,快速提升流量