CircleRun
分类:Interview
一个朋友的产品助理面试题,让我帮他想一想。
题目
小李在400米长的环形跑道上练习长跑。上午8点20分开始,小李按逆时针方向出发,1分钟后,小李掉头按顺时针方向跑,又过了2分钟,小李又掉头按逆时针方向跑。如此,按1、2、3、4…分钟掉头返回跑。当小李按逆时针方向跑道出发点,又恰好该返回跑时,他的练习正好停止。如果假设小李一直保持匀速,每分钟跑120米,请问小李停止练习时是几点几分?
- 10点30分
- 11点30分
- 11时
- 11点45分
思路
首先申明,用穷举法是不可能在规定时间内解出的,而且穷举法有损智商… 思路局限在两条路上:
- 是不是有什么数值技巧,比如120*4-400+120=400/2,刚刚能凑出答案,但是看选项都是较大的数,如果不是很明显的巧合,这个方法应该行不通。又或者呈等差数列求和增长,这种方法也不是没有可能。
- 能不能将环形跑道转化为直线,超过400取余。但是取余之后的双反向(小明本身跑步要反向,超过400时一维坐标要反向)使计算变得麻烦。
解
最后没想到好的解决办法,只能通过程序求解:
#include <stdio.h>
const int runway = 400;
const int speed = 120;
int main()
{
bool clockwise = false; // true = clockwise, false = anticlockwise
int position = 0;
int run_time = 1;
int hour = 8;
int minute = 20;
while(1)
{
if (clockwise)
{
position += (speed * run_time);
position = (position % runway);
}
else
{
position -= (speed * run_time);
position = (position % runway);
}
minute += run_time;
if (minute >= 60)
{
hour += (minute / 60);
minute = (minute % 60);
}
clockwise = !clockwise;
if (position == 0 && clockwise == true)
{
break;
}
run_time++;
}
printf("STOP TIME : %d:%d\n", hour, minute);
return 0;
}
后经人指点,转化为一维坐标的方式可行,并且很重要的一点是超过400不取余,因为最后的结束判断只需满足两个条件:1. 400的整数倍;2. 单次跑的分钟数为奇数 即可。
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
120 | -120 | 240 | -240 | 360 | -360 | 480 | -480 | 600 |
故取120和400的最小公倍数1200,此时单次跑的分钟数为$ 1200/120 * 2 - 1 = 19 $,且刚好为奇数,所以总共需要$ (1 + 19) * 19 / 2 = 190 $,也即是11:30。
欢迎更强大脑提供思路:)
中间有个耐人寻味的小插曲 朋友说这个程序就是根据题目编出来的,它就可以解出来,即使自己不知道怎么解,我说,不完全对,是自己不知道怎么解,但是会有一个运算规则,根据这个规则计算总可以算出来,也就是所谓的穷举法,计算机只是帮助人更准确地执行这个计算过程罢了。但是可能他想说的更多的意思是,这个程序有了智能,可以代替人类思考。作为外行看起来可能是这样,但是即使是现在风靡的深度学习或者强化学习,都无法代替人类思考的过程,即使在专业细分领域已经很大程度的超过人类了,不过仍然不具备智能,都是根据既定的规则集而运算的结果,深度学习和强化学习只不过把指定规则从编码的过程移到了迭代优化参数的过程,名曰:训练学习。 所以,要通过图灵测试,实现通用人工智能,可能还需要全新的建模方式。