Рубрики

Матрица возведения в степень

Это один из наиболее часто используемых методов в конкурентном программировании . Давайте сначала рассмотрим простой вопрос.

Какова минимальная сложность времени, чтобы найти n-е число Фибоначчи?
Мы можем найти n-ое число Фибоначчи в O (Log n) времени, используя матричное возведение в степень. Обратитесь к методу 4 этого для деталей. В этом посте обсуждается общая реализация Matrix Exponentiation.

For solving the matrix exponentiation we are assuming a
linear recurrence equation like below:

F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3)   for n >= 3 
                                 . . . . . Equation (1)
where a, b and c are constants. 

For this recurrence relation, it depends on three previous values. 
Now we will try to represent Equation (1) in terms of the matrix. 

[First Matrix] = [Second matrix] * [Third Matrix]
| F(n)   |     =   Matrix 'C'    *  | F(n-1) |
| F(n-1) |                          | F(n-2) |
| F(n-2) |                          | F(n-3) |
 
Dimension of the first matrix is 3 x 1 . 
Dimension of the third matrix is also 3 x 1. 

So the dimension of the second matrix must be 3 x 3 
[For multiplication rule to be satisfied.]

Now we need to fill the Matrix 'C'. 

So according to our equation. 
F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3)
F(n-1) = F(n-1)
F(n-2) = F(n-2)

C = [a b c
     1 0 0
     0 1 0]

Now the relation between matrix becomes : 
[First Matrix]  [Second matrix]       [Third Matrix]
| F(n)   |  =  | a b c |  *           | F(n-1) |
| F(n-1) |     | 1 0 0 |              | F(n-2) |
| F(n-2) |     | 0 1 0 |              | F(n-3) |

Lets assume the initial values for this case :- 
F(0) = 0
F(1) = 1
F(2) = 1

So, we need to get F(n) in terms of these values.

So, for n = 3 Equation (1) changes to 
| F(3) |  =  | a b c |  *           | F(2) |
| F(2) |     | 1 0 0 |              | F(1) |
| F(1) |     | 0 1 0 |              | F(0) |

Now similarly for n = 4 
| F(4) |  =  | a b c |  *           | F(3) |
| F(3) |     | 1 0 0 |              | F(2) |
| F(2) |     | 0 1 0 |              | F(1) |

             - - - -  2 times - - -
| F(4) |  =  | a b c |  * | a b c | *       | F(2) |
| F(3) |     | 1 0 0 |    | 1 0 0 |         | F(1) |
| F(2) |     | 0 1 0 |    | 0 1 0 |         | F(0) |


So for n, the Equation (1) changes to 

                - - - - - - - - n -2 times - - - -  -       
| F(n)   |  =  | a b c | * | a b c | * ... * | a b c | * | F(2) |
| F(n-1) |     | 1 0 0 |   | 1 0 0 |         | 1 0 0 |   | F(1) |
| F(n-2) |     | 0 1 0 |   | 0 1 0 |         | 0 1 0 |   | F(0) |


| F(n)   |  =  [ | a b c | ] ^ (n-2)   *  | F(2) |
| F(n-1) |     [ | 1 0 0 | ]              | F(1) |
| F(n-2) |     [ | 0 1 0 | ]              | F(0) |

Таким образом, мы можем просто умножить нашу вторую матрицу n-2 раза, а затем умножить ее на третью матрицу, чтобы получить результат. Умножение можно выполнить за время (log n), используя алгоритм Power Divide and Conquer (см. Это или это )

Рассмотрим проблему нахождения n-го члена ряда, определенного с использованием рекуррентности ниже.

n'th term,
    F(n) = F(n-1) + F(n-2) + F(n-3), n >= 3
Base Cases :
    F(0) = 0, F(1) = 1, F(2) = 1

Мы можем найти n-й термин, используя следующее:

Putting a = 1, b = 1 and c = 1 in above formula

| F(n)   |  =  [ | 1 1 1 | ] ^ (n-2)   *  | F(2) |
| F(n-1) |     [ | 1 0 0 | ]              | F(1) |
| F(n-2) |     [ | 0 1 0 | ]              | F(0) |

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска значения f (n), где f (n)
// определяется как
// F (n) = F (n-1) + F (n-2) + F (n-3), n> = 3
// Базовые случаи:
// F (0) = 0, F (1) = 1, F (2) = 1
#include<bits/stdc++.h>

using namespace std;

  
// Функция полезности для умножения двух матриц
// a [] [] и b [] []. Результат умножения
// сохраняется обратно в b [] []

void multiply(int a[3][3], int b[3][3])

{

    // Создание вспомогательной матрицы для хранения элементов

    // матрицы умножения

    int mul[3][3];

    for (int i = 0; i < 3; i++)

    {

        for (int j = 0; j < 3; j++)

        {

            mul[i][j] = 0;

            for (int k = 0; k < 3; k++)

                mul[i][j] += a[i][k]*b[k][j];

        }

    }

  

    // сохраняем результат умножения в [] []

    for (int i=0; i<3; i++)

        for (int j=0; j<3; j++)

            a[i][j] = mul[i][j];  // Обновление нашей матрицы

}

  
// Функция для вычисления поднятия F до мощности n-2.

int power(int F[3][3], int n)

{

    int M[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}};

  

    // Умножаем его на начальные значения, т.е.

    // F (0) = 0, F (1) = 1, F (2) = 1

    if (n==1)

        return F[0][0] + F[0][1];

  

    power(F, n/2);

  

    multiply(F, F);

  

    if (n%2 != 0)

        multiply(F, M);

  

    // Умножаем его на начальные значения, т.е.

    // F (0) = 0, F (1) = 1, F (2) = 1

    return F[0][0] + F[0][1] ;

}

  
// Возвращаем n-й член ряда, определенного ниже
// рекуррентное отношение.
// f (n) определяется как
// f (n) = f (n-1) + f (n-2) + f (n-3), n> = 3
// Базовые случаи:
// f (0) = 0, f (1) = 1, f (2) = 1

int findNthTerm(int n)

{

  

    int F[3][3] = {{1,1,1}, {1,0,0}, {0,1,0}} ;

  

    // Базовые случаи

    if(n==0)

        return 0;

    if(n==1 || n==2)

        return 1;

  

    return power(F, n-2);

}

  
// Код драйвера

int main()

{

   int n = 5;

  

   cout << "F(5) is " << findNthTerm(n);

  

   return 0;

}

Джава

// JAVA-программа для поиска значения f (n) где
// f (n) определяется как
// F (n) = F (n-1) + F (n-2) + F (n-3), n> = 3
// Базовые случаи:
// F (0) = 0, F (1) = 1, F (2) = 1

import java.io.*;

  

class GFG {

      

    // Функция полезности для умножения двух

    // матрицы a [] [] и b [] [].

    // Результат умножения

    // сохраняется обратно в b [] []

    static void multiply(int a[][], int b[][])

    {

        // Создание вспомогательной матрицы для

        // сохраняем элементы

        // матрица умножения

        int mul[][] = new int[3][3];

        for (int i = 0; i < 3; i++)

        {

            for (int j = 0; j < 3; j++)

            {

                mul[i][j] = 0;

                for (int k = 0; k < 3; k++)

                    mul[i][j] += a[i][k]

                                * b[k][j];

            }

        }

      

        // сохраняем умножение

        // результат в [] []

        for (int i=0; i<3; i++)

            for (int j=0; j<3; j++)

              

                // Обновление нашей матрицы

                a[i][j] = mul[i][j]; 

    }

      

    // Функция для вычисления F повышение до

    // мощность n-2.

    static int power(int F[][], int n)

    {

        int M[][] = {{1, 1, 1}, {1, 0, 0},

                               {0, 1, 0}};

      

        // Умножаем это на начальные значения

        // т.е. с F (0) = 0, F (1) = 1,

        // F (2) = 1

        if (n == 1)

            return F[0][0] + F[0][1];

      

        power(F, n / 2);

      

        multiply(F, F);

      

        if (n%2 != 0)

            multiply(F, M);

      

        // Умножаем это на начальные значения

        // т.е. с F (0) = 0, F (1) = 1,

        // F (2) = 1

        return F[0][0] + F[0][1] ;

    }

      

    // Возвращаем n-й член определенной серии

    // используя нижеприведенное соотношение.

    // f (n) определяется как

    // f (n) = f (n-1) + f (n-2) + f (n-3), n> = 3

    // Базовые случаи:

    // f (0) = 0, f (1) = 1, f (2) = 1

    static int findNthTerm(int n)

    {

        int F[][] = {{1, 1, 1}, {1, 0, 0},

                                  {0, 1, 0}} ;

      

        return power(F, n-2);

    }

      

    // Код драйвера

    public static void main (String[] args) {

          

        int n = 5;

          

        System.out.println("F(5) is "

                           + findNthTerm(n));

    }

}

  
// Этот код предоставлен vt_m.

python3

# Python3 программа для поиска значения f (n)
# где f (n) определяется как
# F (n) = F (n-1) + F (n-2) + F (n-3), n> = 3
# Базовые случаи:
# F (0) = 0, F (1) = 1, F (2) = 1

  
# Функция полезности для умножения двух
# матрицы a [] [] и b [] []. умножение
# результат сохраняется обратно в b [] []

def multiply(a, b):

      

    # Создание вспомогательной матрицы

    # хранить элементы

    # матрица умножения

    mul = [[0 for x in range(3)]

              for y in range(3)];

    for i in range(3):

        for j in range(3):

            mul[i][j] = 0;

            for k in range(3):

                mul[i][j] += a[i][k] * b[k][j];

  

    # хранение умножения

    # результат в [] []

    for i in range(3):

        for j in range(3):

            a[i][j] = mul[i][j]; # Обновление нашей матрицы

    return a;

  
# Функция для вычисления F рейз
# к власти n-2.

def power(F, n):

  

    M = [[1, 1, 1], [1, 0, 0], [0, 1, 0]];

  

    # Умножьте это с начальными значениями т.е.

    # с F (0) = 0, F (1) = 1, F (2) = 1

    if (n == 1):

        return F[0][0] + F[0][1];

  

    power(F, int(n / 2));

  

    F = multiply(F, F);

  

    if (n % 2 != 0):

        F = multiply(F, M);

  

    # Умножьте это с начальными значениями т.е.

    # с F (0) = 0, F (1) = 1, F (2) = 1

    return F[0][0] + F[0][1] ;

  
# Вернуть n-й член определенной серии
# используя нижеприведенное соотношение.
# f (n) определяется как
# f (n) = f (n-1) + f (n-2) + f (n-3), n> = 3
# Базовые случаи:
# f (0) = 0, f (1) = 1, f (2) = 1

def findNthTerm(n):

    F = [[1, 1, 1], [1, 0, 0], [0, 1, 0]];

  

    return power(F, n - 2);

  
# Код драйвера

n = 5;

  

print("F(5) is"

      findNthTerm(n));

  
# Этот код предоставлен mits

C #

// C # программа для поиска значения f (n) где
// f (n) определяется как
// F (n) = F (n-1) + F (n-2) + F (n-3), n> = 3
// Базовые случаи:
// F (0) = 0, F (1) = 1, F (2) = 1

using System;

  

class GFG {

  

    // Функция полезности для умножения двух

    // матрицы a [] [] и b [] []. умножение

    // результат сохраняется обратно в b [] []

    static void multiply(int[, ] a, int[, ] b)

    {

          

        // Создание вспомогательной матрицы для хранения

        // элементы матрицы умножения

        int[, ] mul = new int[3, 3];

          

        for (int i = 0; i < 3; i++) {

            for (int j = 0; j < 3; j++) {

                mul[i, j] = 0;

                for (int k = 0; k < 3; k++)

                    mul[i, j] += a[i, k] * b[k, j];

            }

        }

  

        // сохраняем результат умножения

        // в[][]

        for (int i = 0; i < 3; i++)

            for (int j = 0; j < 3; j++)

              

                // Обновление нашей матрицы

                a[i, j] = mul[i, j]; 

    }

  

    // Функция для вычисления поднятия F до мощности n-2.

    static int power(int[, ] F, int n)

    {

          

        int[, ] M = { { 1, 1, 1 }, { 1, 0, 0 }, 

                                   { 0, 1, 0 } };

  

        // Умножаем это на начальные значения т.е.

        // с F (0) = 0, F (1) = 1, F (2) = 1

        if (n == 1)

            return F[0, 0] + F[0, 1];

  

        power(F, n / 2);

  

        multiply(F, F);

  

        if (n % 2 != 0)

            multiply(F, M);

  

        // Умножаем это на начальные значения т.е.

        // с F (0) = 0, F (1) = 1, F (2) = 1

        return F[0, 0] + F[0, 1];

    }

  

    // Возвращаем n-й член определенной серии

    // используя нижеприведенное соотношение.

    // f (n) определяется как

    // f (n) = f (n-1) + f (n-2) + f (n-3), n> = 3

    // Базовые случаи:

    // f (0) = 0, f (1) = 1, f (2) = 1

    static int findNthTerm(int n)

    {

        int[, ] F = { { 1, 1, 1 }, { 1, 0, 0 },

                                 { 0, 1, 0 } };

  

        return power(F, n - 2);

    }

  

    // Код драйвера

    public static void Main()

    {

        int n = 5;

          

        Console.WriteLine("F(5) is " 

                      + findNthTerm(n));

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP-программа для поиска значения f (n), где f (n)
// определяется как
// F (n) = F (n-1) + F (n-2) + F (n-3), n> = 3
// Базовые случаи:
// F (0) = 0, F (1) = 1, F (2) = 1

  
// Функция полезности для умножения двух матриц
// a [] [] и b [] []. Результат умножения
// сохраняется обратно в b [] []

function multiply(&$a, &$b)

{

    // Создание вспомогательной матрицы для хранения

    // элементы матрицы умножения

    $mul = array_fill(0, 3, 

           array_fill(0, 3, 0));

    for ($i = 0; $i < 3; $i++)

    {

        for ($j = 0; $j < 3; $j++)

        {

            $mul[$i][$j] = 0;

            for ($k = 0; $k < 3; $k++)

                $mul[$i][$j] += $a[$i][$k] * 

                                $b[$k][$j];

        }

    }

  

    // сохраняем результат умножения в [] []

    for ($i = 0; $i < 3; $i++)

        for ($j = 0; $j < 3; $j++)

            $a[$i][$j] = $mul[$i][$j]; // Обновление нашей матрицы

}

  
// Функция для вычисления поднятия F до мощности n-2.

function power($F, $n)

{

    $M = array(array(1, 1, 1), 

               array(1, 0, 0), 

               array(0, 1, 0));

  

    // Умножаем его на начальные значения, т.е.

    // F (0) = 0, F (1) = 1, F (2) = 1

    if ($n == 1)

        return $F[0][0] + $F[0][1];

  

    power($F, (int)($n / 2));

  

    multiply($F, $F);

  

    if ($n % 2 != 0)

        multiply($F, $M);

  

    // Умножаем его на начальные значения, т.е.

    // F (0) = 0, F (1) = 1, F (2) = 1

    return $F[0][0] + $F[0][1] ;

}

  
// Возвращаем n-й член определенной серии
// используя нижеприведенное соотношение.
// f (n) определяется как
// f (n) = f (n-1) + f (n-2) + f (n-3), n> = 3
// Базовые случаи:
// f (0) = 0, f (1) = 1, f (2) = 1

function findNthTerm($n)

{

    $F = array(array(1, 1, 1),

               array(1, 0, 0),

               array(0, 1, 0));

  

    return power($F, $n - 2);

}

  
// Код драйвера

$n = 5;

  

echo "F(5) is " . findNthTerm($n);

  
// Этот код предоставлен mits
?>


Выход :

F(5) is 7

Сложность времени этого решения: O (log n)

Эта статья предоставлена Абхираджем Смитом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Матрица возведения в степень

0.00 (0%) 0 votes