母牛养殖日记 - 类斐波那契数列通用递推公式的推导

---

1.引例：母牛的故事

在养殖类的斐波那契类型问题中，经常出现生长的月数改变的情况。比如这道题：
ACM2018

Problem Description

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0 < n < 55)，n的含义如题目中描述。

n = 0表示输入数据的结束，不做处理。


Output

对于每个测试实例，输出在第n年的时候母牛的数量。

每个输出占一行。

这道题的解析：

这里我们先不把母牛换成蛤蟆，看能否解决这个问题。

母牛出生的年份算作这头母牛的第1年而不是第0年；

总时间的进程始于第1年而不是第0年。

容易找到递推公式：

$$f(n) = \begin{cases} 1, & \text{n=1} \\\\ 2, & \text{n=2} \\\\ 3, & \text{n=3} \\\\ f(n-1)+f(n-3), & \text{n}\ge4 \\\\ \end{cases}$$

下面给出证明。

用 $d$ 表示成年母牛，用$y_i(i=1,2,3)$表示 $i$ 岁的小牛，则 $f(n)=d_{f(n)}+y_{3_f(n)}+y_{2_f(n)}+y_{1_f(n)}$。

又有 $f(n)=f(n-1)+d_{f(n)}$ ，因为$y_3$的小牛在变成母牛时会立即生牛。

又有 $d_{f(n)}=d_{f(n-1)}+y_{3_f(n-1)}$

又有 $y_{i_f(n)}=y_{i-1_{f(n-1)}}$

将 $n$ 替换为 $n-i(i=1,2)$，得：

$$\begin{split} f(n) & =f(n-1)+d_{f(n)}\\ & =f(n-1)+d_{f(n-1)}+y_{3_{f(n-1)}}\\ & =f(n-1)+d_{f(n-2)}+y_{3_{f(n-2)}}+y_{2_{f(n-2)}}\\ & =f(n-1)+(d_{f(n-3)}+y_{3_{f(n-3)}}+y_{2_{f(n-3)}}+y_{1_{f(n-3)}}\ \ )\\ & =f(n-1)+f(n-3) \end{split}$$

证明完毕。
由此可见，养殖母牛的问题与养殖兔子和蛤蟆一样，都是可以通过递推解决的。

在这个问题中，由于既要调用$f(n-1)$又要调用$f(n-3)$，所以递归很慢，时间复杂度高达 $O(2^n)$ ，故应采用递推的方式进行计算。

下面给出代码（C语言）：

#include <stdio.h>

int bear(int);
int main(void)
{
	int n=1;
	do
	{
		scanf("%d",&n);
		if(n)
		{
			printf("%d\n",bear(n));
		}
	}while(n);
	return 0;
}

int bear(int n)
{
	int i;
	int cows[55]={0,1,2,3};
	if(n<4)
	{
		return cows[n];
	}
	for(i=4;i<=n;i++)
	{
		cows[i]=cows[i-1]+cows[i-3];
	}
	return cows[n];

}

---

2.一般性结论

由上式可以看出，式子把 $d_{f(i)}$ 一直展开到含$y_{1_{f(j)}}$的项为止，一共进行了$m$ 步，其中$m$是未成年小牛的年龄种类数。本例中有3个年龄段的未成年小牛，所以$m=3$。而每展开一步，$d_{f(n)}$的展开式的下标都减1，所以，最终由$d_{f(i)}$展开的式子，就是$f(n-m)$。
因此，对于类斐波那契数列问题，其递推公式为：$f(n)=f(n-1)+f(n-m)$ ，其中$m$为未成年动物的年龄种类数。