C语言经典例80-猴子分桃

约定不等于承诺〃 2023-07-06 13:20 11阅读 0赞

### 目录 ###

*  1 题目
 *  2 分析
 *  3 实现
 *  4 运行结果

# 1 题目 #

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

# 2 分析 #

设原来至少有  x x x 个桃子：

1.  第一只猴子拿走一份后，剩余的 4 4 4份桃子总数为 a a a， a = 4 / 5 ∗ ( x − 1 ) a=4/5\*(x-1) a=4/5∗(x−1)
2.  第二只猴子拿走一份后，剩余的 4 4 4份桃子总数为 b b b， b = 4 / 5 ∗ ( a − 1 ) b=4/5\*(a-1) b=4/5∗(a−1)
3.  第三只猴子拿走一份后，剩余的 4 4 4份桃子总数为 c c c， c = 4 / 5 ∗ ( b − 1 ) c=4/5\*(b-1) c=4/5∗(b−1)
4.  第四只猴子拿走一份后，剩余的 4 4 4份桃子总数为 d d d， d = 4 / 5 ∗ ( c − 1 ) d=4/5\*(c-1) d=4/5∗(c−1)
5.  第五只猴子拿走一份后，剩余的 4 4 4份桃子总数为 e e e， e = 4 / 5 ∗ ( d − 1 ) e=4/5\*(d-1) e=4/5∗(d−1)

求  x x x 就是要从  e e e 反推到  x x x，本题限定了要求桃子最少的情况，那么当轮到第五只猴子时，要保证最少，则一开始设  e = 4 e = 4 e=4 即此时剩余4份每份只有1个桃子，然后利用该假设进行向上递归计算每轮剩余的桃子个数，判断每轮剩余桃子个数能否被4整除，若中间有一轮不能被4整除，则一开始  e ! = 4 e!=4 e!=4，则用  2 ∗ 4 2\*4 2∗4重新尝试，每轮都要乘 4 4 4是因为，每轮都要保证能被4整除。

# 3 实现 #

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    { 
        int x; // 桃子总数
    	int i = 0; // 循环轮数
    	int j = 1; // 暂存每轮尝试的起始e的倍数
        while (i < 5) {  // 一共五只猴子，五轮循环
            x = 4 * j; // 拟定起始e的值
            for (i = 0; i < 5; i++) { 
                if (x % 4 != 0) {  // 最后一只猴子待分配的桃子数一定能被4整除
    				break; // 若在5轮中某一论不能被4整除，则要重新更换起始e的值
    			}
                x = (x/4)*5+1; // 向上递归累加
            }
            j++; // 通过递增j来更换4的倍数，从而重新更换起始e的值
        }
        printf("%d\n", x);
        return 0;
    }

# 4 运行结果 #

3121