0

这段代码完成时间太长了。我已经尽我所能让它工作并让它运行了一个小时。我正在尝试解决这个问题：

令 a、b、c 和 n 为正整数。如果 a+b+c = 19*97 并且 a+n = bn = c/n 计算 a 的值。

这是我的代码：

from itertools import *
import gc
gc.disable()
a_list = []
ah = 0
b_num = 0
c_num = 0
number_of_solutions = 0
for a, b, c, n in product(range(1, 19*97), repeat=4):
        if a+b+c == 19*97 and a+n == b-n and b-n == c/n and a+n == c/n:
            a_num = a
            b_num = b
            c_num = c
            a_list.append(a)
            number_of_solutions = number_of_solutions + 1
        else:
            pass

print a_num+b_num+c_num
print a_list
print number_of_solutions

请帮忙！谢谢！

4

2 回答 2

3

暴力破解所有可能的组合是低效的。相反，做一些代数。消除变量。

(a+n) + (b-n) == (c/n) + (c/n)
a+b == 2*c/n
a+b+c == 2*c/n + c == 19*97
c*(2+n) == 19*97*n

因为a+n == c/nand a, b, c, andn是正整数，c是 的倍数n，所以

(2+n) * (c/n) == 19*97

(2+n)必须是 19、97 或 19*97。你可以做剩下的事情。

于 2013-08-07T22:17:23.113 回答
0

一些东西。正如@ChrisBarker 所说，您的搜索空间很大。有三种主要方法可以缩小范围。

  1. 确定 a 后，b 大致限制在 1 <= b < 19*97-a 的范围内。
  2. 当你确定了 a 和 b 后，c 完全由 a + b + c = 19*97 确定
  3. 当您确定了 a 和 b 时，n 完全由 a + n = b - n 确定（即 n = (ba)/2）

这是您的代码的编辑版本，可在几秒钟内解决此问题：

a_list = []
ah = 0
b_num = 0
c_num = 0
number_of_solutions = 0

for a in range(1, 19*97):
    for b in range(1, 19*97-a):
        c = 19*97 - b - a
        n = (b - a) / 2
        if n > 0 and n*2 == (b-a) and c/n == a+n:
            print "Found a solution! a=%d, b=%d, c=%d, n=%d" % (a, b, c, n)
            a_num = a
            b_num = b
            c_num = c
            a_list.append(a)
            number_of_solutions = number_of_solutions + 1
print
print a_num+b_num+c_num
print a_list
print number_of_solutions
于 2013-08-07T22:41:17.743 回答