Найти три целых числа так, чтобы их сумма значений косинуса стала максимальной

Question

Существует три целых числа x, y и z (каждое из них> = 1) и заданное целое число верхней границы n <10 ^ 6.Кроме того, <code>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

Нет необходимости вычислять косинус, чтобы ответить на этот вопрос.Просто следите за тремя (двумя, если разрешено n = 0) наименьшими значениями функции f(n) = abs(2pi*n-round(2pi*n)), так как n идет от 1 до N, где N - ваш верхний предел поиска.

Косинус равен 1 с кратностью 2*pi, поэтому мы ищем два или три кратных, ближайших к целому числу в пределах предела поиска.

Еще не запустили программу для этого, но это должно быть легко в любом языке программирования.Я буду использовать Mathematica.

Answer 2

Абсолютно нет необходимости вычислять 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.И вы попробуйте х с косинус (х) = 0,748.Любая сумма с этим x не может быть больше 2.748, так что вы можете отклонить x напрямуюНайдя одну хорошую сумму, вы можете отклонить множество значений x.

Чтобы сделать это более эффективным, вы сортируете значения 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 действительно большое (скажем, миллиард), то вы можете использовать алгоритм Евклида, чтобы быстро найти все целые числа y, близкие к 2k * pi + d, но это будет немного сложно.

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 около 100 миллионов.Оказывается, я могу либо отсортировать массив, чтобы сначала попробовать самые многообещающие значения для x, что занимает много времени, но часто первое значение для x является единственным, которое проверяется.Или я могу использовать x = 1, 2, 3 и т. Д., Что означает, что будут испробованы несколько десятков значений для x, что быстрее, чем сортировка.

Answer 3

Как отметил Жан-Франсуа Фабр в комментариях, вы можете применить множество приемов для повышения производительности, но прежде всего

• , отметив, что значения a иb определить значение c,
• , отметив, что хотя бы одна из трех переменных, WLOG a, меньше или равна N/3,
• , используяоставшаяся симметрия в b и c для ограничения b между 1 и (N - a)//2 + 1
• с предварительным вычислением всех соответствующих значений cos и попыткой избежать поиска одинаковых значений в быстрой последовательности,
• с использованием Numba для JIT-компиляции кода и получения некоторой производительности бесплатно (примерно в 400 раз для N = 500),

, тогда иное решение для грубого обращения прекращаетсяотносительно быстро для N = 1000000 (то есть также для любого данного 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):
        for b in range(1, (N - a)//2 + 1):
            c = N - a - b
            res = cos[a] + cos[b] + cos[c]
            if res > m:
                m = res
                bestabc = (a, b, c)
    return m, bestabc

maximize(1000000)  # (2.9787165245899025, (159775, 263768, 576457))

Answer 4

В идеале вы хотите рассчитать каждую возможную комбинацию только один раз.Не обращая внимания на геометрические свойства cos и рассматривая его как простое сопоставление числа с номером (например, используя его как случайное свойство, как @Jean упомянул во втором комментарии).
Во-первых, вы должны понимать, что после выбора 2 чисел дается третье.и вы можете выбрать «умный», чтобы избежать лишних пиков:

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 для дальнейшей оптимизации.

Редактировать: Сохранение всех ранее рассчитанных значений cos на самом деле дороже, чем их пересчет, когда вы обращаетесь к массиву 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

Если я перемещу создание массива в таймере, это будет еще медленнее.

Answer 5

Это чисто основная проблема тригонометрии.Максимальное значение для вашего уравнения будет, когда все косинусы имеют значение 1. В cos (n), где n - любое число, для всех значений, образованных набором n = 2 * pi * k, где k> = 0 и k является целым числом;ваш косинус будет иметь значение 1. Ваши значения x, y, z принадлежат этому набору, и перестановка этих значений даст вам желаемое значение.Также не забудьте проверить, является ли n в наборе целым числом, чтобы уменьшить пространство выборки.