Dados dos enteros n y k. Encuentre la posición del enésimo múltiplo de K en la serie de Fibonacci.
Ejemplos:
Input : k = 2, n = 3 Output : 9 3'rd multiple of 2 in Fibonacci Series is 34 which appears at position 9. Input : k = 4, n = 5 Output : 30 4'th multiple of 5 in Fibonacci Series is 832040 which appears at position 30.
Serie Fibonacci (F): 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040… (despreciando el primer 0).
Una solución simple es atravesar números de Fibonacci comenzando desde el primer número. Mientras atraviesa, mantenga un registro de los conteos de múltiplos de k. Cada vez que el recuento se convierte en n, devuelve la posición.
Una solución eficiente se basa en la siguiente propiedad interesante.
La serie de Fibonacci siempre es periódica bajo representación modular. A continuación se muestran ejemplos.
F (mod 2) = 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,
1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
Here 0 is repeating at every 3rd index and
the cycle repeats at every 3rd index.
F (mod 3) = 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0
,1,1,2,0,2,2,1,0,1,1,2,0,2,2
Here 0 is repeating at every 4th index and
the cycle repeats at every 8th index.
F (mod 4) = 1,1,2,3,1,0,1,1,2,3,1,0,1,1,2,3,
1,0,1,1,2,3,1,0,1,1,2,3,1,0
Here 0 is repeating at every 6th index and
the cycle repeats at every 6th index.
F (mod 5) = 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,
2,2,4,1,0,1,1,2,3,0,3,3,1,4,0
Here 0 is repeating at every 5th index and
the cycle repeats at every 20th index.
F (mod 6) = 1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,
3,1,4,5,3,2,5,1,0,1,1,2,3,5,2
Here 0 is repeating at every 12th index and
the cycle repeats at every 24th index.
F (mod 7) = 1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,
0,1,1,2,3,5,1,6,0,6,6,5,4,2,6
Here 0 is repeating at every 8th index and
the cycle repeats at every 16th index.
F (mod 8) = 1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,
3,5,0,5,5,2,7,1,0,1,1,2,3,5,0
Here 0 is repeating at every 6th index and
the cycle repeats at every 12th index.
F (mod 9) = 1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,
6,4,1,5,6,2,8,1,0,1,1,2,3,5,8
Here 0 is repeating at every 12th index and
the cycle repeats at every 24th index.
F (mod 10) = 1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,
7,7,4,1,5,6,1,7,8,5,3,8,1,9,0.
Here 0 is repeating at every 15th index and
the cycle repeats at every 60th index.
¿Por qué la serie de Fibonacci es periódica en Modulo?
Bajo la representación modular, sabemos que cada número de Fibonacci se representará como un residuo 0 ? F (mod m) < m. Por lo tanto, solo hay m valores posibles para cualquier F dada (mod m) y, por lo tanto, m*m = m^2 posibles pares de términos consecutivos dentro de la secuencia. Dado que m ^ 2 es finito, sabemos que algún par de términos eventualmente debe repetirse. Además, como cualquier par de términos en la secuencia de Fibonacci determina el resto de la secuencia, vemos que la serie de Fibonacci módulo m debe repetirse en algún punto y, por lo tanto, debe ser periódica.
Fuente: https://www.whitman.edu/Documents/Academics/Mathematics/clancy.pdf
Con base en el hecho anterior, podemos encontrar rápidamente la posición del enésimo múltiplo de K simplemente encontrando el primer múltiplo. Si la posición del primer múltiplo es i, devolvemos la posición como n*i.
A continuación se muestra la implementación:
C++
// C++ program to find position
// of n'th multiple of a number
// k in Fibonacci Series
# include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Returns position of n'th multiple
// of k in Fibonacci Series
int findPosition(int k, int n)
{
// Iterate through all
// fibonacci numbers
unsigned long long int f1 = 0,
f2 = 1,
f3;
for (int i = 2; i <= MAX; i++)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
// Found first multiple of
// k at position i
if (f2 % k == 0)
// n'th multiple would be at
// position n*i using Periodic
// property of Fibonacci numbers
// under modulo.
return n * i;
}
}
// Driver Code
int main ()
{
int n = 5, k = 4;
cout << "Position of n'th multiple of k"
<<" in Fibonacci Series is "
<< findPosition(k, n) << endl;
return 0;
}
Java
// Java Program to find position
// of n'th multiple of a number
// k in Fibonacci Series
class GFG
{
public static int findPosition(int k,
int n)
{
long f1 = 0, f2 = 1, f3;
int i = 2;
while(i != 0)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
if(f2 % k == 0)
{
return n * i;
}
i++;
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
// Multiple no.
int n = 5;
// Number of whose multiple
// we are finding
int k = 4;
System.out.print("Position of n'th multiple" +
" of k in Fibonacci Series is ");
System.out.println(findPosition(k, n));
}
}
// This code is contributed
// by Mohit Gupta_OMG
Python3
# Python Program to find position
# of n'th multiple of a number k
# in Fibonacci Series
def findPosition(k, n):
f1 = 0
f2 = 1
i = 2;
while i != 0:
f3 = f1 + f2;
f1 = f2;
f2 = f3;
if f2 % k == 0:
return n * i
i += 1
return
# Multiple no.
n = 5;
# Number of whose multiple
# we are finding
k = 4;
print("Position of n'th multiple of k in"
"Fibonacci Series is", findPosition(k, n));
# This code is contributed
# by Mohit Gupta_OMG
C#
// C# Program to find position of
// n'th multiple of a number k in
// Fibonacci Series
using System;
class GFG
{
static int findPosition(int k, int n)
{
long f1 = 0, f2 = 1, f3;
int i = 2;
while(i!=0)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
if(f2 % k == 0)
{
return n * i;
}
i++;
}
return 0;
}
// Driver code
public static void Main()
{
// Multiple no.
int n = 5;
// Number of whose multiple
// we are finding
int k = 4;
Console.Write("Position of n'th multiple " +
"of k in Fibonacci Series is ");
// Function calling
Console.WriteLine(findPosition(k, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to find position
// of n'th multiple of a number
// k in Fibonacci Series
$MAX = 1000;
// Returns position of n'th multiple
// of k in Fibonacci Series
function findPosition($k, $n)
{
global $MAX;
// Iterate through all
// fibonacci numbers
$f1 = 0; $f2 = 1; $f3;
for ($i = 2; $i <= $MAX; $i++)
{
$f3 = $f1 + $f2;
$f1 = $f2;
$f2 = $f3;
// Found first multiple of
// k at position i
if ($f2 % $k == 0)
// n'th multiple would be at
// position n*i using Periodic
// property of Fibonacci numbers
// under modulo
return $n * $i;
}
}
// Driver Code
$n = 5; $k = 4;
echo("Position of n'th multiple of k" .
" in Fibonacci Series is " .
findPosition($k, $n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find position
// of n'th multiple of a number
// k in Fibonacci Series
let MAX = 1000;
// Returns position of n'th multiple
// of k in Fibonacci Series
function findPosition(k, n)
{
// Iterate through all
// fibonacci numbers
let f1 = 0;
let f2 = 1;
let f3;
for (let i = 2; i <= MAX; i++)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
// Found first multiple of
// k at position i
if (f2 % k == 0)
// n'th multiple would be at
// position n*i using Periodic
// property of Fibonacci numbers
// under modulo
return n * i;
}
}
// Driver Code
let n = 5;
let k = 4;
document.write("Position of n'th multiple of k" +
" in Fibonacci Series is " +
findPosition(k, n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción :
Position of n'th multiple of k in Fibonacci Series is 30
Complejidad de tiempo: O (1000), el código se ejecutará en un tiempo constante.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Este artículo es una contribución de Kishlay Verma . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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