Comment puis-je générer trois entiers aléatoires qui satisfont à une condition ?

Question

Je suis un débutant en programmation et je suis à la recherche d'une bonne idée comment générer trois entiers qui satisfont une condition.

Exemple :

On nous a donné n = 30, et on nous a demandé de générer trois entiers a, b et c, de sorte que 7*a + 5*b + 3*c = n. J'ai essayé d'utiliser des boucles for, mais cela prend trop de temps et j'ai un temps de test maximum de 1000 ms.

J'utilise Python 3.

Ma tentative :

x = int(input())
c = []
k = []
w = []
for i in range(x):
    for j in range(x):
        for h in range(x):
           if 7*i + 5*j + 3*h = x:
              c.append(i)
              k.append(j)
              w.append(h)
if len(c) == len(k) == len(w) 
    print(-1)
else: 
    print(str(k[0]) + ' ' + str(c[0]) + ' ' + str(w[0]))

Answer 1

import numpy as np


def generate_answer(n: int, low_limit:int, high_limit: int):
    while True:
        a = np.random.randint(low_limit, high_limit + 1, 1)[0]
        b = np.random.randint(low_limit, high_limit + 1, 1)[0]
        c = (n - 7 * a - 5 * b) / 3.0
        if int(c) == c and low_limit <= c <= high_limit:
            break

    return a, b, int(c)


if __name__ == "__main__":
    n = 30
    ans = generate_answer(low_limit=-5, high_limit=50, n=n)
    assert ans[0] * 7 + ans[1] * 5 + ans[2] * 3 == n
    print(ans)

Si vous sélectionnez deux des nombres a, b, c, vous connaissez le troisième. Dans ce cas, je randomise INTS pour a, b, et je trouve c par c = (n - 7 * a - 5 * b) / 3.0.

Assurez-vous que c est un entier, et dans les limites autorisées, et nous avons terminé.

Si ce n'est pas le cas, randomisez à nouveau.

---

Si vous voulez générer toutes les possibilités,

def generate_all_answers(n: int, low_limit:int, high_limit: int):
    results = []
    for a in range(low_limit, high_limit + 1):
        for b in range(low_limit, high_limit + 1):
            c = (n - 7 * a - 5 * b) / 3.0
            if int(c) == c and low_limit <= c <= high_limit:
                results.append((a, b, int(c)))

    return results

Answer 2

Si des bibliothèques tierces sont autorisées, vous pouvez utiliser le solveur d'équations diophantines linéaires diophantine.diop_linear de SymPy :

from sympy.solvers.diophantine.diophantine import diop_linear
from sympy import symbols
from numpy.random import randint

n = 30
N = 8 # Number of solutions needed

# Unknowns
a, b, c = symbols('a, b, c', integer=True)

# Coefficients
x, y, z = 7, 5, 3

# Parameters of parametric equation of solution
t_0, t_1 = symbols('t_0, t_1', integer=True)

solution = diop_linear(x * a + y * b + z * c - n)

if not (None in solution):
  for s in range(N):
    # -10000 and 10000 (max and min for t_0 and t_1)
    t_sub = [(t_0, randint(-10000, 10000)), (t_1, randint(-10000, 10000))]

    a_val, b_val, c_val = map(lambda t : t.subs(t_sub), solution)

    print('Solution #%d' % (s + 1))
    print('a =', a_val, ', b =', b_val, ', c =', c_val)
else:
  print('no solutions')

Sortie (aléatoire) :

Solution #1
a = -141 , b = -29187 , c = 48984
Solution #2
a = -8532 , b = -68757 , c = 134513
Solution #3
a = 5034 , b = 30729 , c = -62951
Solution #4
a = 7107 , b = 76638 , c = -144303
Solution #5
a = 4587 , b = 23721 , c = -50228
Solution #6
a = -9294 , b = -106269 , c = 198811
Solution #7
a = -1572 , b = -43224 , c = 75718
Solution #8
a = 4956 , b = 68097 , c = -125049