环球微动态丨递归公式算法分析_递归公式

1、这题看似简单，其实挺难的。

(资料图片仅供参考)

2、基本思路是先用图解法，头一排全0，头一列全2（除了第一排）然后按照，每个空白处数字等于前一列左上和右下的数字和写下来，结果是类似杨辉三角一样的阵列。

3、求f(2,n)就是求第二列的通项。

4、注意到第二排从第二列起，奇数列总是偶数列的2倍，因此只要求出偶数列的规律即可。

5、即 2， 6 ，20， 70， 252 。

6、的规律。

7、实际上这个看似简单，其实比较麻烦。

8、仔细展看会发现，An=2^(n/2)+f(2)*2^(n/2-1)+f(3)*2^(n/2-2)....其中f(n)是类似于多项式展开系数例如n=3时为1，2，2 ，n=5时为1， 4， 9， 14，14但是由于这里“类杨辉三角”不具有对称性，具体的n必须通过求解系数矩阵实现，算起来很麻烦。

9、但可以肯定地是An具有[2^(n/2)][K(n/2)]的形式，其中K(n/2)是以n/2为变量的n/2阶多项式。

10、具体的求解稍后我再算算，有可能会是个比较简单的式子（总觉得现在的方法小题大作了）。

本文就为大家分享到这里，希望小伙伴们会喜欢。

标签：