五人分鱼问题 #

1. 五人分鱼问题介绍
2. 五人分鱼问题分析
3. 五人分鱼问题的实现

收获 #

学完本节内容，可以更深刻了解递推思想的使用。

五人分鱼问题介绍 #

问题描述：
A、B、C、D、E 五人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。
日上三杆，A 第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。
B 第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉拿走自己的一份。 。
C、D、E依次醒来，也按同样的方法拿鱼。
问他们台伙【至少】捕了多少条鱼?

五人分鱼问题分析 #

可以用顺推来解决这个问题。假设一共捕了x条鱼，在五人的分鱼过程中，需保证鱼的数量为正整数，那么有两个条件一定满足：
（1）当前轮被分的鱼能够正好分为5份：

（x-1）%5==0

（2）下一轮被分的鱼的数量为当前鱼数量的4/5，且为整数

x=4/5*(x-1)

五人分鱼问题的实现 #

python实现代码如下：

f=1 #假设初始状态有1条鱼
while True:
    total=f
    enough=True #初始认为鱼足够分
    #当五次循环都满足时，即可以求得f=1开始时依次增长的最小值
    for i in range(5):
        if (total-1)%5==0: #鱼的总数一定满足-1除5为整数
            total=4*(total-1)//5 #下一次鱼的数量为当前f的4/5
        else:
            enough=False #如果连续的5次循环有任意一次不满足，那么跳出循环
            break
    if enough==True:
        print('鱼的数量至少为%d'%(f))
        break
    f+=1 #下一次循环时鱼的数量+1

小结 #

结合五人分鱼问题的应用，进一步理解递推算法的思想
掌握五人分鱼问题的代码实现

习题 #

1. 习题1：画出五人分鱼问题的流程图
2. 习题2：假如现在有更多的渔民参与进来，8人进行鱼的分配，仍然满足上述情景，请问8人共捕捉到了至少多少条鱼？

–>