乐者为王

Do one thing, and do it well.

逻辑题-共打了多少鱼

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

fishmen = [0, 0, 0, 0, 0]  # 渔民取走的鱼数
total = 1

while true do
  remain = total  # 渔民a醒来时鱼的总数
  5.times do |i|  # 5个渔民轮流取鱼
    break if remain % 5 != 1  # 如果不符合扔掉1条鱼后还能分成5份的条件，就枚举下个值
    fishmen[i] = (remain - 1) / 5  # 渔民取走的鱼数
    remain = 4 * fishmen[i]  # 渔民取走鱼后剩下的鱼数
  end
  break if fishmen[4] != 0  # 如果渔民e也取到了鱼，那么就得到了鱼的总数
  total += 1
end

puts total  # 结果是3121条鱼

上面的代码总过做了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

fishmen = Array.new(n, 0)
total = 11

while true do
  remain = total
  5.times do |i|
    break if remain % 5 != 1
    fishmen[i] = (remain - 1) / 5
    remain = 4 * fishmen[i]
  end
  break if fishmen[4] != 0
  total += 5
end

puts total

总的循环次数减少到1401次，减少了整整64%的循环。

推而广之：n个渔民打渔，每个渔民依次扔掉1条鱼后，把鱼分成n份，然后拿走其中一份，求最少打了多少条鱼？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

fishmen = Array.new(n, 0)
total = 2 * n + 1

while true do
  remain = total
  n.times do |i|
    break if remain % n != 1
    fishmen[i] = (remain - 1) / n
    remain = remain - 1 - fishmen[i]
  end
  break if fishmen[n - 1] != 0
  total += n
end

puts total

这下子无论多少个渔民打渔都可以用这段代码搞定了。我试了试9个渔民，发现竟然可以打近3.9亿条鱼，那得有多少鱼啊！另外，计算时间也明显开始变长了。不知道还能不能做更进一步的优化。如果你有更好的算法，请快点告诉我吧！

Comments