¿De cuántas maneras volverá la pelota al primer niño después de N vueltas?

Cuatro niños están jugando un juego con una pelota. En cada turno, el jugador (que tiene la pelota en ese momento) la pasa a un jugador diferente al azar. Bob siempre comienza el juego. La tarea es encontrar de cuántas maneras la pelota regresará a Bob después de N pases.
Ejemplos: 
 

Entrada: N = 3 
Salida: 6 
Aquí están todas las formas posibles: 
Bob -> Boy1 -> Boy2 -> Bob 
Bob -> Boy1 -> Boy3 -> Bob 
Bob -> Boy2 -> Boy1 -> Bob 
Bob -> Boy2 – > Chico3 -> Bob 
Bob -> Chico3 -> Chico1 -> Bob 
Bob -> Chico3 -> Chico2 -> Bob
Entrada: N = 10 
Salida: 14763 
 

Enfoque: Deje que el número de secuencias que vuelven a Bob después de N pases sea P(N) . Hay dos casos, o el paso N – 2 es para Bob o no. Tenga en cuenta que Bob no puede tener el balón en (N – 1) ^pase porque entonces no tendrá el balón en el ^pase N.
 

1. Caso 1: Si el pase N – 2 es para Bob, entonces el pase N – 1 puede ser para cualquiera de los otros 3 niños. Por lo tanto, el número de tales secuencias es 3 * P(N – 2) .
2. Caso 2: Si el pase N – 2 no es para Bob, entonces el pase N – 1 es para uno de los 2 niños que no sea Bob ni el que tiene el balón en la mano. Entonces, sustituya a Bob por el receptor del pase N – 1 y obtenga una secuencia N – 1 única. Entonces, el número de tales secuencias es 2 * P(N – 1) .

Por lo tanto, la relación de recurrencia será P(N) = 2 * P(N – 1) + 3 * P(N – 2) donde P(0) = 1 y P(1) = 0 .
Después de resolver la relación de recurrencia, P(N) = (3 ^N + 3 * (-1 ^N )) / 4
A continuación se muestra la implementación del enfoque anterior: 
 

// Function to return the number of
// sequences that get back to Bob
#include <bits/stdc++.h>
using namespace std;
 
int numSeq(int n)
{
    return (pow(3, n) + 3 * pow(-1, n)) / 4;
}
 
// Driver code
int main()
{
    int N = 10;
    printf("%d", numSeq(N));
    return 0;
}
 
// This code is contributed by Mohit kumar

// Function to return the number of
// sequences that get back to Bob
import java.util.*;
 
class GFG
{
 
static int numSeq(int n)
{
    return (int) ((Math.pow(3, n) + 3 *
                    Math.pow(-1, n)) / 4);
}
 
// Driver code
public static void main(String[] args)
{
    int N = 10;
    System.out.printf("%d", numSeq(N));
}
}
 
// This code is contributed by Rajput-Ji

# Function to return the number of
# sequences that get back to Bob
def numSeq(n):
    return (pow(3, n) + 3 * pow(-1, n))//4
     
# Driver code
N = 10
print(numSeq(N))

// C# implementation of the above approach
using System;
 
// Function to return the number of
// sequences that get back to Bob
class GFG
{
 
    static int numSeq(int n)
    {
        return (int) ((Math.Pow(3, n) + 3 *
                       Math.Pow(-1, n)) / 4);
    }
     
    // Driver code
    public static void Main()
    {
        int N = 10;
        Console.WriteLine(numSeq(N));
    }
}
 
// This code is contributed by AnkitRai01

<script>
 
// Function to return the number of
// sequences that get back to Bob
function numSeq(n)
{
    return  Math.floor((Math.pow(3, n) + 3 * Math.pow(-1, n)) / 4);
}
 
// Driver code
 
    let N = 10;
    document.write(numSeq(N));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

14763

Complejidad de tiempo: O (log n)

Espacio Auxiliar: O(1)