递推题之分鱼问题
发布时间
阅读量:
阅读量
五个人(A,B,C,D,E)在河边夜间共同捕捞了一夜之后都睡着了。次日清晨五人依次醒来。A最先苏醒后将渔获物平均分成五堆并剩下一尾鱼,他便将多出的那一尾鱼放回河中并拿走自己的一份回家.随后B同样将现有的鱼群进行均分,多出一条也予以释放,并带走自己的那一份.接着C,D,E三人也按照同样的方法依次分配.请问他们至少一共捕获了多少尾鱼?每人起床时看到的鱼的数量又是多少?
依次输出A,B,C,D,E五个人醒来后看到的鱼的数目,每个一行。
输出
分析:
一个涉及递推关系的数学问题可用倒退法解决。设当前状态量为s_n ,则满足关系式:s_{n+1} = \frac{4}{5}(s_n - 1) 。经过代数变换后得到新序列a_{n+1} = \frac{5}{4} a_n + 1 ,并确保所有项均被4整除
AC代码如下:
#include "stdio.h"
int main()
{
int fish[10],i,j,k;
for (j=4;;j++)//试值
{
fish[0]=j; //fish[0]为所有人都走了以后剩下的鱼数
int count=0; //count记录整数项的数目
for (i=0;i<5;i++)
{
if (fish[i]/4*4==fish[i])
全部评论 (0)
还没有任何评论哟~
