Заменить цикл с формулой

Question

У меня есть этот цикл, который работает в O (конец - начало), и я хотел бы заменить его чем-то O (1).
Если бы «ширина» не уменьшалась, это было бы довольно просто.

for (int i = start; i <= end; i++, width--)
    if (i % 3 > 0) // 1 or 2, but not 0
        z += width;

начало, конец и ширина имеют положительные значения

Answer 1

Как уже упоминал кто-то, это, вероятно, проще всего представить как сумму двух рядов.

   x     x+3       x+6      ...  x+3N
 + x+3N  x+3(N-1)  x+3(N-2) ...  x
  -----------------------------------
  2x+3N 2x+3N     2x+3N     ... 2x+3N

Вышесказанное можно упростить до (2х + 3N) (N + 1) * * +1004

Что означает, что сумма одного из них действительно ... (2й + 3N) (N + 1) / 2

Это уравнение необходимо будет применить для обеих серий. Возможно, что N будет отличаться для обоих.

Таким образом, все, что вам нужно сделать, это определить начальную точку и количество предметов в серии. Это должно быть оставлено в качестве упражнения для студента.

Надеюсь, это поможет.

Answer 2

Обратите внимание, что

width == initial_width - (i - start)

, поэтому суммирование можно переписать как

      end
     —————
     \      (initial_width + start - i)
     /
     —————
    i=start
  i mod 3 ≠ 0

      end                                   ⌊end/3⌋
     —————                                   —————
==   \      (initial_width + start - i)  ——  \      (initial_width + start - 3j)
     /                                       /
     —————                                   —————
    i=start                               j=⌈start/3⌉

Остальное должно быть просто.

Answer 3

Замкнутая форма суммы (i = 1 ... n) i есть (n) (n + 1) / 2. Вы должны быть в состоянии использовать это с небольшой алгеброй, чтобы найти закрытую форму, которая дает вам результат, который вы ищете.

Answer 4

Я придумал этот уродливый метод:

int start; // = some number
int end; // = ...

int initialwidth; // = ...

int each = (end+1)/3 - (start-1)/3 - 1;
int loop = 2*(3-(start+2)%3)+1;
int total = each*loop + 3*each*(each-1) + (start%3==1) + (end-start)*(end%3==1);

int result = -total + initialwidth*(1 + end - start - end/3 + (start-1)/3);

total даст сумму (i-start) s, когда (i% 3> 0) для i = начало и конец.

Результат даст сумму ширин, добавленных к z.

Answer 5

Вероятно, проще всего думать об этом как о сумме двух отдельных рядов, один для случая, когда i%3 = 1, а другой для, когда i%3=2. В качестве альтернативы вы можете определить ее как сумму для всех значений i минус сумма для i%3=0. В качестве аргумента давайте рассмотрим первую половину последнего подхода: суммирование всех значений ширины.

В этом случае width начнется с некоторого начального значения, и на каждой итерации его значение будет уменьшено на 1. На последней итерации его значение будет уменьшено на (end-start). Возможно, проще всего думать об этом как о треугольнике. Для простоты мы будем использовать маленькие числа - начнем с width = 5, start = 1 и end = 5. Возможно, проще всего нарисовать диаграмму:

Значения ширины:

*
**
***
****
*****

Что мы действительно ищем, так это площадь этого треугольника - довольно известная формула из элементарной геометрии - 1 / 2ab, где a и b - длины двух сторон (в данном случае , определяется начальным значением width и end-start). Это предполагает, что это действительно треугольник, то есть он уменьшается до 0. В действительности, есть хороший шанс, что мы имеем дело с усеченным треугольником, но формула для этого также хорошо известна (1 / 2a ₁ b + 1 / 2a ₂ b, где a - высоты правой и левой сторон, а b - ширина.

Answer 6

Это не полный ответ, но вы должны заметить, что:

x = end - start;
k = ~(-1 << x); // I think (width * k)>>x would be your z except if you didn't have the contidional

и что значение, которое от LSB вверх имеет два установленных бита, один очищенный бит, два установленных бита, один очищенный бит (0x ... 011011011), может использоваться для вычисления, где% 3 равно 0.

R = k - (k & 0x...011011011); // This is the series 3 + (3 << 3) + (3 << 6) ...

z = (R * width)>>x;  // I think.

Просто кое-что попробовать. Я, наверное, допустил какую-то ошибку.

Answer 7

Хотите что-то вроде z = 2 * width * (start - end) / 3 + (start - end) % 3? (не совсем правильно, но достаточно близко, чтобы вы могли встать на правильный путь.