Encuentra el término n de una relación de recurrencia dada

Sea a _n una secuencia de números, que está definida por la relación de recurrencia a ₁ =1 y a _n+1 /a _n =2 ⁿ . La tarea es encontrar el valor de log ₂ (a _n ) para un n dado .
Ejemplos:

Input: 5
Output: 10
Explanation: 
log₂(a_n) = (n * (n - 1)) / 2
= (5*(5-1))/2
= 10

Input: 100
Output: 4950

$\frac{a_{n+1}}{a_{n}}=2^{n}$
$\frac{a_{n}}{a_{n-1}}=2^{n-1}$
$.$
$.$
$.$
$\frac{a_{2}}{a_{1}}=2^{1}$ , We multiply all of the above in order to reach
$\frac{a_{n+1}}{a_{n}}\;.\;\frac{a_{n}}{a_{n-1}}=2^{n-1}\;.\;.\;.\;\frac{a_{2}}{a_{1}}=2^{n+(n-1)+...+1}$
$\frac{a_{n+1}}{a_{n}}=2^{\frac{n(n+1)}{2}}$
Since $1+2+3+...+(n-1)+n=\frac{n(n+1)}{2}$ . Then
$a_{n+1}=2^{\frac{n(n+1)}{2}}\;.a_{1}=2^{\frac{n(n+1)}{2}}$ .
Substituting n+1 for n: $a_{n}=2^{\frac{n(n-1)}{2}}$
So, $log_{2}(a_{n})=\frac{n(n-1)}{2}$
Below is the implementation of above approach.

C++

// C++ program to find nth term of
// a given recurrence relation
 
#include <bits/stdc++.h>
using namespace std;
 
// function to return required value
int sum(int n)
{
 
    // Get the answer
    int ans = (n * (n - 1)) / 2;
 
    // Return the answer
    return ans;
}
 
// Driver program
int main()
{
 
    // Get the value of n
    int n = 5;
 
    // function call to print result
    cout << sum(n);
 
    return 0;
}

Java

// Java program to find nth term
// of a given recurrence relation
import java.util.*;
 
class solution
{
static int sum(int n)
{
    // Get the answer
    int ans = (n * (n - 1)) / 2;
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void main(String arr[])
{
 
    // Get the value of n
    int n = 5;
 
    // function call to print result
    System.out.println(sum(n));
}
}
//This code is contributed byte
//Surendra_Gangwar

Python3

# Python3 program to find nth
# term of a given recurrence
# relation
 
# function to return
# required value
def sum(n):
 
    # Get the answer
    ans = (n * (n - 1)) / 2;
     
    # Return the answer
    return ans
 
# Driver Code
 
# Get the value of n
n = 5
 
# function call to prresult
print(int(sum(n)))
 
# This code is contributed by Raj

C#

// C# program to find nth term
// of a given recurrence relation
using System;
 
class GFG
{
static int sum(int n)
{
    // Get the answer
    int ans = (n * (n - 1)) / 2;
 
    // Return the answer
    return ans;
}
 
// Driver code
public static void Main()
{
 
    // Get the value of n
    int n = 5;
 
    // function call to print result
    Console.WriteLine(sum(n));
}
}
 
// This code is contributed byte
// inder_verma

PHP

<?php
// PHP program to find nth term of
// a given recurrence relation
 
// function to return required value
function sum($n)
{
 
    // Get the answer
    $ans = ($n * ($n - 1)) / 2;
 
    // Return the answer
    return $ans;
}
 
// Driver Code
 
// Get the value of n
$n = 5;
 
// function call to print result
echo sum($n);
 
// This code is contributed by
// inder_verma
?>

Javascript

<script>
// Javascript program to find nth term of
// a given recurrence relation
 
// function to return required value
function sum(n)
{
 
    // Get the answer
    let ans = parseInt((n * (n - 1)) / 2);
 
    // Return the answer
    return ans;
}
 
// Driver program
 
// Get the value of n
let n = 5;
 
// function call to print result
document.write(sum(n));
 
// This code is contributed by subham348.
</script>

Producción:

Complejidad de tiempo: O(1)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta