编程求解: - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
forgottencoast
V2EX    数学

编程求解:

  •  
  •   forgottencoast 2024-02-24 15:00:27 +08:00 2614 次点击
    这是一个创建于 669 天前的主题,其中的信息可能已经有所发展或是发生改变。

    从 1 到 100 这 100 个数字中任意选取 10 个数,求这 10 个数字的倒数之和为 1 的所有可能结果。

    扩展: 从 1 到 n 这 n 个数字中随机选取 m 个数,求这 m 个数字的倒数之和为 1 的所有可能结果。

    21 条回复    2024-02-29 17:52:15 +08:00
    vituralfuture
        1
    vituralfuture  
       2024-02-24 15:20:07 +08:00 via Android
    枚举法,注意一下为了避免浮点数误差,不要直接取倒数,把先分母弄到等号另外一边,消除分母
    Rang666
        2
    Rang666  
       2024-02-24 15:21:06 +08:00 via iPhone
    递归就行,第一个是 a ,就 1-100 选 9 个,求倒数是 1-1/a
    forgottencoast
        3
    forgottencoast  
    OP
       2024-02-24 15:27:28 +08:00
    @Rang666
    @vituralfuture
    难点在于计算量太大,两位可以尝试。
    klo424
        4
    klo424  
       2024-02-24 16:17:51 +08:00
    标题应改为“算法求解”
    klo424
        5
    klo424  
       2024-02-24 16:22:26 +08:00
    然后建议问问 GPT
    phrack
        6
    phrack  
       2024-02-24 20:19:51 +08:00
    递归加减枝,标准操作
    neteroster
        7
    neteroster  
       2024-02-24 21:33:31 +08:00   1
    每次选择上界稍微剪一下(选 m 个倒数和为 k 的话最小那个一定要小于 m/k 了)就跑的出来了,总共 69014 组,不知道有没漏。应该还可以再优化。
    forgottencoast
        8
    forgottencoast  
    OP
       2024-02-25 17:23:40 +08:00
    @klo424 它不会,或者说给出的答案很差。
    forgottencoast
        9
    forgottencoast  
    OP
       2024-02-25 17:26:53 +08:00
    @neteroster
    你这个可能是对的,有几个人也得出这个结果。
    你的程序跑一次要多长时间?
    neteroster
        10
    neteroster  
       2024-02-25 18:47:10 +08:00   1
    @forgottencoast 我最近在学 Racket ,所以用这个语言写的。这语言编译后基本操作大概比 C / C++ 慢一个数量级。

    我后来还加了一个小优化,最后三个数直接查表(提前算好)。总时间在我电脑上大概 9 秒,代码和具体计时详见: https://gist.github.com/neteroster/9f59b6a868ef26fc7a43ce6a3eaac4bd
    forgottencoast
        11
    forgottencoast  
    OP
       2024-02-25 19:43:09 +08:00   1
    @neteroster
    真快,有人用 C 写也要几秒钟。
    我还是第一次听说 Racket 。
    谢谢分享代码。
    v24radiant
        12
    v24radiant  
       2024-02-26 13:38:44 +08:00
    根据上面的代码改成 python, 优化一下剪枝, 总运行时间如下:

    3.18 s ± 211 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

    python 代码如下:

    ```python
    %%timeit
    import itertools

    min_sum = [0 for _ in range(10)]
    min_sum[0] = 1 / 100
    for i in range(1, 10):
    min_sum[i] = min_sum[i - 1] + 1 / (100 - i)

    with open('resf.txt', 'w') as res_port:
    res_port.write("make table: \n")

    sum_table = {}
    for i in range(1, 101):
    for j in range(i + 1, 101):
    for k in range(j + 1, 101):
    key = 1 / i + 1 / j + 1 / k
    if key not in sum_table:
    sum_table[key] = []
    sum_table[key].append((k, j, i))

    def backtrack(path, start, target, n):
    if target < min_sum[n - 1]:
    return

    if n == 3:
    if target in sum_table:
    for c in sum_table[target]:
    if c[2] >= start:
    res_port.write(str(list(path) + list(c)) + '\n')
    else:
    kmax = int(n / target)
    end = min(100, kmax) + 1
    start = max(start, int(1 / target))
    for i in range(start, end):
    if 1 / i < target:
    backtrack(path + (i, ), i + 1, target - 1 / i, n - 1)

    res_port.write("backtrack: \n")
    backtrack((), 1, 1, 10)
    ```
    neteroster
        13
    neteroster  
       2024-02-26 14:20:53 +08:00 via Android
    @v24radiant 遗憾的是,由于 Python 默认并不以精确方式表示与运算有理数,所以如此查表将遗漏大部分的解。
    v24radiant
        14
    v24radiant  
       2024-02-26 15:51:39 +08:00
    @neteroster #13 说反了吧, 应该是由于精度问题错误算多了答案吧 实际用 decimal 模块精确计算答案, 最终结果只有 242 条()
    neteroster
        15
    neteroster  
       2024-02-26 15:57:26 +08:00 via Android
    @v24radiant 算多也是有可能的,不过我的直觉是算少(查表的时候意外撞上的可能性感觉不大),不过反正都是不精确的。
    几百条肯定是少了,我原程序算的六万多条都化成整数运算检验过的,只可能少不会多。
    neteroster
        16
    neteroster  
       2024-02-26 16:01:21 +08:00 via Android
    @neteroster 另外,用 decimal 应该也不行。它能正确表示精确的 1/3 吗?
    forgottencoast
        17
    forgottencoast  
    OP
       2024-02-26 17:09:09 +08:00
    @neteroster
    基本确定 69014 是对的,很多人算出这个结果。
    v24radiant
        18
    v24radiant  
       2024-02-26 17:46:36 +08:00
    @neteroster #16
    @forgottencoast #17
    这种还是要处理成最简分式再进行计算, 直接用 decimal 不行, 要花大概 10s 了
    forgottencoast
        19
    forgottencoast  
    OP
       2024-02-26 18:10:16 +08:00
    @v24radiant
    目前看到的解决方案努力方向都是剪枝。
    sillydaddy
        20/div>
    sillydaddy  
       2024-02-29 15:52:30 +08:00
    这个帖子发在「数学」节点下面,每人想过用一点数学知识吗?
    一个数学方面的线索: 如果 p,q,r,s...都是素数(比如 2,3,5,7,...),那么 1/p + 1/q + 1/r + 1/s + ... 永远也不会等于整数(例如 1 )。
    另一个数学方面的线索: 如果 p,q,r 和 s 这两组数互素(比如 2,4,7 作为一组,3 作为一组),那么 1/p + 1/q + 1/r + 1/s + ...不可能等于整数(例如 1 ),而 2,3,6 的倒数和是 1 ,它们无法拆分为互素的两组数。

    通过上述(有关素数的)线索,应该可以排除大量的组合。
    forgottencoast
        21
    forgottencoast  
    OP
       2024-02-29 17:52:15 +08:00
    @sillydaddy
    水木社区有人用光滑数来裁剪,目前的最优解。
    不过我看不懂。( □ )
    关于     帮助文档     自助推广系统     博客     API     FAQ     Solana     2955 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 29ms UTC 12:22 PVG 20:22 LAX 04:22 JFK 07:22
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86