<p>在你给我的两个例子中,我注意到了相同的模式。例如,对于第一种情况,如果你把这两个方程加在一起,你会得到</p>
<pre><code>-n1 - n2 - n3 - n4 - n5 - n6 - n7 + 20 > 0
</code></pre>
<p>可以重新排列为</p>
^{pr2}$
<p>这是一个很好的有界方程,你可以用蛮力。具体地说,你可以迭代从0到19的<code>n1</code>,从0到19-n1等等。一个可能的解决方案是(0,0,0,0,0,0,0),但是我们注意到这并不满足我们原来的方程。所以,只需生成(n1,n2,…,n7)的所有可能值,只保留那些满足方程的值。将所有这些结果硬编码到</p>
<pre><code>def find_solutions(N):
sols = []
for n1 in xrange(N):
for n2 in xrange(N-n1):
for n3 in xrange(N-n1-n2):
for n4 in xrange(N-n1-n2-n3):
for n5 in xrange(N-n1-n2-n3-n4):
for n6 in xrange(N-n1-n2-n3-n4-n5):
for n7 in xrange(N-n1-n2-n3-n4-n5-n6):
if (97*n1 + 89*n2 + 42*n3 + 20*n4 + 16*n5 + 11*n6 + 2*n7 - 185 > 0 and
-98*n1 - 90*n2 - 43*n3 - 21*n4 - 17*n5 - 12*n6 - 3*n7 + 205 > 0):
sols.append((n1, n2, n3, n4, n5, n6, n7))
return sols
</code></pre>
<p><code>find_solutions(20)</code>在0.6秒内找到所有1013个解。同样,对于第二种情况,它在2.3秒内找到所有4015个解。现在,这一点很难概括,但它表明,使用一种聪明的方法,Python或任何其他语言都不必慢。在</p>
<p>另一方面,递归允许我们将其推广到任意数量的嵌套循环中,但代价是运行速度稍慢。在</p>
<pre><code>def find_solutions(N, coeffs, depth=0, variables=None, subtotal=None, solutions=None):
if variables is None:
solutions = []
subtotal = [0 for _ in xrange(len(coeffs[0]))]
variables = [0 for _ in xrange(len(coeffs[0])-1)]
if depth == len(coeffs[0])-2:
for v in xrange(N-sum(variables[:depth])):
conditions = all(
subtotal[i]+coeffs[i][depth]*v > coeffs[i][-1]
for i in xrange(len(coeffs))
)
if conditions:
variables[depth] = v
solutions.append(tuple(variables))
else:
for v in xrange(N-sum(variables[:depth])):
variables[depth] = v
total = [subtotal[i]+coeffs[i][depth]*v for i in xrange(len(coeffs))]
find_solutions(N, coeffs, depth+1, variables, total, solutions)
if depth == 0:
return solutions
</code></pre>
<p>要运行此操作,请生成每个方程的系数并将其传递给函数。记住常数的符号是颠倒的!在</p>
<pre><code>coeffs = [
[97, 89, 42, 20, 16, 11, 2, 185],
[-98, -90, -43, -21, -17, -12, -3, -205]
]
solutions = find_solutions(20, coeffs)
print(len(solutions))
</code></pre>
<p>这一个在1.6秒内完成<em>n</em>=7个案例,5.8秒完成<em>n</em>=8案例。如果你希望你的<em>n</em>变得非常大,我会考虑任何可能的优化,但目前看来这是令人满意的。在</p>
<p>剩下的问题是方程的和是否总是简化为<code>n1 + n2 + ... nn < N</code>。如果不是这样的话,有一个简单的解决方案可以解决这个问题,但是我不想过早地过度概括您提供的示例之外的代码。在</p>
<p>最后,我设想同样的方法可以用Java或C实现,而且可能会更快。如果你的一般案件需要更长时间才能解决,我不介意这样做。在</p>