经典算法题-猴子分桃

经典算法题-猴子分桃

引用

CSDN

1.

https://blog.csdn.net/vvilkim/article/details/145576412

海滩上有一堆桃子，五只猴子来分。第一只猴子把这堆桃子平均分为五份，多了一个，这只猴子把多的一个扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一个，它同样把多的一个扔入海中，拿走了一份，第三、第四、第五只猴子都是这样做的，问海滩上原来最少有多少个桃子？

思路一：

假设原来有桃子数量peaches;每次剩余桃子数量temp_peaches;

由于每次剩余的桃子都可以被分成5份且多一个（前四次），所以temp_peaches满足 temp_peaches%5==1，若满足，则更新剩余桃子数量 temp_peaches = （temp_peaches - 1）// 5 * 4，直到第五只猴子，如果五只猴子都符合条件，表示找到答案；

peaches取值由1往上递增，直到满足上述条件，此时桃子数量最少

程序示例：

def calculate_min_peaches():
    peaches = 0
    while True:
        peaches += 1
        count = 0
        temp_peaches = peaches
        for i in range(5):
            if temp_peaches % 5 != 1:  # 判断是否符合第一只猴子拿走后的情况
                break
            count += 1
            temp_peaches = (temp_peaches - 1) // 5 * 4  # 更新剩余桃子数量
        if count == 5:  # 如果五只猴子都符合条件，表示找到答案
            return peaches
min_peaches = calculate_min_peaches()
print("海滩上原来最少有{}个桃子".format(min_peaches))  

程序结果：

思路二：

假设第五只猴子分到的桃子数量是x；则可推算出第五只猴子分桃时桃子数量 t = 5*x+1；

由于每次分完都会留下四份，所以剩下数量应是4的倍数，即 t % 4 == 0，若满足，则往上继续推算，得到第一只猴子分桃时的数量，即一开始桃子的数量；

x取值由1往上递增，直到满足上述条件，此时桃子数量最少

程序示例：

def find_minimum_peaches():
    # 假设第五只猴子拿到的是1个桃子
    x = 1
    # 倒推计算原来的桃子数量
    while True:
        t = 5 * x + 1  # 第五只猴子分桃时，剩下的桃子的数量
        index = 1
        # 由于每次分完都剩四份，所以每次剩下数量应是4的倍数
        for _ in range(4):
            if t % 4 != 0:
                break
            t = t // 4 * 5 + 1
        else:
            # 如果for循环没有被break，则说明满足条件
            return t
        x += 1
# 找到最少的桃子数量
minimum_peaches = find_minimum_peaches()
print("海滩上原来最少有{}个桃子。".format(minimum_peaches))  

程序结果：