如何按顺序生成天然产物？

Question

您想获得订购产品的列表 n x m，以便 n 和 m 都是自然数，并且 1 < (n x m) < upper_limit，比如 uper_limit = 100 . n 和 m 也不能大于上限的平方根（因此 n <= 10 和 m <= 10）。最直接的做法是使用列表理解生成所有产品，然后对结果进行排序。

sorted(n*m for n in range(1,10) for m in range(1,n))

然而，当 upper_limit 变得非常大时，这不是很有效，特别是如果 objective 是在给定特定条件下只找到一个数字（例如找到最大乘积，使得.. . -> 我想按降序生成产品，测试它们并在找到第一个符合条件的产品后立即停止整个过程）。

那么，如何按顺序生成这些产品？

我做的第一件事就是从upper_limit开始，一个一个往回走，做一个双测： - 检查数字是否可以是 n 和 m 的乘积 - 检查标准同样，这不是很有效...... 有解决这个问题的算法吗？

Answer 1

以下代码将不重复地检查所有可能的组合，并在满足条件时停止。这段代码中如果break在内层循环中执行，则外层循环中的break语句也被执行，否则执行continue语句。

from math import sqrt
n = m = round(sqrt(int(input("Enter upper limit"))))
for i in range(n, 0, -1):
    for j in range(i - 1, 0, -1):
        if * required condition:
            n = i
            m = j
            break
    else:
        continue
    break

Answer 2

我找到了一个稍微更有效的解决这个问题的方法。对于 a 和 b 是自然数：

S = a + b
D = abs(a - b)

如果S一定，D越小，a*b越大。因此，对于每个 S（按降序排列），可以通过递增的 D 遍历所有可能的元组 (a, b)。

首先，我插入外部条件，如果乘积 ab 符合该条件，那么我将遍历其他 (a,b) 具有较小递减 S 和较小递增 D 的元组，以检查我是否找到其他符合相同条件但具有更大 ab 的数字。我重复迭代，直到找到 D == 0 或 1 的数字（因为在那种情况下，不可能有具有更高产品的更小 S 的元组）

如何按顺序生成天然产物？

How to generate natural products in order?

python

math

mathematical-optimization