c语⾔5个⼈分鱼程序题,C语⾔递归解决5⼈分鱼问题
问题描述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()函数。
下⾯是完整的代码：
#include
/*分鱼递归函数*/
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;
}
运⾏结果：
五个⼈合伙捕到的鱼总数为3121
知识点补充
本题还可以使⽤“递推法”来求解。下⾯先对递推法做下简介。
递推法：利⽤问题本⾝所具有的递推关系来求解。所谓的递推关系指的是：当得到问题规模为n-1的解后，可以得出问题规模为n的解。因此，从规模为0或1的解可以依次递推出任意规模的解。
下⾯是完整的代码：
#include
/*分鱼递归函数*/
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 fish[6], i;
fish[5]=6;
while(1)
{
c语言编写递归函数for(i=4; i>0; i--)
{
if(fish[i+1]%4!=0)
break;
fish[i]=fish[i+1]*5/4+1;
if(fish[i]%5!=1)
break;
}
if(i == 0)
break;
fish[5]+=5;
}
for(i=1; i<=5; i++)
printf("fish[%d]=%d\n", i, fish[i]); return 0;
}
运⾏结果：
fish[1]=3121
fish[2]=2496 fish[3]=1996 fish[4]=1596 fish[5]=1276

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。