【分享】递归分鱼方法

没头脑and不高兴

A、B、C、D、E这5个人合伙夜间捕鱼，凌晨时都已经疲惫不堪，于是各自在河边的树丛中找地方睡着了。第二天日上三竿时，A第一个醒来，他将鱼平分为5份，把多余的一条扔回河中，然后拿着自己的一份回家去了；B第二个醒来，但不知道A已经拿走了一份鱼，于是他将剩下的鱼平分为5份，扔掉多余的一条，然后只拿走了自己的一份；接着C、D、E依次醒来，也都按同样的办法分鱼。问这5人至少合伙捕到多少条鱼？每个人醒来后所看到的鱼是多少条？
问题分析
假设5个人合伙捕了x条鱼，则“A第一个醒来，他将鱼平分为5份，把多余的一条扔回河中，然后拿着自己的一份回家去了”之后，还剩下4(x-1)/5条鱼。

这里实际包含了一个隐含条件：假设Xn为第n(n=1、2、3、4、5)个人分鱼前鱼的总数，则(Xn-1)/5必须为正整数，否则不合题意。（Xn-1)/5为正整数即(X〜l)mod5=0必须成立。

又根据题意，应该有下面等式：
X4=4(X5-1)/5
X3=4(X4-1)/5
X2-4(X3-1)/5
X1=4(X2-1)/5

则一旦给定X5，就可以依次推算出X4、X3、X2和X1的值。要保证X5、X4、X3、X2和X1都满足条件(Xn-1)mod5=0，此时的X5则为5个人合伙捕到的鱼的总条数。显然，5个人合伙可能捕到的鱼的条数并不唯一，但题目中强调了 “至少”合伙捕到的鱼，此时题目的答案唯一。该问题可使用递归的方法求解。
程序设计
在main()函数中构建一个不定次数的do-while循环。定义变量x表示5个人合伙可能捕到的鱼的条数，可以取x的最小值为6，让x值逐渐增加，x每一次取值，都增加5，直到找到一个符合问题要求的答案。由于题目中问“这5人至少合伙捕到多少条鱼”，而我找到的第一个x值就是5个人至少捕到的鱼的总条数。

通过这个循环，就可以对每一个的可能情况进行检查。当然，是通过调用分鱼的递归函数来进行检查的。

分鱼的递归函数如下：
fish()函数中包含了两个参数：n和x。n表示参与分鱼的人数，x表示n个人分鱼前鱼的总条数。这两个参数都是由main()函数中传递进来的。

根据前面的分析，当n=5时，(x-1)mod5==0必须成立，否则该x值不是满足题意的值，退出fish()函数，返回到main()函数，main()函数中再传递新的x值到fish中进行检验。如果(x-1)mod5==0条件成立，则要判断n=4时，(x-1)mod5=0条件是否成立，需要注意的是，此时的形参x是4个人分鱼前鱼的总条数，即f(5,x)递归调用f(4,(x-1)/5*4)。这样依次进行下去，直到n=1时，(x-1)mod5==0条件仍成立，则说明开始从main()函数中传递进来的x值是符合题意要求的一个值，可以逐层从递归函数中返回，每次返回值都为1，直至返回到main()函数。

[Asm] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include<stdio.h> /*分鱼递归函数*/ int fish(int n, int x) { if((x-1)%5 == 0) { if(n == 1) return 1; /*递归出口*/ else return fish(n-1, (x-1)/5*4); /*递归调用*/ } return 0; /*x不是符合题意的解，返回0*/ } int main() { int i=0, flag=0, x; do { i=i+1; x=i*5+1; /*x最小值为6，以后每次增加5*/ if(fish(5, x)) /*将x传入分鱼递归函数进行检验*/ { flag=1; /*找到第一个符合题意的x则置标志位为1*/ printf("五个人合伙捕到的鱼总数为%d\n", x); } } while(!flag); /*未找到符合题意的x，继续循环，否则退出循环*/ return 0; }

原文：https://blog.csdn.net/as472780551/article/details/75804024

一点点窃爱

RoyPenn 发表于 2019-3-21 10:08
[mw_shl_code=python,true]def main():
    fish_number = 1
    while True:

我想爆了脑子都没想出来，不用函数能做么？

yhgfwly007

感谢分享，思路清晰

忘记你

学习了，，思路清晰

jiayaozhuce

学习了，，思路清晰

han-wang11

这道题如果不用编程，可以用如下思路解题：
1、每次分完都多一条，假设一开始5n+1，即扔一条，拿走n条，可视为拿走（n + 1）条；
2、构建出虚拟的4条鱼，记为大写的“四”，则初始变为（5n+1+四）= 5n + 5 = 5 (n + 1)，显然能被5整除，除以5可得n+1，恰好被A拿走。剩4n+四（虚拟出来的四）条；
3、由题可知，4n除以5余1，加上虚拟出来的四，可以整除5，假设4n = 5m +1，则4n+四=5（m+1）；B拿走m条扔一条，可视为拿走（m+1）条；
4、以此类推，到最后E分鱼的时候，加上虚拟的四条仍然可以整除5，这四条一直存在于分完后剩下的鱼里，假设原来有x条，则x+四至少可以连续整除5有5次，因此x+4=y（5^5），当y=1时，x有最小值为3121.

没头脑and不高兴

liphily 发表于 2019-3-21 09:11
有一种清新脱俗的感觉~
很多题目都是难在了数学，直接新人跑路了。。。。

对，好多题都是数学方法不理解，弄得人写不下来！

龙之觉醒

感谢分享，思路清晰

RoyPenn

[Python] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17

def main():     fish_number = 1     while True:         n,flag = fish_number,True         for x in range(5):             if (n - 1) % 5 == 0:                 n = (n - 1) // 5 * 4             else:                 flag = False                 break         if flag:             print(fish_number)             break         fish_number += 1   if __name__ == "__main__":     main()

雨落荒原

思路清晰 感谢分享