Непосредственное вычисление элемента в рекурсии с использованием побитового оператора XOR

Question

Давайте получим матрицу M X N- матрицы A [i] [j], заданную частично как:(начиная с row = 0 column = 0):

1) для всех 1<=i<=N A [0] [i] = 0

2) для всех 0 <= j <= M A [j] [0] = 1

Матрица строит A [i] [j] далее как:

для всех 1<=i<=N и 1 <= j <= M, A [i] [j] = A [i-1] [j] ^ A [i] [j-1], где ^ обозначает побитовая операция XOR.

Если я хочу получить какое-то значение A [i] [j], как я могу получить это напрямую (без фактического вычисления A [i] [j] для всех 1... j-1 и 1...i-1)? Есть ли образец? Даны М и N слишком велики.

Answer 1

Давайте построим первые 16 строк и столбцов матрицы A:

1000000000000000
1111111111111111
1010101010101010
1100110011001100
1000100010001000
1111000011110000
1010000010100000
1100000011000000
1000000010000000
1111111100000000
1010101000000000
1100110000000000
1000100000000000
1111000000000000
1010000000000000
1100000000000000

Ответ на ваш вопрос "есть ли закономерность" довольно ясно "Да!" Подматрица 8x8 в верхнем левом углу копируется непосредственно под собой, а также непосредственно вправо, за исключением того, что копия справа имеет 0 в верхнем левом углу вместо 1. Подматрица нижнего правого размера 8x8 - это все 0, кроме он имеет 1 в верхнем левом углу. Этот точно такой же шаблон возникает, если мы изучим только первые 8 строк и столбцов:

10000000
11111111
10101010
11001100
10001000
11110000
10100000
11000000

Верхняя левая подматрица 4x4 копируется непосредственно под собой, а также прямо вправо, за исключением того, что копия справа имеет 0 в верхнем левом углу вместо 1. Нижняя правая подматрица 4x4 - это все 0, кроме нее. имеет 1 в верхнем левом углу.

Это рекурсивное самоподобие делает матрицу A фракталом, очень похожим на треугольник Серпинского.

Рекурсивное самоподобие также позволяет нам легко вычислять A[i][j], используя двоичные представления i и j. Пусть B будет битом высшего порядка, установленным в двоичном представлении i или j. Затем следующая процедура вернет правильное значение A[i][j]:

• для b = B до 0:
  • если j=0, когда он ограничен битами от 0 до b, вернуть 1 (мы находимся в первом столбце, который равен всем 1)
  • в противном случае, если i=0, когда он ограничен битами от 0 до b, возвращается 0 (мы находимся в первой строке)
  • иначе, если i и j оба имеют 1, сохраненный в бите b, тогда возвращают 0, если все остальные биты в каждом не равны 0, в этом случае возвращают 1
  • еще продолжить (мы возвращаемся к меньшей субматрице)

Этот алгоритм работает во время выполнения O(log(max(i,j))), что намного быстрее, чем время выполнения O(ij) наивного подхода.

Давайте посмотрим на этот алгоритм в действии с несколькими примерами:

• A [9] [9] = 0 из вышеприведенной матрицы. В двоичном представлении i = 1001 и j = 1001. Оба имеют 1 в старшем значащем бите и после него устанавливаются некоторые биты, поэтому по приведенным выше правилам мы возвращаем 0.

• A [9] [3] = 1 из вышеприведенной матрицы. В двоичном представлении i = 1001 и j = 0011. В крайнем левом (самом значимом бите) i имеет 1, а j имеет 0. Поэтому мы переходим к следующему биту (recurse), где оба имеют 0. Мы снова перейдите к следующему биту, где у меня 0, а у j 1. Поэтому мы переходим к последнему биту. Оба имеют 1 в бите, и все последующие биты равны 0 (это тривиально верно, так как нет следующих битов), поэтому мы возвращаем 1.

• A [9] [4] = 1 из матрицы выше. В двоичном представлении i = 1001 и j = 0100. В крайнем левом (самом значимом бите) у меня есть 1, а у j - 0. Поэтому мы переходим к следующему биту (рекурсивный), где у меня есть 0, а у j есть 1. Мы снова переходим к следующему биту, где оба имеют 0. j имеет 0 в этом и всех последующих битах, поэтому мы возвращаем 1.

Одним интересным следствием этого алгоритма является то, что каждая строка k (для k > 0) имеет повторяющуюся комбинацию с периодом 2^B, где B - самый старший бит двоичного представления номера строки. Например, строка 3 (двоичное представление 11) повторяет 1100, в то время как строка 9 (двоичное представление 1001) повторяет 1111111100000000. Это означает, что полный повторяющийся ряд строки k> 0 может быть представлен в памяти O(k) и может быть вычислен в O(k log k) время путем отдельного вычисления A[k,j] для j = 0, 1, ..., 2^ потолок (log_2 k)-1.