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

编程求解:

  •  
  •   forgottencoast · 51 天前 · 1283 次点击
    这是一个创建于 51 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    我后来还加了一个小优化,最后三个数直接查表(提前算好)。总时间在我电脑上大概 9 秒,代码和具体计时详见: https://gist.github.com/neteroster/9f59b6a868ef26fc7a43ce6a3eaac4bd
    forgottencoast
        11
    forgottencoast  
    OP
       50 天前   ❤️ 1
    @neteroster
    真快,有人用 C 写也要几秒钟。
    我还是第一次听说 Racket 。
    谢谢分享代码。
    v24radiant
        12
    v24radiant  
       49 天前
    根据上面的代码改成 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  
       49 天前 via Android
    @v24radiant 遗憾的是,由于 Python 默认并不以精确方式表示与运算有理数,所以如此查表将遗漏大部分的解。
    v24radiant
        14
    v24radiant  
       49 天前
    @neteroster #13 说反了吧, 应该是由于精度问题错误算多了答案吧😂 实际用 decimal 模块精确计算答案, 最终结果只有 242 条╮(╯▽╰)╭
    neteroster
        15
    neteroster  
       49 天前 via Android
    @v24radiant 算多也是有可能的,不过我的直觉是算少(查表的时候意外撞上的可能性感觉不大),不过反正都是不精确的。
    几百条肯定是少了,我原程序算的六万多条都化成整数运算检验过的,只可能少不会多。
    neteroster
        16
    neteroster  
       49 天前 via Android
    @neteroster 另外,用 decimal 应该也不行。它能正确表示精确的 1/3 吗?
    forgottencoast
        17
    forgottencoast  
    OP
       49 天前
    @neteroster
    基本确定 69014 是对的,很多人算出这个结果。
    v24radiant
        18
    v24radiant  
       49 天前
    @neteroster #16
    @forgottencoast #17
    这种还是要处理成最简分式再进行计算😂, 直接用 decimal 不行, 要花大概 10s 了
    forgottencoast
        19
    forgottencoast  
    OP
       49 天前
    @v24radiant
    目前看到的解决方案努力方向都是剪枝。
    sillydaddy
        20
    sillydaddy  
       46 天前
    这个帖子发在「数学」节点下面,每人想过用一点数学知识吗?
    一个数学方面的线索: 如果 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
       46 天前
    @sillydaddy
    水木社区有人用光滑数来裁剪,目前的最优解。
    不过我看不懂。( ╯□╰ )
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4050 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 05:12 · PVG 13:12 · LAX 22:12 · JFK 01:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.