Número de secuencias que tiene HEAD en posiciones alternas a la derecha del primer HEAD

Dado que se lanza una moneda N veces. La tarea es encontrar el número total de la secuencia de lanzamientos tal que después de la primera cara desde la izquierda, todas las posiciones alternas a la derecha estén ocupadas solo por la cara. Las posiciones excepto la posición alterna pueden ser ocupadas por cualquiera de cabeza o cola. 
Por ejemplo, si está lanzando una moneda 10 veces (N = 10) y la primera cara aparece en la tercera posición, todas las demás posiciones alternas a la derecha son 5, 7, 9…

Ejemplos: 

Entrada: N = 2 
Salida: 4 
Todas las combinaciones posibles serán TT, TH, HT, HH.

Entrada: N = 3 
Salida: 6 
Todas las combinaciones posibles serán TTT, TTH, THT, THH, HTH, HHH. 
En este caso, HHT & HTT no es posible porque en esta combinación 
no se cumple la condición de cabezas alternas. Por lo tanto, la respuesta será 6.  

Aproximación: 
Si la secuencia debe comenzar con una cola, entonces todas las posibles secuencias de longitud N-1 son válidas. Ahora, si la secuencia debe comenzar con una cara, entonces cada índice impar en la secuencia (asumiendo que la secuencia está basada en 1) será cara, y el resto de los N/2 lugares pueden ser cara o cruz. Por lo tanto, la fórmula recursiva para el problema anterior será:  

f(N) = f(N-1) + 2floor(N/2)

Cálculo Matemático: 

Let fo(N) and fe(N) be the functions 
that are defined for the odd and even values of N respectively.

 fo(N) =  fe(N-1) + 2(N-1)/2
 fe(N) =  fo(N-1) + 2N/2

From above equation compute
 fo(N) = fo(N-2) + 2(N-1)/2 + 2(N-1)/2
 fe(N) = fe(N-2) + 2N/2 + 2(N-2)/2

Base Case: 
 fo(1) = 2
 fe(0) = 1

By using the above equation, compute the following results :
 fo(N) - fo(N-2) =  2(N-1)/2 + 2(N-1)/2
 fo(N) - fo(N-2) =  2(N+1)/2 

By taking the sum of above equation for all odd values of N, 
below thing is computed.  
 fo(N) - fo(N-2) + fo(N-1) - fo(N-3) + ...... + fo(3) - fo(1) = 
 22 + 23 + 24 + ..... + 2(N+1)/2

Hence on summation,
fo(N) - fo(1) = SUM[ n = 0 to (N+1)/2 ] 2n - 21 - 20

By using sum of geometric progression
fo(N) = 2( N + 1 ) / 2 + 2( N + 1 ) / 2 - 2

Similarly, find fe(N) :
 fe(N) = fe(N-2) + 2N/2 + 2(N-2)/2
 fe(N) - fe(0) = SUM[ n = 0 to N/2 ] 2n - 20 - SUM[ n = 0 to (N-1)/2 ] 2n

By using sum of geometric progression
fe(N) = 2 (N / 2) + 1 + 2 N / 2 - 2

La fórmula final será la siguiente: 

f(N) = 2 ^(N+1)/2 + 2 ^(N+1)/2 – 2 , si N es impar
f(N) = 2 ^{(N/2) + 1} + 2 ^N/2 – 2 , si N es par

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find number of sequences
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate total sequences possible
int findAllSequence(int N)
{
 
    // Value of N is even
    if (N % 2 == 0) {
        return pow(2, N / 2 + 1) + pow(2, N / 2) - 2;
    }
    // Value of N is odd
    else {
        return pow(2, (N + 1) / 2) + pow(2, (N + 1) / 2) - 2;
    }
}
 
// Driver code
int main()
{
    int N = 2;
    cout << findAllSequence(N) << endl;
    return 0;
}

// Java program to find
// number of sequences
import java.io.*;
 
class GFG
{
 
// function to calculate
// total sequences possible
static int findAllSequence(int N)
{
 
    // Value of N is even
    if (N % 2 == 0)
    {
        return (int)(Math.pow(2, N / 2 + 1) +
                     Math.pow(2, N / 2) - 2);
    }
     
    // Value of N is odd
    else
    {
        return (int)(Math.pow(2, (N + 1) / 2) +
                     Math.pow(2, (N + 1) / 2) - 2);
    }
}
 
// Driver code
public static void main (String[] args)
{
    int N = 2;
    System.out.print( findAllSequence(N));
}
}
 
// This code is contributed
// by anuj_67.

# Python3 program to find number
# of sequences
 
# function to calculate total
# sequences possible
def findAllSequence(N):
 
    # Value of N is even
    if (N % 2 == 0):
        return (pow(2, N / 2 + 1) +
                pow(2, N / 2) - 2);
    # Value of N is odd
    else:
        return (pow(2, (N + 1) / 2) +
                pow(2, (N + 1) / 2) - 2);
 
# Driver code
N = 2;
print(int(findAllSequence(N)));
 
# This code is contributed by mits

// C# program to find
// number of sequences
using System;
public class GFG{
 
  
    // function to calculate
    // total sequences possible
    static int findAllSequence(int N)
    {
 
        // Value of N is even
        if (N % 2 == 0)
        {
            return (int)(Math.Pow(2, N / 2 + 1) +
                         Math.Pow(2, N / 2) - 2);
        }
 
        // Value of N is odd
        else
        {
            return (int)(Math.Pow(2, (N + 1) / 2) +
                         Math.Pow(2, (N + 1) / 2) - 2);
        }
    }
 
    // Driver code
    public static void Main ()
    {
        int N = 2;
        Console.WriteLine( findAllSequence(N));
    }
}
 
// This code is contributed by 29AjayKumar

<?php
// PHP program to find number of sequences
 
// function to calculate total
// sequences possible
function findAllSequence($N)
{
 
    // Value of N is even
    if ($N % 2 == 0)
    {
        return pow(2, $N / 2 + 1) +
               pow(2, $N / 2) - 2;
    }
     
    // Value of N is odd
    else
    {
        return pow(2, ($N + 1) / 2) +
               pow(2, ($N + 1) / 2) - 2;
    }
}
 
// Driver code
$N = 2;
echo findAllSequence($N);
 
// This code is contributed by mits
?>

<script>
    // Javascript program to find number of sequences
     
    // function to calculate
    // total sequences possible
    function findAllSequence(N)
    {
   
        // Value of N is even
        if (N % 2 == 0)
        {
            return (Math.pow(2, N / 2 + 1) +
                         Math.pow(2, N / 2) - 2);
        }
   
        // Value of N is odd
        else
        {
            return (Math.pow(2, (N + 1) / 2) +
                         Math.pow(2, (N + 1) / 2) - 2);
        }
    }
     
    let N = 2;
      document.write(findAllSequence(N));
     
</script>

4

Complejidad de tiempo : O (LogN)