完全没有必要计算3 x n^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。并且你尝试了一个cosine(x)=0.748的x。任何涉及此x的总和都不能超过2.748,所以你可以直接拒绝x。一旦你找到一个好的总和,你就可以拒绝许多x的值。
为了使这更加有效,你可以按cosine(x)的最高到最低值对x值进行排序,因为这样更有可能找到一个高的总和,从而可以删除更多的值。
由于计算cos(x)很慢,所以你可以将值存储在表中。
Set 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
如果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非常大(比如十亿),则可以使用欧几里得算法快速找到所有接近2k*pi + d的整数y,但这会有点复杂。
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值,这比排序更快。