Encuentre el término N (un ejemplo de exponenciación matricial)

Posted on by Rudeus Greyrat

Se nos da una función recursiva que describe enésimos términos en forma de otros términos. En este artículo, hemos tomado ejemplos específicos. 
T_{n} = 2*T_{n-1}+3*T{n-2} \\ Dado, T_0=1 T_1=1
Ahora te dan n, y tienes que encontrar el término n utilizando la fórmula anterior.

Ejemplos: 

Input : n = 2
Output : 5

Input : n = 3
Output :13

Requisito previo: 
enfoque básico: este problema se puede resolver simplemente iterando sobre los n términos. Cada vez que encuentre un término, use este término para encontrar el siguiente, y así sucesivamente. Pero la complejidad temporal de este problema es de orden O(n).

Enfoque optimizado 
Todos aquellos problemas en los que un término es una función de otros términos de forma lineal. Luego, estos se pueden resolver usando Matrix (consulte: Exponenciación de Matrix ). Primero, hacemos una array de transformación y luego usamos la exponenciación de arrays para encontrar el término N. 
 

El método paso a paso incluye: 

Paso 1. Determine k el número de términos de los que depende T(i).  
Para nuestro ejemplo, T(i) depende de dos términos. Entonces, k = 2

Paso 2. Determinar los valores iniciales 
Como en este artículo se dan T0=1, T1=1.

Paso 3. Determinar TM, la array de transformación.  
Este es el paso más importante para resolver las relaciones de recurrencia. En este paso, tenemos que hacer la array de dimensión k*k. 
Tal que 
T(i)=TM*(vector de valor inicial)

Aquí vector de valor inicial es el vector que contiene un valor inicial. Llamamos a este vector como initial . 
$So, Initial Vector=\left[ \begin{array}{c} T_1 & T_0\\ \end{array} \right] $Now find Transformation matrix. $TM=\left[ \begin{array}{cc} 2 & 3\\ 1 & 0 \\ \end{array} \right]$Now, First row of T2 give us 2nd term. $T_2=\left[ \begin{array}{cc} 2 & 3\\ 1 & 0 \\ \end{array} \right]*\left[ \begin{array}{c} T_1 & T_0\\ \end{array} \right]$So, general term will be, First row of Tn. $T_n=\left[ \begin{array}{cc} 2 & 3\\ 1 & 0 \\ \end{array} \right]^{n-1}*\left[ \begin{array}{c} T_1 & T_0\\ \end{array} \right]$So, finally we have Tn=$TM^{n-1}*Intial Vector$And this power of matrix can be calculated using matrix exponenciation in O(logn).

A continuación se muestra el programa para implementar el enfoque anterior. 

C++

// CPP program to find n-th term of a recursive
// function using matrix exponentiation.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000009
 
#define ll long long int
 
ll power(ll n)
{
    if (n <= 1)
        return 1;
 
    // This power function returns first row of
    // {Transformation Matrix}^n-1*Initial Vector
    n--;
 
    // This is an identity matrix.
    ll res[2][2] = { 1, 0, 0, 1 };
 
    // this is Transformation matrix.
    ll tMat[2][2] = { 2, 3, 1, 0 };
 
    // Matrix exponentiation to calculate power of {tMat}^n-1
    // store res in "res" matrix.
    while (n) {
 
        if (n & 1) {
            ll tmp[2][2];
            tmp[0][0] = (res[0][0] * tMat[0][0] + res[0][1] * tMat[1][0]) % MOD;
            tmp[0][1] = (res[0][0] * tMat[0][1] + res[0][1] * tMat[1][1]) % MOD;
            tmp[1][0] = (res[1][0] * tMat[0][0] + res[1][1] * tMat[1][0]) % MOD;
            tmp[1][1] = (res[1][0] * tMat[0][1] + res[1][1] * tMat[1][1]) % MOD;
            res[0][0] = tmp[0][0];
            res[0][1] = tmp[0][1];
            res[1][0] = tmp[1][0];
            res[1][1] = tmp[1][1];
        }
        n = n / 2;
        ll tmp[2][2];
        tmp[0][0] = (tMat[0][0] * tMat[0][0] + tMat[0][1] * tMat[1][0]) % MOD;
        tmp[0][1] = (tMat[0][0] * tMat[0][1] + tMat[0][1] * tMat[1][1]) % MOD;
        tmp[1][0] = (tMat[1][0] * tMat[0][0] + tMat[1][1] * tMat[1][0]) % MOD;
        tmp[1][1] = (tMat[1][0] * tMat[0][1] + tMat[1][1] * tMat[1][1]) % MOD;
        tMat[0][0] = tmp[0][0];
        tMat[0][1] = tmp[0][1];
        tMat[1][0] = tmp[1][0];
        tMat[1][1] = tmp[1][1];
    }
 
    // res store {Transformation matrix}^n-1
    // hence will be first row of res*Initial Vector.
    return (res[0][0] * 1 + res[0][1] * 1) % MOD;
}
 
// Driver code
int main()
{
    ll n = 3;
    cout << power(n);
    return 0;
}

Java

// Java program to find n-th term of a recursive
// function using matrix exponentiation.
class GfG {
 
    static int MAX = 100;
    static int MOD = 1000000009;
    static int power(int n)
    {
        if (n <= 1) {
            return 1;
        }
 
        // This power function returns first row of
        // {Transformation Matrix}^n-1*Initial Vector
        n--;
 
        // This is an identity matrix.
        int res[][] = { { 1, 0 }, { 0, 1 } };
 
        // this is Transformation matrix.
        int tMat[][] = { { 2, 3 }, { 1, 0 } };
 
        // Matrix exponentiation to calculate power of {tMat}^n-1
        // store res in "res" matrix.
        while (n > 0) {
 
            if (n % 2 == 1) {
                int tmp[][] = new int[2][2];
                tmp[0][0] = (res[0][0] * tMat[0][0]
                             + res[0][1] * tMat[1][0])
                            % MOD;
                tmp[0][1] = (res[0][0] * tMat[0][1]
                             + res[0][1] * tMat[1][1])
                            % MOD;
                tmp[1][0] = (res[1][0] * tMat[0][0]
                             + res[1][1] * tMat[1][0])
                            % MOD;
                tmp[1][1] = (res[1][0] * tMat[0][1]
                             + res[1][1] * tMat[1][1])
                            % MOD;
                res[0][0] = tmp[0][0];
                res[0][1] = tmp[0][1];
                res[1][0] = tmp[1][0];
                res[1][1] = tmp[1][1];
            }
 
            n = n / 2;
            int tmp[][] = new int[2][2];
            tmp[0][0] = (tMat[0][0] * tMat[0][0]
                         + tMat[0][1] * tMat[1][0])
                        % MOD;
            tmp[0][1] = (tMat[0][0] * tMat[0][1]
                         + tMat[0][1] * tMat[1][1])
                        % MOD;
            tmp[1][0] = (tMat[1][0] * tMat[0][0]
                         + tMat[1][1] * tMat[1][0])
                        % MOD;
            tmp[1][1] = (tMat[1][0] * tMat[0][1]
                         + tMat[1][1] * tMat[1][1])
                        % MOD;
            tMat[0][0] = tmp[0][0];
            tMat[0][1] = tmp[0][1];
            tMat[1][0] = tmp[1][0];
            tMat[1][1] = tmp[1][1];
        }
 
        // res store {Transformation matrix}^n-1
        // hence wiint be first row of res*Initial Vector.
        return (res[0][0] * 1 + res[0][1] * 1) % MOD;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 3;
        System.out.println(power(n));
    }
}
 
// This code contributed by Rajput-Ji

Python3

# Python3 program to find n-th term of a recursive
# function using matrix exponentiation.
MOD = 1000000009;
 
def power(n):
    if (n <= 1):
        return 1;
 
    # This power function returns first row of
    # {Transformation Matrix}^n-1 * Initial Vector
    n-= 1;
 
    # This is an identity matrix.
    res = [[1, 0], [0, 1]];
 
    # this is Transformation matrix.
    tMat = [[2, 3], [1, 0]];
 
    # Matrix exponentiation to calculate
    # power of {tMat}^n-1 store res in "res" matrix.
    while (n):
        if (n & 1):
            tmp = [[0 for x in range(2)] for y in range(2)];
            tmp[0][0] = (res[0][0] * tMat[0][0] +
                        res[0][1] * tMat[1][0]) % MOD;
            tmp[0][1] = (res[0][0] * tMat[0][1] +
                        res[0][1] * tMat[1][1]) % MOD;
            tmp[1][0] = (res[1][0] * tMat[0][0] +
                        res[1][1] * tMat[1][0]) % MOD;
            tmp[1][1] = (res[1][0] * tMat[0][1] +
                        res[1][1] * tMat[1][1]) % MOD;
            res[0][0] = tmp[0][0];
            res[0][1] = tmp[0][1];
            res[1][0] = tmp[1][0];
            res[1][1] = tmp[1][1];
     
        n = n // 2;
        tmp = [[0 for x in range(2)] for y in range(2)];
        tmp[0][0] = (tMat[0][0] * tMat[0][0] +
                    tMat[0][1] * tMat[1][0]) % MOD;
        tmp[0][1] = (tMat[0][0] * tMat[0][1] +
                    tMat[0][1] * tMat[1][1]) % MOD;
        tmp[1][0] = (tMat[1][0] * tMat[0][0] +
                    tMat[1][1] * tMat[1][0]) % MOD;
        tmp[1][1] = (tMat[1][0] * tMat[0][1] +
                    tMat[1][1] * tMat[1][1]) % MOD;
        tMat[0][0] = tmp[0][0];
        tMat[0][1] = tmp[0][1];
        tMat[1][0] = tmp[1][0];
        tMat[1][1] = tmp[1][1];
 
    # res store {Transformation matrix}^n-1
    # hence will be first row of res * Initial Vector.
    return (res[0][0] * 1 + res[0][1] * 1) % MOD;
 
# Driver code
n = 3;
print(power(n));
     
# This code is contributed by mits

C#

// C# program to find n-th term of a recursive
// function using matrix exponentiation.
using System;
 
class GfG {
 
    // static int MAX = 100;
    static int MOD = 1000000009;
    static int power(int n)
    {
        if (n <= 1) {
            return 1;
        }
 
        // This power function returns first row of
        // {Transformation Matrix}^n-1*Initial Vector
        n--;
 
        // This is an identity matrix.
        int[, ] res = { { 1, 0 }, { 0, 1 } };
 
        // this is Transformation matrix.
        int[, ] tMat = { { 2, 3 }, { 1, 0 } };
 
        // Matrix exponentiation to calculate power of {tMat}^n-1
        // store res in "res" matrix.
        while (n > 0) {
 
            if (n % 2 == 1) {
                int[, ] tmp = new int[2, 2];
                tmp[0, 0] = (res[0, 0] * tMat[0, 0]
                             + res[0, 1] * tMat[1, 0])
                            % MOD;
                tmp[0, 1] = (res[0, 0] * tMat[0, 1]
                             + res[0, 1] * tMat[1, 1])
                            % MOD;
                tmp[1, 0] = (res[1, 0] * tMat[0, 0]
                             + res[1, 1] * tMat[1, 0])
                            % MOD;
                tmp[1, 1] = (res[1, 0] * tMat[0, 1]
                             + res[1, 1] * tMat[1, 1])
                            % MOD;
                res[0, 0] = tmp[0, 0];
                res[0, 1] = tmp[0, 1];
                res[1, 0] = tmp[1, 0];
                res[1, 1] = tmp[1, 1];
            }
 
            n = n / 2;
            int[, ] tmp1 = new int[2, 2];
            tmp1[0, 0] = (tMat[0, 0] * tMat[0, 0]
                          + tMat[0, 1] * tMat[1, 0])
                         % MOD;
            tmp1[0, 1] = (tMat[0, 0] * tMat[0, 1]
                          + tMat[0, 1] * tMat[1, 1])
                         % MOD;
            tmp1[1, 0] = (tMat[1, 0] * tMat[0, 0]
                          + tMat[1, 1] * tMat[1, 0])
                         % MOD;
            tmp1[1, 1] = (tMat[1, 0] * tMat[0, 1]
                          + tMat[1, 1] * tMat[1, 1])
                         % MOD;
            tMat[0, 0] = tmp1[0, 0];
            tMat[0, 1] = tmp1[0, 1];
            tMat[1, 0] = tmp1[1, 0];
            tMat[1, 1] = tmp1[1, 1];
        }
 
        // res store {Transformation matrix}^n-1
        // hence wiint be first row of res*Initial Vector.
        return (res[0, 0] * 1 + res[0, 1] * 1) % MOD;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 3;
        Console.WriteLine(power(n));
    }
}
 
// This code contributed by mits

PHP

<?php
// PHP program to find n-th term of a recursive
// function using matrix exponentiation.
$MOD = 1000000009;
 
function power($n)
{
    global $MOD;
    if ($n <= 1)
        return 1;
 
    // This power function returns first row of
    // {Transformation Matrix}^n-1*Initial Vector
    $n--;
 
    // This is an identity matrix.
    $res = array(array(1, 0), array(0, 1));
 
    // this is Transformation matrix.
    $tMat= array(array(2, 3), array(1, 0));
 
    // Matrix exponentiation to calculate
    // power of {tMat}^n-1 store res in "res" matrix.
    while ($n)
    {
        if ($n & 1)
        {
            $tmp = array_fill(0, 2, array_fill(0, 2, 0));
            $tmp[0][0] = ($res[0][0] * $tMat[0][0] +
                          $res[0][1] * $tMat[1][0]) % $MOD;
            $tmp[0][1] = ($res[0][0] * $tMat[0][1] +
                          $res[0][1] * $tMat[1][1]) % $MOD;
            $tmp[1][0] = ($res[1][0] * $tMat[0][0] +
                          $res[1][1] * $tMat[1][0]) % $MOD;
            $tmp[1][1] = ($res[1][0] * $tMat[0][1] +
                          $res[1][1] * $tMat[1][1]) % $MOD;
            $res[0][0] = $tmp[0][0];
            $res[0][1] = $tmp[0][1];
            $res[1][0] = $tmp[1][0];
            $res[1][1] = $tmp[1][1];
        }
        $n = (int)($n / 2);
        $tmp = array_fill(0, 2, array_fill(0, 2, 0));
        $tmp[0][0] = ($tMat[0][0] * $tMat[0][0] +
                      $tMat[0][1] * $tMat[1][0]) % $MOD;
        $tmp[0][1] = ($tMat[0][0] * $tMat[0][1] +
                      $tMat[0][1] * $tMat[1][1]) % $MOD;
        $tmp[1][0] = ($tMat[1][0] * $tMat[0][0] +
                      $tMat[1][1] * $tMat[1][0]) % $MOD;
        $tmp[1][1] = ($tMat[1][0] * $tMat[0][1] +
                      $tMat[1][1] * $tMat[1][1]) % $MOD;
        $tMat[0][0] = $tmp[0][0];
        $tMat[0][1] = $tmp[0][1];
        $tMat[1][0] = $tmp[1][0];
        $tMat[1][1] = $tmp[1][1];
    }
 
    // res store {Transformation matrix}^n-1
    // hence will be first row of res*Initial Vector.
    return ($res[0][0] * 1 + $res[0][1] * 1) % $MOD;
}
 
// Driver code
$n = 3;
echo power($n);
     
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to find n-th term of a recursive
// function using matrix exponentiation.
var MOD = 1000000009;
 
function power(n)
{
    if (n <= 1)
        return 1;
 
    // This power function returns first row of
    // {Transformation Matrix}^n-1*Initial Vector
    n--;
 
    // This is an identity matrix.
    var res = [[1, 0,], [0, 1]];
 
    // this is Transformation matrix.
    var tMat = [[2, 3],[1, 0]];
 
    // Matrix exponentiation to calculate power of {tMat}^n-1
    // store res in "res" matrix.
    while (n) {
 
        if (n & 1) {
            var tmp = Array.from(Array(2), ()=> Array(2));
            tmp[0][0] = (res[0][0] * tMat[0][0] + res[0][1] * tMat[1][0]) % MOD;
            tmp[0][1] = (res[0][0] * tMat[0][1] + res[0][1] * tMat[1][1]) % MOD;
            tmp[1][0] = (res[1][0] * tMat[0][0] + res[1][1] * tMat[1][0]) % MOD;
            tmp[1][1] = (res[1][0] * tMat[0][1] + res[1][1] * tMat[1][1]) % MOD;
            res[0][0] = tmp[0][0];
            res[0][1] = tmp[0][1];
            res[1][0] = tmp[1][0];
            res[1][1] = tmp[1][1];
        }
        n = parseInt(n / 2);
        var tmp = Array.from(Array(2), ()=> Array(2));
        tmp[0][0] = (tMat[0][0] * tMat[0][0] + tMat[0][1] * tMat[1][0]) % MOD;
        tmp[0][1] = (tMat[0][0] * tMat[0][1] + tMat[0][1] * tMat[1][1]) % MOD;
        tmp[1][0] = (tMat[1][0] * tMat[0][0] + tMat[1][1] * tMat[1][0]) % MOD;
        tmp[1][1] = (tMat[1][0] * tMat[0][1] + tMat[1][1] * tMat[1][1]) % MOD;
        tMat[0][0] = tmp[0][0];
        tMat[0][1] = tmp[0][1];
        tMat[1][0] = tmp[1][0];
        tMat[1][1] = tmp[1][1];
    }
 
    // res store {Transformation matrix}^n-1
    // hence will be first row of res*Initial Vector.
    return (res[0][0] * 1 + res[0][1] * 1) % MOD;
}
 
// Driver code
var n = 3;
document.write( power(n));
 
</script>
Producción: 

13

 

Complejidad de tiempo: O (Log n)
La misma idea se usa para encontrar el n-ésimo número de Fibonacci en O (Log n)
 

Publicación traducida automáticamente

Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *