Programa para hallar el MCM de dos Números de Fibonacci

Posted on by Rudeus Greyrat

Aquí se dan dos números positivos a y b . La tarea es imprimir el mínimo común múltiplo de a’ésimo y b’ésimo Números de Fibonacci.
Los primeros números de Fibonacci son 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……
Tenga en cuenta que 0 se considera como el 0’th Número de Fibonacci.
Ejemplos: 
 

Input : a = 3, b = 12
Output : 144

Input : a = 8, b = 37
Output : 507314157

Enfoque : La solución simple del problema es, 
 

  1. Encuentre el número de fibonacci a’th .
  2. Encuentre el segundo número de fibonacci.
  3. Encuentre su GCD y, con la ayuda del GCD, encuentre su MCM. La relación es LCM(a, b) = (axb) / GCD(a, b) (Consulte aquí) .

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

C++

// C++ Program to find LCM of Fib(a)
// and Fib(b)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
 
// Create an array for memorization
int f[MAX] = { 0 };
 
// Function to return the n'th Fibonacci
// number using table f[].
int fib(int n)
{
    // Base cases
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
 
    // If fib(n) is already computed
    if (f[n])
        return f[n];
 
    int k = (n & 1) ? (n + 1) / 2 : n / 2;
 
    // Applying recursive formula
    // Note value n&1 is 1
    // if n is odd, else 0.
    f[n] = (n & 1) ? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1))
                   : (2 * fib(k - 1) + fib(k)) * fib(k);
 
    return f[n];
}
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return the LCM of
// Fib(a) and Fib(a)
int findLCMFibonacci(int a, int b)
{
    return (fib(a) * fib(b)) / fib(gcd(a, b));
}
 
// Driver code
int main()
{
    int a = 3, b = 12;
 
    cout << findLCMFibonacci(a, b);
 
    return 0;
}

Java

// Java program to find LCM of Fib(a)
// and Fib(b)
import java.util.*;
 
class GFG
{
 
static int MAX = 1000;
 
// Create an array for memoization
static int[] f = new int[MAX];
 
// Function to return the n'th Fibonacci
// number using table f[].
static int fib(int n)
{
    // Base cases
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
 
    // If fib(n) is already computed
    if (f[n] != 0)
        return f[n];
    int k = 0;
    if ((n & 1) != 0)
        k = (n + 1) / 2;
    else
        k = n / 2;
 
    // Applying recursive formula
    // Note value n&1 is 1
    // if n is odd, else 0.
    if((n & 1 ) != 0)
        f[n] = (fib(k) * fib(k) +
                fib(k - 1) * fib(k - 1));
    else
        f[n] = (2 * fib(k - 1) +
                    fib(k)) * fib(k);
 
    return f[n];
}
 
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return the LCM of
// Fib(a) and Fib(a)
static int findLCMFibonacci(int a, int b)
{
    return (fib(a) * fib(b)) / fib(gcd(a, b));
}
 
// Driver code
public static void main(String args[])
{
    int a = 3, b = 12;
 
    System.out.println(findLCMFibonacci(a, b));
}
}
 
// This code is contributed by
// Surendra_Gangwar

Python3

# Python 3 Program to find LCM of
# Fib(a) and Fib(b)
MAX = 1000
 
# Create an array for memoization
f = [0] * MAX
 
# Function to return the n'th
# Fibonacci number using table f[].
def fib(n):
 
    # Base cases
    if (n == 0):
        return 0
    if (n == 1 or n == 2):
        f[n] = 1
        return f[n]
 
    # If fib(n) is already computed
    if (f[n]):
        return f[n]
 
    k = (n + 1) // 2 if (n & 1) else n // 2
 
    # Applying recursive formula
    # Note value n&1 is 1
    # if n is odd, else 0.
    if (n & 1):
        f[n] = (fib(k) * fib(k) +
                fib(k - 1) * fib(k - 1))
    else:
        f[n] = (2 * fib(k - 1) + fib(k)) * fib(k)
 
    return f[n]
 
# Function to return gcd of a and b
def gcd(a, b):
    if (a == 0):
        return b
 
    return gcd(b % a, a)
 
# Function to return the LCM of
# Fib(a) and Fib(a)
def findLCMFibonacci(a, b):
 
    return (fib(a) * fib(b)) // fib(gcd(a, b))
 
# Driver code
if __name__ == "__main__":
    a = 3
    b = 12
 
    print (findLCMFibonacci(a, b))
 
# This code is contributed by ita_c

C#

// C# program to find LCM of Fib(a)
// and Fib(b)
using System;
 
class GFG
{
 
static int MAX = 1000;
 
// Create an array for memoization
static int[] f = new int[MAX];
 
// Function to return the n'th Fibonacci
// number using table f[].
static int fib(int n)
{
    // Base cases
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
 
    // If fib(n) is already computed
    if (f[n] != 0)
        return f[n];
    int k = 0;
    if ((n & 1) != 0)
        k = (n + 1) / 2;
    else
        k = n / 2;
 
    // Applying recursive formula
    // Note value n&1 is 1
    // if n is odd, else 0.
    if((n & 1 ) != 0)
        f[n] = (fib(k) * fib(k) +
                fib(k - 1) * fib(k - 1));
    else
        f[n] = (2 * fib(k - 1) +
                    fib(k)) * fib(k);
 
    return f[n];
}
 
// Function to return gcd of a and b
static int gcd(int a, int b)
{
    if (a == 0)
        return b;
 
    return gcd(b % a, a);
}
 
// Function to return the LCM of
// Fib(a) and Fib(a)
static int findLCMFibonacci(int a, int b)
{
    return (fib(a) * fib(b)) / fib(gcd(a, b));
}
 
// Driver code
static void Main()
{
    int a = 3, b = 12;
 
    Console.WriteLine(findLCMFibonacci(a, b));
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP Program to find LCM of Fib(a)
// and Fib(b)
 
$GLOBALS['MAX'] = 1000;
 
// Create an array for memoization
$GLOBALS['f'] = array();
 
for($i = 0; $i < $GLOBALS['MAX']; $i++)
    $GLOBALS['f'][$i] = 0;
 
// Function to return the n'th Fibonacci
// number using table f[].
function fib($n)
{
    // Base cases
    if ($n == 0)
        return 0;
    if ($n == 1 || $n == 2)
        return ($GLOBALS['f'][$n] = 1);
 
    // If fib(n) is already computed
    if ($GLOBALS['f'][$n])
        return $GLOBALS['f'][$n];
 
    $k = ($n & 1) ? ($n + 1) / 2 : $n / 2;
 
    // Applying recursive formula
    // Note value n&1 is 1
    // if n is odd, else 0.
    $GLOBALS['f'][$n] = ($n & 1) ?
                        (fib($k) * fib($k) +
                         fib($k - 1) * fib($k - 1)) :
                        (2 * fib($k - 1) + fib($k)) * fib($k);
 
    return $GLOBALS['f'][$n];
}
 
// Function to return gcd of a and b
function gcd($a, $b)
{
    if ($a == 0)
        return $b;
 
    return gcd($b % $a, $a);
}
 
// Function to return the LCM of
// Fib(a) and Fib(a)
function findLCMFibonacci($a, $b)
{
    return (fib($a) * fib($b)) /
            fib(gcd($a, $b));
}
 
// Driver code
$a = 3;
$b = 12;
 
echo findLCMFibonacci($a, $b);
 
// This code is contributed by Ryuga
?>

Javascript

<script>
// Javascript program to find LCM of Fib(a)
// and Fib(b)
 
let MAX = 1000;
 
// Create an array for memoization
let f = new Array(MAX);
for(let i=0;i<MAX;i++)
{
    f[i]=0;
}
 
// Function to return the n'th Fibonacci
// number using table f[].
function fib(n)
{
    // Base cases
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
   
    // If fib(n) is already computed
    if (f[n] != 0)
        return f[n];
    let k = 0;
    if ((n & 1) != 0)
        k = (n + 1) / 2;
    else
        k = n / 2;
   
    // Applying recursive formula
    // Note value n&1 is 1
    // if n is odd, else 0.
    if((n & 1 ) != 0)
        f[n] = (fib(k) * fib(k) +
                fib(k - 1) * fib(k - 1));
    else
        f[n] = (2 * fib(k - 1) +
                    fib(k)) * fib(k);
   
    return f[n];
}
 
// Function to return gcd of a and b
function gcd(a,b)
{
    if (a == 0)
        return b;
   
    return gcd(b % a, a);
}
 
// Function to return the LCM of
// Fib(a) and Fib(a)
function findLCMFibonacci(a,b)
{
    return (fib(a) * fib(b)) / fib(gcd(a, b));
}
 
// Driver code
let a = 3, b = 12;
document.write(findLCMFibonacci(a, b));
 
 
// This code is contributed by rag2127
</script>
Producción: 

144

 

Complejidad del tiempo: O(2 n )

Espacio Auxiliar: O(MAX)

Publicación traducida automáticamente

Artículo escrito por IshwarGupta 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 *