Se le dan dos números positivos M y N. La tarea es imprimir el máximo común divisor de M’th y N’th 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 : M = 3, N = 6 Output : 2 Fib(3) = 2, Fib(6) = 8 GCD of above two numbers is 2 Input : M = 8, N = 12 Output : 3 Fib(8) = 21, Fib(12) = 144 GCD of above two numbers is 3
Una solución simple es seguir los pasos a continuación.
1) Encuentra el M-ésimo número de Fibonacci.
2) Encuentre el N’th Número de Fibonacci.
3) Devolver MCD de dos números.
Una mejor solución se basa en la siguiente identidad
GCD(Fib(M), Fib(N)) = Fib(GCD(M, N)) The above property holds because Fibonacci Numbers follow Divisibility Sequence, i.e., if M divides N, then Fib(M) also divides N. For example, Fib(3) = 2 and every third third Fibonacci Number is even. Source : Wiki
Los pasos son:
1) Encuentra el MCD de M y N. Sea GCD g.
2) Devolver Fib(g).
A continuación se muestran implementaciones de la idea anterior.
C++
// C++ Program to find GCD of Fib(M) and Fib(N)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Create an array for memoization
int f[MAX] = { 0 };
// Returns n'th Fibonacci number using table f[].
// Refer method 6 of below post for details.
// https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
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 M, int N)
{
if (M == 0)
return N;
return gcd(N % M, M);
}
// Returns GCD of Fib(M) and Fib(N)
int findGCDofFibMFibN(int M, int N)
{
return fib(gcd(M, N));
}
// Driver code
int main()
{
int M = 3, N = 12;
cout << findGCDofFibMFibN(M, N);
return 0;
}
C
// C Program to find GCD of Fib(M) and Fib(N)
#include <stdio.h>
const int MAX = 1000;
// Returns n'th Fibonacci number using table arr[].
// Refer method 6 of below post for details.
// https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
int fib(int n)
{
// Create an array for memoization
int arr[MAX];
for (int i = 0; i < MAX; i++)
arr[i] = 0;
// Base cases
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (arr[n] = 1);
// If fib(n) is already computed
if (arr[n])
return arr[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.
arr[n]
= (n & 1)
? (fib(k) * fib(k) + fib(k - 1) * fib(k - 1))
: (2 * fib(k - 1) + fib(k)) * fib(k);
return arr[n];
}
// Function to return gcd of a and b
int gcd(int M, int N)
{
if (M == 0)
return N;
return gcd(N % M, M);
}
// Returns GCD of Fib(M) and Fib(N)
int findGCDofFibMFibN(int M, int N)
{
return fib(gcd(M, N));
}
// Driver code
int main()
{
int M = 3, N = 12;
printf("%d", findGCDofFibMFibN(M, N));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java Program to find GCD of Fib(M) and Fib(N)
class gcdOfFibonacci
{
static final int MAX = 1000;
static int[] f;
gcdOfFibonacci() // Constructor
{
// Create an array for memoization
f = new int[MAX];
}
// Returns n'th Fibonacci number using table f[].
// Refer method 6 of below post for details.
// https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
private 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 = ((n & 1)==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)==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
private static int gcd(int M, int N)
{
if (M == 0)
return N;
return gcd(N%M, M);
}
// This method returns GCD of Fib(M) and Fib(N)
static int findGCDofFibMFibN(int M, int N)
{
return fib(gcd(M, N));
}
// Driver method
public static void main(String[] args)
{
// Returns GCD of Fib(M) and Fib(N)
gcdOfFibonacci obj = new gcdOfFibonacci();
int M = 3, N = 12;
System.out.println(findGCDofFibMFibN(M, N));
}
}
// This code is contributed by Pankaj Kumar
Python3
# Python Program to find # GCD of Fib(M) and Fib(N) MAX = 1000 # Create an array for memoization f=[0 for i in range(MAX)] # Returns n'th Fibonacci # number using table f[]. # Refer method 6 of below # post for details. # https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ def fib(n): # Base cases if (n == 0): return 0 if (n == 1 or n == 2): f[n] = 1 # 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. f[n] = (fib(k)*fib(k) + fib(k-1)*fib(k-1)) if(n & 1) else ((2* fib(k-1) + fib(k))*fib(k)) return f[n] # Function to return # gcd of a and b def gcd(M, N): if (M == 0): return N return gcd(N % M, M) # Returns GCD of # Fib(M) and Fib(N) def findGCDofFibMFibN(M, N): return fib(gcd(M, N)) # Driver code M = 3 N = 12 print(findGCDofFibMFibN(M, N)) # This code is contributed # by Anant Agarwal.
C#
// C# Program to find GCD of
// Fib(M) and Fib(N)
using System;
class gcdOfFibonacci {
static int MAX = 1000;
static int []f;
// Constructor
gcdOfFibonacci()
{
// Create an array
// for memoization
f = new int[MAX];
}
// Returns n'th Fibonacci number
// using table f[]. Refer method
// 6 of below post for details.
// https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
private 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 = ((n & 1)==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) == 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
private static int gcd(int M, int N)
{
if (M == 0)
return N;
return gcd(N%M, M);
}
// This method returns GCD of
// Fib(M) and Fib(N)
static int findGCDofFibMFibN(int M, int N)
{
return fib(gcd(M, N));
}
// Driver method
public static void Main()
{
// Returns GCD of Fib(M) and Fib(N)
new gcdOfFibonacci();
int M = 3, N = 12;
Console.Write(findGCDofFibMFibN(M, N));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to find
// GCD of Fib(M) and Fib(N)
$MAX = 1000;
// Create an array for memoization
$f = array_fill(0, $MAX, 0);
// Returns n'th Fibonacci number
// using table f[]. Refer method
// 6 of below post for details.
function fib($n)
{
global $f;
// Base cases
if ($n == 0)
return 0;
if ($n == 1 or $n == 2)
$f[$n] = 1;
// If fib(n) is already computed
if ($f[$n])
return $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.
$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
function gcd($M, $N)
{
if ($M == 0)
return $N;
return gcd($N % $M, $M);
}
// Returns GCD of Fib(M) and Fib(N)
function findGCDofFibMFibN($M, $N)
{
return fib(gcd($M, $N));
}
// Driver code
$M = 3;
$N = 12;
print(findGCDofFibMFibN($M, $N))
// This code is contributed
// by mits
?>
Javascript
<script>
// JavaScript Program to find GCD of Fib(M) and Fib(N)
const MAX = 1000;
// Create an array for memoization
var f = [...Array(MAX)];
f.fill(0);
// Returns n'th Fibonacci number using table f[].
// Refer method 6 of below post for details.
// https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
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]) return f[n];
var 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
function gcd(M, N) {
if (M == 0) return N;
return gcd(N % M, M);
}
// Returns GCD of Fib(M) and Fib(N)
function findGCDofFibMFibN(M, N) {
return fib(gcd(M, N));
}
// Driver code
var M = 3,
N = 12;
document.write(findGCDofFibMFibN(M, N));
// This code is contributed by rdtank.
</script>
Producción:
2
Este artículo es una contribución de Shubham Agrawal . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA