蚂蚁走木棍

| Comments

蚂蚁走木棍

百度面试题

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

简化问题

看上去很复杂,但可以这样看问题:假设可以过两只蚂蚁,那么蚂蚁相撞两蚂蚁调头相当于不调头继续前进。 这样问题就可以迎刃而解了。最大的时间就是每只蚂蚁往远端前进(算出来是离一端最远的那只),最小的时间就是每只蚂蚁往近端前进(算出来是最后爬出来的那只)。 这样,最大时间就是3厘米的那只,耗时24秒。最小时间是11厘米那只,它最快要11秒才能出来。

小学竞赛题

这个题目让我想起一个竞赛题,大概是说,有两个人相距x米迎面走来(速度已知),其中有只狗在他们之间来回跑(狗的速度较快), 求两人相逢的时候,狗跑了多长距离。如果着眼点在狗每次跑动的距离,那一样非常复杂。如果着眼于时间, 则问题也就迎刃而解了。话说回来,类似的这些题目,更像是智力题而非编程题。

Comments