永川做网站的,政务网站建设交流发言,苏州中心有什么好玩的,给公司做兼职维护网站多少钱如有小伙伴想学习C语言基础#xff0c;可以进群731871503进行交流学习#xff0c;提升编程#xff0c;共同进步
问题描述
A、B、C、D、E这5个人合伙夜间捕鱼#xff0c;凌晨时都已经疲惫不堪#xff0c;于是各自在河边的树丛中找地方睡着了。第二天日上三竿时#xff0…如有小伙伴想学习C语言基础可以进群731871503进行交流学习提升编程共同进步
问题描述
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(n1、2、3、4、5)个人分鱼前鱼的总数则(Xn-1)/5必须为正整数否则不合题意。Xn-1)/5为正整数即(X〜l)mod50必须成立。
又根据题意应该有下面等式
X44(X5-1)/5 X34(X4-1)/5 X2-4(X3-1)/5 X14(X2-1)/5
则一旦给定X5就可以依次推算出X4、X3、X2和X1的值。要保证X5、X4、X3、X2和X1都满足条件(Xn-1)mod50此时的X5则为5个人合伙捕到的鱼的总条数。显然5个人合伙可能捕到的鱼的条数并不唯一但题目中强调了 “至少”合伙捕到的鱼此时题目的答案唯一。该问题可使用递归的方法求解。
程序设计
在main()函数中构建一个不定次数的do-while循环。定义变量x表示5个人合伙可能捕到的鱼的条数可以取x的最小值为6让x值逐渐增加x每一次取值都增加5直到找到一个符合问题要求的答案。由于题目中问“这5人至少合伙捕到多少条鱼”而我找到的第一个x值就是5个人至少捕到的鱼的总条数。
通过这个循环就可以对每一个的可能情况进行检查。当然是通过调用分鱼的递归函数来进行检查的。
分鱼的递归函数如下
fish()函数中包含了两个参数n和x。n表示参与分鱼的人数x表示n个人分鱼前鱼的总条数。这两个参数都是由main()函数中传递进来的。
根据前面的分析当n5时(x-1)mod50必须成立否则该x值不是满足题意的值退出fish()函数返回到main()函数main()函数中再传递新的x值到fish中进行检验。
如果(x-1)mod50条件成立则要判断n4时(x-1)mod50条件是否成立需要注意的是此时的形参x是4个人分鱼前鱼的总条数即f(5,x)递归调用f(4,(x-1)/5*4)。这样依次进行下去直到n1时(x-1)mod50条件仍成立则说明开始从main()函数中传递进来的x值是符合题意要求的一个值可以逐层从递归函数中返回每次返回值都为1直至返回到main()函数。
下面是完整的代码
#includestdio.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 i0, flag0, x;
do
{
ii1;
xi*51; /x最小值为6以后每次增加5/
if(fish(5, x)) /将x传入分鱼递归函数进行检验/
{
flag1; /找到第一个符合题意的x则置标志位为1/
printf(“五个人合伙捕到的鱼总数为%d\n”, x);
}
}
while(!flag); /未找到符合题意的x继续循环否则退出循环/
return 0;
}
运行结果
五个人合伙捕到的鱼总数为3121
知识点补充
本题还可以使用“递推法”来求解。下面先对递推法做下简介。
递推法利用问题本身所具有的递推关系来求解。所谓的递推关系指的是当得到问题规模为n-1的解后可以得出问题规模为n的解。因此从规模为0或1的解可以依次递推出任意规模的解。
下面是完整的代码
#includestdio.h
/分鱼递归函数/
int fish(int n, int x)
{
if((x-1)%5 0)
{
if(n1)
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)
{
for(i4; i0; i–)
{
if(fish[i1]%4!0)
break;
fish[i]fish[i1]*5/41;
if(fish[i]%5!1)
break;
}
if(i 0)
break;
fish[5]5;
}
for(i1; i5; 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
