Col*_*ker 39 python random python-3.x
我是编程的初学者，我正在寻找如何生成满足条件的三个整数的好主意。
例子：
给定n = 30，我们被要求生成三个整数 a、b 和 c，因此7*a + 5*b + 3*c = n。我尝试使用for循环，但它花费了太多时间，而且我的最大测试时间为 1000 毫秒。
我正在使用 Python 3。
我的尝试：
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]))
Ilm*_*nen 80
首先，让我注意到您的任务至少在两个方面没有明确规定：
通常，如果没有指定，人们可能会假设方程的一组可能解上的均匀分布是预期的（因为在某种意义上，它是给定集合上最随机的可能分布）。但是（离散的）均匀分布只有在解集是有限的情况下才有可能，如果结果的范围不受限制，则不可能。（特别是，如果 ( a , b , c ) 是一个解，那么 ( a , b + 3 k , c ? 5 k ) 对于任何整数k也是一个解.) 因此，如果我们将任务解释为要求具有无限范围的均匀分布，那实际上是不可能的！
另一方面，如果允许我们选择任何分布和范围，任务就变得微不足道：只需让生成器始终返回a = ? n , b = n , c = n。显然，这是方程的解（因为 ?7 n + 5 n + 3 n = (?7 + 5 + 3) n = 1 n），并且将所有概率质量分配给单点的退化分布仍然是有效的概率分布！
如果您想要一个稍微简并的解决方案，您可以选择一个随机整数k（使用您选择的任何分布）并返回a = ? n , b = n + 3 k , c = n ? 5千。如上所述，这也是对任何k的方程的解。当然，这种分布仍然有点退化，因为值一个是固定的。
如果你想让所有的返回值至少有点随机，你也可以选择一个随机的h并返回a = ? n + h , b = n ? 2 h + 3 k和c = n + h？5千。同样，这保证是任何h和k的有效解，因为它清楚地满足h = k = 0的方程，而且很容易看出增加或减少h或k 将保持等式左侧的值不变。
事实上，可以证明这种方法可以生成方程的所有可能解，并且每个解都会对应一个唯一的 ( h , k ) 对！（观察这一点的一种相当直观的方法是在 3D 空间中绘制解并观察它们在 2D 平面上形成规则点阵，并且向量 (+1, ?2, +1) 和 (0, + 3, ?5) 跨越这个格子。）如果我们从某个分布（至少在理论上）为每个整数分配一个非零概率的分布中选择h和k，那么我们将有一个非零概率返回任何有效的解决方案。因此，至少对于任务的某种合理解释（无界范围，任何完全支持的分布) 以下代码应该有效地解决任务：
from random import gauss
def random_solution(n):
h = int(gauss(0, 1000)) # any distribution with full support on the integers will do
k = int(gauss(0, 1000))
return (-n + h, n - 2*h + 3*k, n + h - 5*k)
如果可能值的范围受到限制，问题就会变得有点棘手。从积极的方面来说，如果所有值都低于（或高于）范围，则可能的解决方案集是有限的，因此其上存在均匀分布。另一方面，对这种均匀分布进行有效采样并非易事。
您自己使用过的一种可能的方法是首先生成所有可能的解决方案（假设它们的数量有限），然后从解决方案列表中取样。我们可以像这样相当有效地生成解决方案：
棘手的部分是第 2 步，我们要计算可能的b值的范围。为此，我们可以利用观察结果，对于给定的a，将c设置为其最小允许值并求解方程给出b的上限（反之亦然）。
特别地，分别求解a、b和c的方程，我们得到：
给定一些值的下限，我们可以使用这些解决方案来计算其他值的相应上限。例如，以下代码将有效地生成所有非负解（如果需要，可以轻松修改为使用 0 以外的下限）：
def all_nonnegative_solutions(n):
a_min = b_min = c_min = 0
a_max = (n - 5*b_min - 3*c_min) // 7
for a in range(a_min, a_max + 1):
b_max = (n - 7*a - 3*c_min) // 5
for b in range(b_min, b_max + 1):
if (n - 7*a - 5*b) % 3 == 0:
c = (n - 7*a - 5*b) // 3
yield (a, b, c)
然后我们可以将解决方案存储在列表或元组中，并从该列表中获取样本：
from random import choice
solutions = tuple(all_nonnegative_solutions(30))
a, b, c = choice(solutions)
附言。显然，Pythonrandom.choice不够聪明，无法使用水库采样从任意迭代中进行采样，因此即使我们只想从中采样一次，我们也确实需要存储解决方案的完整列表。或者，当然，我们总是可以实现我们自己的采样器：
def reservoir_choice(iterable):
r = None
n = 0
for x in iterable:
n += 1
if randrange(n) == 0:
r = x
return r
a, b, c = reservoir_choice(all_nonnegative_solutions(30))
顺便说一句，我们可以all_nonnegative_solutions通过观察(n - 7*a - 5*b) % 3 == 0条件（检查c = ( n ? 7 a ? 5 b ) / 3 是否是一个整数，因此是一个有效的解决方案）对于每三个值都为真，从而使上面的函数更有效一点的b。因此，如果我们首先计算满足给定a条件的b的最小值（可以通过一些模算术来完成），我们可以从该最小值开始以 3 的步长迭代b并跳过完全可分性检查。我将实施该优化作为练习。
Gul*_*zar 36
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)
如果您选择数字 a、b、c 中的两个，您就会知道第三个。在这种情况下，我将 a、b 的整数随机化，然后找到 c by c = (n - 7 * a - 5 * b) / 3.0。
确保 c 是一个整数，并且在允许的范围内，我们就完成了。
如果不是，则再次随机化。
如果你想产生所有的可能性，
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
MrG*_*eek 15
如果允许使用第三方库，您可以使用 SymPy 的线性丢番图方程求解器：diophantine.diop_linear
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')
输出（随机）：
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
Art*_*ius 13
为什么您的解决方案无法处理大的值 n
您可能会理解，for范围为i,的循环中的所有内容都将运行i时间。所以它会乘以时间i。
例如，让我们假装（为简单起见）它在 4 毫秒内运行：
if 7*a + 5*b + 3*c = n:
c.append(a)
k.append(b)
w.append(c)
然后这将在 4×n 毫秒内运行：
for c in range(n):
if 7*a + 5*b + 3*c = n:
c.append(a)
k.append(b)
w.append(c)
大约：
如果你把它放在一个for范围内的循环中，n那么整个事情将被重复n多次。IE
for b in range(n):
for c in range(n):
if 7*a + 5*b + 3*c = n:
c.append(a)
k.append(b)
w.append(c)
将需要 4n² 毫秒。
将它放入第三个 for 循环将需要 4n³ 毫秒。
现在，如果你把原来的if时间减半到 2 毫秒呢？n在第一种情况下可以增加 15000 ……在最后一种情况下可以增加 23。这里的教训是，更少的 for 循环通常比加速其中的内容重要得多。正如您在 Gulzar 的回答第 2 部分中所见，只有两个 for 循环有很大的不同。（这仅适用于循环彼此内部的情况；如果它们只是一个接一个，则您没有乘法问题。）