algorithm
Вычисление матрицы

Выравнивание матрицы для решения проблем

Найти f (n): n- ^й номер Фибоначчи. Проблема довольно проста, когда n относительно мало. Мы можем использовать простую рекурсию, f(n) = f(n-1) + f(n-2) , или мы можем использовать метод динамического программирования, чтобы избежать повторения одной и той же функции снова и снова. Но что вы будете делать, если проблема говорит: учитывая 0 <n <10⁹, найдите f (n) mod 999983? Динамическое программирование завершится неудачно, и как мы справимся с этой проблемой?

Сначала давайте посмотрим, как матричное возведение в степень может помочь представить рекурсивное отношение.

Предпосылки:

• Учитывая две матрицы, вы знаете, как найти их продукт. Далее, учитывая матрицу произведения двух матриц и одну из них, знаем, как найти другую матрицу.
• Учитывая матрицу размера d X d , знаете, как найти ее n- ^ю степень в O (d ³ log (n)) .

Шаблоны:

Сначала нам нужно рекурсивное соотношение, и мы хотим найти матрицу M, которая может привести нас к желаемому состоянию из набора уже известных состояний. Предположим, что мы знаем k состояний данного рекуррентного отношения и хотим найти (k + 1) ^-е состояние. Пусть M - матрица k X k , и мы строим матрицу A: [k X 1] из известных состояний рекуррентного отношения, теперь мы хотим получить матрицу B: [k X 1], которая будет представлять множество следующих состояний, то есть MXA = B, как показано ниже:

       |  f(n)  |     | f(n+1) |
       | f(n-1) |     |  f(n)  |
   M X | f(n-2) |  =  | f(n-1) |
       | ...... |     | ...... |
       | f(n-k) |     |f(n-k+1)|

Итак, если мы сможем спроектировать M соответственно, наша работа будет выполнена! Затем матрица будет использоваться для представления рекуррентного отношения.

Тип 1:
Начнем с простейшего, f(n) = f(n-1) + f(n-2)
Получаем, f(n+1) = f(n) + f(n-1) .
Предположим, что мы знаем f(n) и f(n-1) ; Мы хотим узнать f(n+1) .
Из изложенной выше ситуации матрица A и матрица B могут быть сформированы, как показано ниже:

 Matrix A          Matrix B

|  f(n)  |        | f(n+1) |
| f(n-1) |        |  f(n)  |

[Примечание: матрица A будет всегда сконструирована таким образом, чтобы каждое состояние, от которого зависит f(n+1) , будет присутствовать]
Теперь нам нужно создать матрицу 2X2 M такую, что она удовлетворяет MXA = B, как указано выше.
Первым элементом B является f(n+1) который фактически является f(n) + f(n-1) . Чтобы получить это, из матрицы A нам понадобится 1 X f (n) и 1 X f (n-1) . Таким образом, первая строка M будет [1 1] .

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| ----- |     | f(n-1) |     | ------ |

[Примечание: ----- означает, что нас это не касается.]
Аналогично, второй элемент B является f(n) который можно получить, просто взяв 1 X f (n) из A , поэтому вторая строка M равна [1 0].

| ----- |  X  |  f(n)  |  =  | ------ |
| 1   0 |     | f(n-1) |     |  f(n)  |

Тогда мы получим желаемые 2 X 2 матрицы M.

| 1   1 |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

Эти матрицы просто выведены с использованием матричного умножения.

Тип 2:

Сделаем его несколько сложным: найдем f(n) = a X f(n-1) + b X f(n-2) , где a и b - постоянные.
Это говорит нам, что f(n+1) = a X f(n) + b X f(n-1) .
До сих пор должно быть ясно, что размерность матриц будет равна числу зависимостей, то есть в этом конкретном примере, снова 2. Итак, для A и B мы можем построить две матрицы размера 2 X 1 :

Matrix A             Matrix B
|  f(n)  |          | f(n+1) |
| f(n-1) |          |  f(n)  |

Теперь для f(n+1) = a X f(n) + b X f(n-1) нам нужно [a, b] в первой строке объектной матрицы M. А для второго элемента в B , т. f(n) мы уже имеем это в матрице A , поэтому просто возьмем то, что приводит, вторая строка матрицы M к [1 0]. На этот раз мы получим:

| a   b |  X  |  f(n)  |  =  | f(n+1) |
| 1   0 |     | f(n-1) |     |  f(n)  |

Довольно просто, а?

Тип 3:

Если вы дожили до этого этапа, вы стали намного старше, теперь давайте рассмотрим несколько сложное соотношение: find f(n) = a X f(n-1) + c X f(n-3) ?
По электронной почте Ой! Несколько минут назад все, что мы видели, были смежными состояниями, но здесь состояние f (n-2) отсутствует. Сейчас?

На самом деле это уже не проблема, мы можем преобразовать соотношение следующим образом: f(n) = a X f(n-1) + 0 X f(n-2) + c X f(n-3) , выводя f(n+1) = a X f(n) + 0 X f(n-1) + c X f(n-2) . Теперь мы видим, что это на самом деле форма, описанная в типе 2. Таким образом, объективная матрица M будет 3 X 3 , а элементы:

| a 0 c |     |  f(n)  |     | f(n+1) |
| 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
| 0 1 0 |     | f(n-2) |     | f(n-1) |

Они вычисляются так же, как тип 2, если вам сложно, попробуйте его на ручке и бумаге.

Тип 4:

Теперь жизнь становится сложной, и г-н, Проблема теперь просит вас найти f(n) = f(n-1) + f(n-2) + c где c - любая константа.
Теперь это новый и все, что мы видели в прошлом, после умножения каждое состояние в A переходит в следующее состояние в B.

f(n) = f(n-1) + f(n-2) + c
f(n+1) = f(n) + f(n-1) + c
f(n+2) = f(n+1) + f(n) + c
.................... so on

Таким образом, обычно мы не можем получить это через предыдущий способ, но как насчет добавления c как состояния:

      |  f(n)  |   | f(n+1) |
  M X | f(n-1) | = |  f(n)  |
      |    c   |   |    c   |

Теперь его не так сложно создать M. Вот как это делается, но не забудьте проверить:

  | 1 1 1 |     |  f(n)  |     | f(n+1) |
  | 1 0 0 |  X  | f(n-1) |  =  |  f(n)  |
  | 0 0 1 |     |    c   |     |    c   |

Тип 5:

Положим все: find f(n) = a X f(n-1) + c X f(n-3) + d X f(n-4) + e . Давайте оставим это как упражнение для вас. Сначала попробуйте выяснить состояния и матрицу M. И проверьте, соответствует ли это вашему решению. Также найдите матрицы A и B.

| a 0 c d 1 |
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 0 1 |

Тип 6:

Иногда повторение дается так:

f(n) = f(n-1)   -> if n is odd
f(n) = f(n-2)   -> if n is even

Короче:

f(n) = (n&1) X f(n-1) + (!(n&1)) X f(n-2)

Здесь мы можем разбить функции на основе нечетного четного и сохранить для них две разные матрицы и рассчитать их отдельно.

Тип 7:

Чувствовать себя слишком уверенно? Повезло тебе. Иногда нам может потребоваться поддерживать более одного повторения, где они заинтересованы. Например, пусть повторение re; atopm будет:

g(n) = 2g(n-1) + 2g(n-2) + f(n)

Здесь рекурсия g (n) зависит от f(n) и это можно вычислить в той же матрице, но с увеличенными размерами. Из них сначала создадим матрицы A и B.

 Matrix A            Matrix B
|  g(n)  |          | g(n+1) |
| g(n-1) |          |  g(n)  |
| f(n+1) |          | f(n+2) |
|  f(n)  |          | f(n+1) |

Здесь g(n+1) = 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n) . Теперь, используя описанные выше процессы, мы можем найти объективную матрицу M :

| 2 2 1 0 |
| 1 0 0 0 |
| 0 0 2 2 |
| 0 0 1 0 |

Итак, это основные категории рекуррентных отношений, которые используются для решения этой простой методики.