乐者为王

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