Нахождение трех целых чисел так, чтобы их сумма значений косинуса становилась макс
Существует три целых числа 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)
Ответы
Ответ 1
В идеале вы хотите рассчитать каждую возможную комбинацию только один раз. Игнорируя геометрические свойства 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
Если я перемещу создание массива внутри таймера, он будет еще медленнее.
Ответ 2
Как отметил Жан-Франсуа Фабр в комментариях, есть много приемов, которые можно применить для повышения производительности, но прежде всего
- отмечая, что значения
a
и b
определяют значение c
,
- отмечая, что хотя бы одна из трех переменных, WLOG
a
, меньше или равна N/3
,
- используя оставшуюся симметрию в
b
и c
, чтобы связать b
между a
и (N - a)//2 + 1
- предварительно вычисляя все соответствующие значения cos и стараясь не искать одинаковые значения в быстрой последовательности,
- сокращение внешнего цикла для преждевременной остановки, когда заданное значение
cos(a)
никогда не приведет к новому максимуму,
- используя 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):
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))
Ответ 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 с косинусом (x) = 0,748. Любое общее количество, связанное с этим x, не может превышать 2,748, поэтому вы можете отклонить x прямо. Когда вы найдете одну хорошую сумму, вы можете отклонить многие значения x.
Чтобы сделать это более эффективным, вы сортируете значения x от наивысшего до самого низкого значения cosine (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, sort 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 будут проверены, что быстрее, чем сортировка.
Ответ 4
Это другой подход, довольно быстрый (менее 1 с):
from math import cos
limit = 1000000
pairs = [[0,0], [0,0], [0,0]]
for x in range(1,limit+1):
pairs.sort(key=lambda e: e[1])
cos_x = cos(x)
if cos_x > pairs[0][1] and ( x + sum([x[0] for x in pairs]) - min([x[0] for x in pairs]) ) < limit:
pairs[0] = [x, cos_x]
Он возвращает:
print(pairs)
print(sum([x[1] for x in pairs]))
print(sum([x[0] for x in pairs]))
#=> [[103993, 0.9999999998170342], [416682, 0.9999999998683157], [312689, 0.9999999999957929]]
#=> 2.999999999681143
#=> 833364
Ответ 5
Нет необходимости когда-либо вычислять косинус, чтобы ответить на этот вопрос. Просто отслеживайте три (два, если n = 0 разрешено) наименьшие значения функции f(n) = abs(2pi*n-round(2pi*n))
когда n
идет от 1 до N, где N является вашим верхним предел поиска.
Косинус равен 1 в кратных 2*pi
поэтому мы ищем два или три кратных числа, ближайших к целому числу в пределах предела поиска.
Не запускайте программу, чтобы сделать это, но это должно быть легко в любом программировании langauage. Я буду использовать Mathematica.
Ответ 6
Это чисто основная проблема тригонометрии. Максимальное значение для вашего уравнения будет, когда каждый из косинусов имеет значение 1. В cos (n), где n - любое число, для всех значений, образованных набором n = 2 * pi * k, где k > = 0, а k - целое число; ваш косинус будет иметь значение 1. Значения x, y, z принадлежат этому набору, и перестановка этих значений даст вам желаемое значение. Кроме того, не забудьте проверить, является ли n в наборе целочисленным, чтобы уменьшить пространство выборки.