V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
mathzhaoliang
V2EX  ›  奇思妙想

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

  •  
  •   mathzhaoliang · 2020-08-11 21:54:12 +08:00 · 3310 次点击
    这是一个创建于 1325 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有这么一个函数 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) 的值。

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

    27 条回复    2020-08-19 21:32:50 +08:00
    huabalance
        1
    huabalance  
       2020-08-12 11:54:40 +08:00
    `f(x, y) = [xf(x+1, y-1) + yf(x-1, y+1)] / (x+y) 对任何 y > x > 0 成立`

    这一条会导致无尽的循环。例子:x=2, y=3
    rekulas
        2
    rekulas  
       2020-08-12 13:13:05 +08:00
    @huabalance 2,3 还可以通过变形计算出来,但是还有很多这样的组合,可能不能通过常规递归方法来计算
    mathzhaoliang
        3
    mathzhaoliang  
    OP
       2020-08-12 14:24:00 +08:00
    @huabalance 你要是直接调用递归是不行的。实际上 f(2,3) 可以解方程组解出来。
    huabalance
        4
    huabalance  
       2020-08-12 17:07:47 +08:00
    @rekulas
    @mathzhaoliang 受教了二位。。还有这样的思路。
    hebin
        5
    hebin  
       2020-08-12 22:58:02 +08:00 via iPhone
    没有很懂 第三个不是可以推出来 f x y = f 0 y = y , 第四个又能随便算出如 f 1 2 != 2,
    mathzhaoliang
        6
    mathzhaoliang  
    OP
       2020-08-13 11:08:01 +08:00
    @hebin 第三个关系式到了 f(y-1, y) 以后,由于 y-1 < y 就不满足 3 了。
    mathzhaoliang
        8
    mathzhaoliang  
    OP
       2020-08-13 15:29:58 +08:00
    @no1xsyzy 虽然我没看懂,但是看到了求逆和计算矩阵乘法,感觉思路有点靠谱。但是对 n=10000 的情形运行太慢了。
    mathzhaoliang
        9
    mathzhaoliang  
    OP
       2020-08-13 16:26:57 +08:00
    @no1xsyzy 你的程序逻辑是对的,就是有点太慢了,对 x = y = 10000 的情形跑不动。
    xml123
        10
    xml123  
       2020-08-13 22:44:32 +08:00
    只能算个 x=y=1000 的规模
    ITJoker
        11
    ITJoker  
       2020-08-14 23:47:01 +08:00
    我有个思路,前面的老哥写的代码虽然遍历可能太慢。
    但是如果我们另寻他路,我不知道可不可以,
    首先先生成( 0,100 )的数字
    求出 f(x,x)的值,例:f(1,1) , f(2,2).....
    最后生成的图像如下
    ![Figure_1.png]( https://i.loli.net/2020/08/14/SLHFJev5QE6Mquj.png)
    因此,这是个一次函数
    然后拟合结果为:```y = 1.856 x - 3.798```
    虽然我觉得这个答案可能不大准确,但是应该算出来的答案误差也不是很大,拿来当估值也是可以的。XD
    ITJoker
        12
    ITJoker  
       2020-08-14 23:47:59 +08:00
    ```y = 1.85631216*x -3.79846311```
    ITJoker
        13
    ITJoker  
       2020-08-15 00:07:37 +08:00
    之前的有点问题,用哪个老兄计算的方法,最多可以计算到 109
    我重新拟合了下:y = (1.86313312*x -4.0335139)
    误差范围: (1.2019039967254912,1.2535931255835067)
    ITJoker
        14
    ITJoker  
       2020-08-15 00:17:09 +08:00
    正确误差范围:(-0.8856246689377087,4.0335139)
    太乌龙了,代码写错了|||
    mathzhaoliang
        15
    mathzhaoliang  
    OP
       2020-08-15 09:28:14 +08:00
    @ITJoker 这是一份我写的代码,使用了一个递推关系:

    令 v_k = f(k, k), p_k = \binom{2k}{k} / 2^{2k},则

    v_{k+1} = (1- p_k) / (1 + p_k) v_k + (2k+1) * (2p_k) / (1+P_k)

    ```python
    from decimal import *

    pi = 3.14159265358979

    getcontext().prec = 20

    def solve_sheep(n):
    p = [0 for _ in range(n + 1)]
    v = [0 for _ in range(n + 1)]
    v[1] = 1
    p[1] = Decimal(0.5)
    for k in range(2, n + 1):
    p[k] = (1 - 1 / Decimal(2 * k)) * p[k - 1]
    for k in range(1, n):
    w = (1 - p[k]) / (1 + p[k])
    v[k + 1] = w * v[k] + (1 - w) * (2 * k + 1)

    return v[n]

    def estimate_sheep(n):
    return 2 * n + pi / 4 - (pi * n)**0.5

    print(solve_sheep(10000))
    print(estimate_sheep(10000))
    ```
    spcharc
        16
    spcharc  
       2020-08-16 17:55:20 +08:00
    得到了 f(10000,10000)精确值,存入文件一看有 60M 大,也是无语。试着让 Python 读出来再 eval(),结果一个小时过去都没 load 完…
    spcharc
        17
    spcharc  
       2020-08-16 18:36:01 +08:00
    @spcharc #16
    使用的是楼主提供的递推程序。完全看不出为什么会有这个递推关系
    jingslunt
        18
    jingslunt  
       2020-08-17 08:56:22 +08:00 via Android
    我也出道估计你解不出来的题
    odd(n) :
    while(n>1)
    if(odd(n))
    n=3*n+1;
    else
    n=n/2;
    其中 odd(n)为奇数。
    找出这个递归函数最终值不为 1 的那个 n 值。
    jingslunt
        19
    jingslunt  
       2020-08-17 09:02:46 +08:00 via Android
    其中 odd(n)为奇数就执行 if 下的赋值,偶数执行 else 下的赋值,找出最终递归值不唯一的那个 n
    mathzhaoliang
        20
    mathzhaoliang  
    OP
       2020-08-17 09:55:46 +08:00
    @spcharc 你运行的代码肯定做了修改,只计算 f(10000, 10000) 的值一秒都用不了。
    mathzhaoliang
        21
    mathzhaoliang  
    OP
       2020-08-17 09:57:01 +08:00
    @jingslunt 我出的问题是有确定可行的解的。
    dongyx
        22
    dongyx  
       2020-08-17 17:16:06 +08:00
    有意思的问题。

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

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

    愿闻楼主高见。
    mathzhaoliang
        23
    mathzhaoliang  
    OP
       2020-08-17 22:31:44 +08:00
    @dongyx  如果问题只要求算 f(n, n) 的值,那么所有的 v_n=f(n,n) 之间满足一个递推关系,所以可以快速求解。
    如果是计算任意 f(x, y) 的值,那确实就得逐个对角线求解了。这个推导过程可以见我的一篇文章
    http://pywonderland.com/mabinogion-sheep-problem/
    ITJoker
        24
    ITJoker  
       2020-08-18 00:16:54 +08:00
    ITJoker
        25
    ITJoker  
       2020-08-18 00:33:09 +08:00
    之前思路大概和你差不多,只不过列出来的公式不是这样,确切的是用我推导的那个公式答案算出来有点偏差,所以放弃了那个思路转拟合思路了,数学用的太少了,害😂
    hardwork
        26
    hardwork  
       2020-08-19 21:31:32 +08:00
    每一层都是个方程组,10000 层是 9999 元一次方程组,每个方程组的参数需要上一个方程组的解
    计算机递推只想到这种解法。
    或者数学上能直接递推出公式?
    mathzhaoliang
        27
    mathzhaoliang  
    OP
       2020-08-19 21:32:50 +08:00
    @hardwork 对,数学上可以找出递推公式。见 23 楼的链接。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2771 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 12:50 · PVG 20:50 · LAX 05:50 · JFK 08:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.