V 友们，考察你们计算能力的时候到了，给出一个递推题目的数值解

[mathzhaoliang]

有这么一个函数 f(x, y)，其中 x, y 都是非负整数，f(x,y) 的值为非负实数。

已知 f 满足如下条件：

1. f(x, 0) = 0 对任何 x 成立
2. f(0, y) = y 对任何 y 成立
3. f(x, y) = f(y-1, y) 对任何 x >= y > 0 成立
4. f(x, y) = [xf(x+1, y-1) + yf(x-1, y+1)] / (x+y) 对任何 y > x > 0 成立

请写出一个程序，可以计算 f(10000, 10000) 的值。

给出可行解的朋友可以留二维码地址，有红包打赏。

[mathzhaoliang]

@jingslunt 我出的问题是有确定可行的解的。

[dongyx]

有意思的问题。

我目前的思路是动态规划，计算顺序是一条对角线一条对角线地算，不断地填充左上三角。

算第 n 条对角线的时候，其实算一个一维的二阶递推式，需要 O(n)的时间，那么要算 f(n, n)需要 O(n^2)，感觉算 f(10000, 100000)有点吃力。我想看看能不能优化一下算一条对角线的做法，可惜系数不是常数，不然就可以矩阵快速幂了。

愿闻楼主高见。

[mathzhaoliang]

@dongyx 　如果问题只要求算 f(n, n) 的值，那么所有的 v_n=f(n,n) 之间满足一个递推关系，所以可以快速求解。
如果是计算任意 f(x, y) 的值，那确实就得逐个对角线求解了。这个推导过程可以见我的一篇文章
http://pywonderland.com/mabinogion-sheep-problem/

[ITJoker]

@mathzhaoliang 强

[ITJoker]

之前思路大概和你差不多，只不过列出来的公式不是这样，确切的是用我推导的那个公式答案算出来有点偏差，所以放弃了那个思路转拟合思路了，数学用的太少了，害😂

[hardwork]

每一层都是个方程组，10000 层是 9999 元一次方程组，每个方程组的参数需要上一个方程组的解
计算机递推只想到这种解法。
或者数学上能直接递推出公式？

[mathzhaoliang]

@hardwork 对，数学上可以找出递推公式。见 23 楼的链接。