Contar formas de expresar ‘n’ como suma de enteros impares

Dado un entero positivo n. Cuente el número total de formas de expresar ‘n’ como suma de números enteros positivos impares. 
 

Input: 4
Output: 3

Explanation
There are only three ways to write 4
as sum of odd integers:
1. 1 + 3
2. 3 + 1
3. 1 + 1 + 1 + 1

Input: 5
Output: 5

El enfoque simple es encontrar la naturaleza recursiva del problema. El número ‘n’ se puede escribir como la suma de enteros impares de (n-1) ^número o (n-2) ^número . Deje que el número total de formas de escribir ‘n’ sea formas (n). El valor de ‘vías (n)’ se puede escribir mediante una fórmula recursiva de la siguiente manera: 
 

ways(n) = ways(n-1) + ways(n-2)

La expresión anterior es en realidad la expresión de los números de Fibonacci . Por lo tanto, el problema se reduce a encontrar el n ^-ésimo número de Fibonacci. 
 

ways(1) = fib(1) = 1
ways(2) = fib(2) = 1
ways(3) = fib(2) = 2
ways(4) = fib(4) = 3

// C++ program to count ways to write
// number as sum of odd integers
#include<iostream>
using namespace std;
 
// Function to calculate n'th Fibonacci number
int fib(int n)
{
  /* Declare an array to store Fibonacci numbers. */
  int f[n+1];
  int i;
 
  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;
 
  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }
 
  return f[n];
}
 
// Return number of ways to write 'n'
// as sum of odd integers
int countOddWays(int n)
{
    return fib(n);
}
 
// Driver code
int main()
{
    int n = 4;
    cout << countOddWays(n) << "\n";
 
    n = 5;
    cout << countOddWays(n);
   return 0;
}

// Java program to count ways to write
// number as sum of odd integers
import java.util.*;
 
class GFG {
     
// Function to calculate n'th Fibonacci number
static int fib(int n) {
     
    /* Declare an array to store Fibonacci numbers. */
    int f[] = new int[n + 1];
    int i;
 
    /* 0th and 1st number of the series are 0 and 1*/
    f[0] = 0;
    f[1] = 1;
 
    for (i = 2; i <= n; i++) {
         
    /* Add the previous 2 numbers in the series
        and store it */
    f[i] = f[i - 1] + f[i - 2];
    }
 
    return f[n];
}
 
// Return number of ways to write 'n'
// as sum of odd integers
static int countOddWays(int n)
{
    return fib(n);
}
 
// Driver code
public static void main(String[] args) {
     
    int n = 4;
    System.out.print(countOddWays(n) + "\n");
 
    n = 5;
    System.out.print(countOddWays(n));
}
}
 
// This code is contributed by Anant Agarwal.

# Python code to count ways to write
# number as sum of odd integers
 
# Function to calculate n'th
# Fibonacci number
def fib( n ):
 
    # Declare a list to store
    # Fibonacci numbers.
    f=list()
     
    # 0th and 1st number of the
    # series are 0 and 1
    f.append(0)
    f.append(1)
     
    i = 2
    while i<n+1:
 
        # Add the previous 2 numbers
        # in the series and store it
        f.append(f[i-1] + f[i-2])
        i += 1
    return f[n]
 
# Return number of ways to write 'n'
# as sum of odd integers
def countOddWays( n ):
    return fib(n)
 
# Driver code
n = 4
print(countOddWays(n))
n = 5
print(countOddWays(n))
 
# This code is contributed by "Sharad_Bhardwaj"

// C# program to count ways to write
// number as sum of odd integers
using System;
 
class GFG {
     
    // Function to calculate n'th
    // Fibonacci number
    static int fib(int n) {
         
        /* Declare an array to store
        Fibonacci numbers. */
        int []f = new int[n + 1];
        int i;
     
        /* 0th and 1st number of the
        series are 0 and 1*/
        f[0] = 0;
        f[1] = 1;
     
        for (i = 2; i <= n; i++)
        {
             
            /* Add the previous 2 numbers
            in the series and store it */
            f[i] = f[i - 1] + f[i - 2];
        }
     
        return f[n];
    }
     
    // Return number of ways to write 'n'
    // as sum of odd integers
    static int countOddWays(int n)
    {
        return fib(n);
    }
     
    // Driver code
    public static void Main()
    {
        int n = 4;
        Console.WriteLine(countOddWays(n));
     
        n = 5;
        Console.WriteLine(countOddWays(n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to count ways to write
// number as sum of odd integers
 
// Function to calculate n'th
// Fibonacci number
function fib($n)
{
     
    // Declare an array to
    // store Fibonacci numbers.
    $f = array();
    $i;
     
    // 0th and 1st number of the
    // series are 0 and 1
    $f[0] = 0;
    $f[1] = 1;
     
    for($i = 2; $i <= $n; $i++)
    {
         
        // Add the previous 2
        // numbers in the series
        // and store it
        $f[$i] = $f[$i - 1] +
                 $f[$i - 2];
    }
     
    return $f[$n];
}
 
// Return number of ways to write 'n'
// as sum of odd integers
function countOddWays( $n)
{
    return fib($n);
}
 
    // Driver Code
    $n = 4;
    echo countOddWays($n) , "\n";
    $n = 5;
    echo countOddWays($n);
     
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program to count ways to write
// number as sum of odd integers
 
// Function to calculate n'th Fibonacci number
function fib(n) {
       
    /* Declare an array to store Fibonacci numbers. */
    let f = [];
    let i;
   
    /* 0th and 1st number of the series are 0 and 1*/
    f[0] = 0;
    f[1] = 1;
   
    for (i = 2; i <= n; i++) {
           
    /* Add the previous 2 numbers in the series
        and store it */
    f[i] = f[i - 1] + f[i - 2];
    }
   
    return f[n];
}
   
// Return number of ways to write 'n'
// as sum of odd integers
function countOddWays(n)
{
    return fib(n);
}
     
// Driver code
        let n = 4;
    document.write(countOddWays(n) + "<br/>");
   
    n = 5;
    document.write(countOddWays(n));
     
    // This code is contributed by code_hunt.
</script>

Producción:

3
5

Nota: La complejidad temporal de la implementación anterior es O(n). Se puede optimizar aún más hasta el tiempo O (Logn) utilizando la optimización de la función de Fibonacci mediante Matrix Exponential .
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.