Как генерировать натуральные продукты на заказ?

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 становится очень большим, это не очень эффективно, особенно еслицель состоит в том, чтобы найти только одно число с учетом определенных критериев (например, найти максимальный продукт таким образом, чтобы ... -> Я хотел бы сгенерировать продукты в порядке убывания, протестировать их и остановить весь процесс, как только я найду первыйчто соответствует критериям).

Итак, как сгенерировать эти продукты по порядку?

Первое, что я сделал, это начался с upper_limit и пошел назад один за другим, делая двойнойtest: - проверка, может ли число быть произведением n и m - проверка критериев. Опять же, это не очень эффективно ... Какой-нибудь алгоритм, который решает эту проблему?

Answer 1

Я нашел немного более эффективное решение этой проблемы.Если a и b являются натуральными числами:

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

Если S постоянно, то чем меньше D, тем больше a * b.Поэтому для каждого S (взятого в порядке убывания) можно итерировать все возможные наборы (a, b) с увеличением D.

Сначала я подключаю внешнее условие, и если продукт a bсоблюдает условие, которое я затем повторяю через другие (a, b) кортежи с меньшим убывающим S и меньшим возрастающим D, чтобы проверить, не найду ли я другие числа, которые соответствуют тому же условию, но имеют больший a b.Я повторяю итерацию, пока не найду число с D == 0 или 1 (потому что в этом случае не может быть кортежей с меньшим S, которые имеют более высокое произведение)

Answer 2

Следующий код проверит все возможные комбинации без повторов и остановится, когда условие будет выполнено. В этом коде, если разрыв выполняется во внутреннем цикле, выполняется также оператор 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