找到三个整数，使它们的余弦值之和变为最大值

Question

有三个整数x，y并且z（每个 >= 1）和一个给定的上限整数n< 10^6。还有，n = x + y + z和output = cos(x) + cos(y) + cos(z)。

练习是最大化output。

我为此编写了一个简单的脚本，但时间复杂度为 O(n^3)。有什么办法可以简化这个吗？

from math import cos

n = 50

x = 1

y = 1

z = 1

total = cos(x) + cos(y) + cos(z)

for x in xrange(n):

    for y in xrange(n):

        for z in xrange(n):

            if x + y + z == n:

                temp = cos(x) + cos(y) + cos(z)

                if temp > total: total = temp

print round(total, 9) 

Answer 1

理想情况下，您只想计算每个可能的组合一次。忽略 的几何属性cos，并将其视为简单的从数字到数字的映射（例如，将其用作随机属性，正如@Jean 在他的第二条评论中提到的那样）。首先，您必须意识到在选择了 2 个数字后，给出了第三个。您可以选择“智能”以避免多余的选择：from math import cosimport timeimport numpy as npfrom numba import jitdef calc(n):&nbsp; &nbsp; x = 1&nbsp; &nbsp; y = 1&nbsp; &nbsp; z = 1&nbsp; &nbsp; total = cos(x) + cos(y) + cos(z)&nbsp; &nbsp; for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to&nbsp; n/3 -1 , after that we will repeat.&nbsp; &nbsp; &nbsp; &nbsp; cosx = cos(x)&nbsp; &nbsp; &nbsp; &nbsp; for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; z = n-x-y #Infer the z, taking the rest in account&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp = cosx + cos(y) + cos(z)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if temp > total: total = temp&nbsp; &nbsp; return totaltic = time.clock()total = calc(10000)print(time.clock()-tic)print (total)将采取1.3467099999999999（在我的机器上）。正如@fuglede 提到的，值得使用 numba 进行进一步优化。编辑： 保存所有先前计算的 cos 值实际上比重新计算它们更昂贵，当您访问 np 数组时，您不仅仅是访问内存中的一个点，而是使用 ndarray 函数。使用内置的pythoncos实际上更快：import numpy as npfrom math import cosimport timeimport timeitcos_arr = np.cos(np.arange(10000000))tic = time.time()def calc1():&nbsp; &nbsp; total = 0&nbsp; &nbsp; for j in range(100):&nbsp; &nbsp; &nbsp; &nbsp; for i in range(10000000):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total += cos_arr[i]def calc2():&nbsp; &nbsp; total = 0&nbsp; &nbsp; for j in range(100):&nbsp; &nbsp; &nbsp; &nbsp; for i in range(10000000):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; total += cos(i)time1 = timeit.Timer(calc1).timeit(number=1)time2 = timeit.Timer(calc2).timeit(number=1)print(time1)print(time2)有输出：127.9849290860002108.21062094399986如果我在计时器内移动数组创建，它会更慢。

Answer 2

正如 Jean-François Fabre 在评论中指出的那样，您可以应用很多技巧来提高性能，但首先注意到 的值a和b确定 的值c，注意到三个变量中的至少一个 WLOGa小于或等于N/3，使用b和之间的剩余对称性c来限制和ba(N - a)//2 + 1预先计算 cos 的所有相关值，并尽量避免快速连续查找相同的值，当给定的值cos(a)永远不会导致新的最大值时，修剪外循环以提前停止，使用Numba对代码进行 JIT 编译并免费获得一些性能（大约是 400 倍N = 500），然后否则蛮力解决方案相对较快地终止N = 1000000：import numpy as npfrom numba import jit@jitdef maximize(N):&nbsp; &nbsp; cos = np.cos(np.arange(N))&nbsp; &nbsp; m = -3&nbsp; &nbsp; for a in range(1, N//3 + 1):&nbsp; &nbsp; &nbsp; &nbsp; cosa = cos[a]&nbsp; &nbsp; &nbsp; &nbsp; if m - 2 > cosa:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue&nbsp; &nbsp; &nbsp; &nbsp; for b in range(a, (N - a)//2 + 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; c = N - a - b&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res = cosa + cos[b] + cos[c]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if res > m:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m = res&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bestabc = (a, b, c)&nbsp; &nbsp; return m, bestabcmaximize(1000000)&nbsp; # (2.9787165245899025, (159775, 263768, 576457))值得注意的是，上面利用的对称性仅在人们愿意忽略这样一个事实的情况下成立：数值问题导致浮点数的加法通常不是可交换的；这cos(a) + cos(b)不必与cos(b) + cos(a). 不过，您可能不会为此担心。

Answer 3

绝对不需要计算 3 xn^3 余弦值。我们可以假设 x ≤ y ≤ z。因此，x 可以是 1 到 n/3 范围内的任何整数。y 可以是 x 到 (n - x) / 2 范围内的任何整数。 z 必须等于 n - x - y。仅此一项就将您尝试的三元组 (x, y, z) 的数量从 n^3 减少到大约 n^2 / 6。接下来假设您找到了三个数字，总和为 2.749。并且您尝试使用余弦 (x) = 0.748 的 x。任何涉及此 x 的总数都不能超过 2.748，因此您可以完全拒绝 x。一旦找到一个好的总和，您就可以拒绝 x 的多个值。为了使这更有效，您将值 x 从 cosine(x) 的最高值到最低值进行排序，因为这使您更有可能找到允许您删除更多值的高总数。并且计算 cos(x) 很慢，因此您将值存储到表中。所以：Set c[i] = cos (i) for 1 ≤ i ≤ n.&nbsp;Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].&nbsp;Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].for x = elements of array x where c[x] + 2 ≥ bestTotal&nbsp; &nbsp; for y = x to (n-x)/2&nbsp; &nbsp; &nbsp; &nbsp; z = n - x - y&nbsp; &nbsp; &nbsp; &nbsp; total = c[x] + c[]y] + c[z]&nbsp; &nbsp; &nbsp; &nbsp; if total > bestTotal&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (bestx, besty, bestz) = (x, y, z)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bestTotal = total你可以通过一些数学来改进这一点。如果 y + z 的总和是常数，就像这里 y + z = n - x 一样，cos(y) + cos (z) 的总和是有限的。设 P 为最接近 (n - x) / 2pi 的整数，令 d = (n - x) - P * 2pi，则 cos (y) + cos (z) 的最大可能和为 2 * cos (d /2）。所以对于每个 x，1 ≤ x ≤ n/3，我们计算这个值 d 和 cos (x) + 2 * cos (d/2)，将这些值存储为某些 x 可以达到的最大总数，对 x 排序以便这些值按降序排列，并忽略可实现的总数小于目前最佳总数的那些 x。如果 n 真的很大（比如十亿），那么你可以使用 Euclid 算法快速找到所有接近 2k*pi + d 的整数 y，但这会有点复杂。for x in 1 to n/3&nbsp; &nbsp; let s = n - x&nbsp; &nbsp; let P = s / 2pi, rounded to the nearest integer&nbsp; &nbsp; let d = (s - P * 2pi) / 2&nbsp; &nbsp; let maxSum [x] = cos(x) + 2*cos(d)Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i].&nbsp;Set (bestx, besty, bestz) = (1, 1, n-2)Set bestTotal = c[bestx] + c [besty] + c [bestz].for x = elements of array x where maxSum[x] ≥ bestTotal&nbsp; &nbsp; for y = x to (n-x)/2&nbsp; &nbsp; &nbsp; &nbsp; z = n - x - y&nbsp; &nbsp; &nbsp; &nbsp; total = c[x] + c[]y] + c[z]&nbsp; &nbsp; &nbsp; &nbsp; if total > bestTotal&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; (bestx, besty, bestz) = (x, y, z)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bestTotal = total附注。我实际上尝试了一些 N 大约 1 亿的值。事实证明，我可以对数组进行排序以首先尝试 x 的最有希望的值，这需要很长时间，但通常 x 的第一个值是唯一尝试过的值。或者我可以使用 x = 1, 2, 3 等，这意味着将尝试 x 的几十个值，这比排序更快。