abcde五人打渔,打完睡觉,a先醒来,扔掉1条鱼,把剩下的分成5份,拿1份走了;b再醒来,也扔掉1条,把剩下的分成5份,拿1份走了;然后cde都按上面的方法取鱼。问他们最少打了多少条鱼?
渔民 | 醒来时鱼的总数 | 取走的鱼数 |
---|---|---|
a | x1 = x | (x1 - 1) / 5 |
b | x2 = 4 * (x1 - 1) / 5 | (x2 - 1) / 5 |
c | x3 = 4 * (x2 - 1) / 5 | (x3 - 1) / 5 |
d | x4 = 4 * (x3 - 1) / 5 | (x4 - 1) / 5 |
e | x5 = 4 * (x4 - 1) / 5 | (x5 - 1) / 5 |
由于扔掉1条鱼后,还能被分成5份,设渔民醒来时鱼的总数为remain,那么(remain - 1) % 5的值为0,即remain % 5的值为1。
最简单的方法就是枚举,最小值从1开始:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
上面的代码总过做了3901次循环,下面来做进一步的优化。
从表格可以看出,因为(x5 - 1) % 5 == 0,推导出x5 >= 6;又x1 % 5 == 1,因此x1的个位数必须是1或者6。所以,枚举的最小值可以从11开始,每次步进为5。优化后的代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
总的循环次数减少到1401次,减少了整整64%的循环。
推而广之:n个渔民打渔,每个渔民依次扔掉1条鱼后,把鱼分成n份,然后拿走其中一份,求最少打了多少条鱼?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
这下子无论多少个渔民打渔都可以用这段代码搞定了。我试了试9个渔民,发现竟然可以打近3.9亿条鱼,那得有多少鱼啊!另外,计算时间也明显开始变长了。不知道还能不能做更进一步的优化。如果你有更好的算法,请快点告诉我吧!