给定三个整数 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)
正如Jean-François Fabre在评论中指出的那样，您可以应用许多技巧来提高性能，但首先需要注意：
a和b的值确定了c的值，a）小于或等于N/3，b和c中剩余的对称性将b限制在a和(N - a)//2 + 1之间cos(a)值永远无法导致新的最大值时及早停止，N = 500大约为400倍），然后，否则粗暴的解决方案会相对较快地结束，即使对于N = 1000000也是如此：
import numpy as np
from numba import jit
@jit
def maximize(N):
cos = np.cos(np.arange(N))
m = -3
for a in range(1, N//3 + 1):
cosa = cos[a]
if m - 2 > cosa:
continue
for b in range(a, (N - a)//2 + 1):
c = N - a - b
res = cosa + cos[b] + cos[c]
if res > m:
m = res
bestabc = (a, b, c)
return m, bestabc
maximize(1000000) # (2.9787165245899025, (159775, 263768, 576457))
cos(a) + cos(b) 不一定等同于 cos(b) + cos(a)。尽管如此，您可能不必担心这个问题。from math import cos
import time
import numpy as np
from numba import jit
def calc(n):
x = 1
y = 1
z = 1
total = cos(x) + cos(y) + cos(z)
for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to n/3 -1 , after that we will repeat.
cosx = cos(x)
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
z = n-x-y #Infer the z, taking the rest in account
temp = cosx + cos(y) + cos(z)
if temp > total: total = temp
return total
tic = time.clock()
total = calc(10000)
print(time.clock()-tic)
print (total)
在我的电脑上需要 1.3467099999999999 的时间（可能执行该操作）。
如 @fuglede 所述，值得使用 numba 进行进一步优化。
编辑：
实际上保存所有先前计算的余弦值比重新计算它们更昂贵。当你访问 np 数组时，你不仅仅是访问内存中的一个点，而是使用 ndarray 函数。使用 Python 内置的 cos 实际上更快：
import numpy as np
from math import cos
import time
import timeit
cos_arr = np.cos(np.arange(10000000))
tic = time.time()
def calc1():
total = 0
for j in range(100):
for i in range(10000000):
total += cos_arr[i]
def calc2():
total = 0
for j in range(100):
for i in range(10000000):
total += cos(i)
time1 = timeit.Timer(calc1).timeit(number=1)
time2 = timeit.Timer(calc2).timeit(number=1)
print(time1)
print(time2)
输出结果：
127.9849290860002
108.21062094399986
x 调用了超过一次 cos(x)，都应该被点踩。 - TonyKfor语句之后，只需设置cosx = cos(x)，然后使用它代替cos(x)即可。试一试看看。 - TonyKSet c[i] = cos (i) for 1 ≤ i ≤ n.
Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i].
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
for y = x to (n-x)/2
z = n - x - y
total = c[x] + c[]y] + c[z]
if total > bestTotal
(bestx, besty, bestz) = (x, y, z)
bestTotal = total
for x in 1 to n/3
let s = n - x
let P = s / 2pi, rounded to the nearest integer
let d = (s - P * 2pi) / 2
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].
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
for y = x to (n-x)/2
z = n - x - y
total = c[x] + c[]y] + c[z]
if total > bestTotal
(bestx, besty, bestz) = (x, y, z)
bestTotal = total
PS. 实际上，我尝试了一些N值约为1亿的情况。结果发现，我可以将数组排序，以尝试首先尝试最有前途的x值，这需要很长时间，但通常只会尝试第一个x值。或者我可以使用x = 1、2、3等，这意味着将尝试几十个x值，这比排序更快。
这纯粹是一个基本的三角学问题。你的方程的最大值将在每个余弦函数的值都为1时达到。对于cos(n)，其中n是任意数字，在由n = 2 * pi * k组成的k >= 0且k为整数的所有值中，你的余弦函数将具有值1。你的x、y和z值属于这个集合，并且这些值的排列将使你得到所需的值。 此外，不要忘记检查集合中的n是否为整数，以减少样本空间。
n 可以给你余弦值为 1 的解。 - Sneftel