Dado un número ‘n’, escribe una función que imprima los dos últimos dígitos del n-ésimo (‘n’ también puede ser un número grande) número de Fibonacci.
Ejemplos:
Input : n = 65 Output : 65 Input : n = 365 Output : 65
Recomendado: Resuelva primero en » PRÁCTICA «, antes de pasar a la solución.
Una solución simple es encontrar el n-ésimo número de Fibonacci e imprimir sus dos últimos dígitos. Pero N puede ser muy grande, por lo que no funcionaría.
Una mejor solución es utilizar el hecho de que después del número 300 de Fibonacci, los últimos dos dígitos comienzan a repetirse.
1) Encuentra m = n % 300.
2) Devuelve el m-ésimo número de Fibonacci.
C++
// Program to find last two digits of n-th
// Fibonacci number
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Fills f[] with first 300 fibonacci numbers
void precomput(ll f[])
{
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
/* Add the previous 2 numbers in the series
and store last two digits of result */
for (ll i = 2; i < 300; i++)
f[i] = (f[i-1] + f[i-2])%100;
}
// Returns last two digits of n'th Fibonacci
// Number
int findLastDigit(ll f[], int n)
{
return f[n%300];
}
/* Driver program to test above function */
int main ()
{
// Precomputing units digit of first 300
// Fibonacci numbers
ll f[300] = {0};
precomput(f);
ll n = 1;
cout << findLastDigit(f, n) << endl;
n = 61;
cout << findLastDigit(f, n) << endl;
n = 7;
cout << findLastDigit(f, n) << endl;
n = 67;
cout << findLastDigit(f, n) << endl;
return 0;
}
Java
// Program to find last two digits of
// n-th Fibonacci number
import java.util.Arrays;
class GFG {
// Fills f[] with first 300
// fibonacci numbers
static void precomput(long f[])
{
/* 0th and 1st number of the
series are 0 and 1*/
f[0] = 0;
f[1] = 1;
/* Add the previous 2 numbers in
the series and store last two
digits of result */
for (int i = 2; i < 300; i++)
f[i] = (f[i-1] + f[i-2]) % 100;
}
// Returns last two digits of n'th
// Fibonacci Number
static long findLastDigit(long f[], int n)
{
return (f[(n%300)]);
}
/* Driver program to test above function */
public static void main (String args[])
{
// Precomputing units digit of
// first 300 Fibonacci numbers
long f[] = new long[300];
Arrays.fill(f,0);
precomput(f);
int n = 1;
System.out.println(findLastDigit(f, n));
n = 61;
System.out.println(findLastDigit(f, n));
n = 7;
System.out.println(findLastDigit(f, n));
n = 67;
System.out.println(findLastDigit(f, n));
}
}
/*This code is contributed by Nikita Tiwari.*/
Python3
# Python code to find last two # digits of n-th Fibonacci number def precomput(f): # 0th and 1st number of the series # are 0 and 1 f.append(0) f.append(1) # Add the previous 2 numbers in the series # and store last two digits of result for i in range(2,300): f.append((f[i-1] + f[i-2]) % 100) # Returns last two digits of # n'th Fibonacci Number def findLastDigit(f,n): return f[n%300] # driver code f = list() precomput(f) n = 1 print(findLastDigit(f, n)) n = 61 print(findLastDigit(f, n)) n = 7 print(findLastDigit(f, n)) n = 67 print(findLastDigit(f, n)) # This code is contributed by "Abhishek Sharma 44"
C#
// Program to find last two digits of
// n-th Fibonacci number
using System;
class GFG {
// Fills f[] with first 300
// fibonacci numbers
static void precomput(long []f)
{
/* 0th and 1st number of the
series are 0 and 1*/
f[0] = 0;
f[1] = 1;
/* Add the previous 2 numbers in
the series and store last two
digits of result */
for (int i = 2; i < 300; i++)
f[i] = (f[i-1] + f[i-2]) % 100;
}
// Returns last two digits of n'th
// Fibonacci Number
static long findLastDigit(long []f, int n)
{
return (f[(n % 300)]);
}
/* Driver program to test above function */
public static void Main ()
{
// Precomputing units digit of
// first 300 Fibonacci numbers
long []f = new long[300];
precomput(f);
int n = 1;
Console.WriteLine(findLastDigit(f, n));
n = 61;
Console.WriteLine(findLastDigit(f, n));
n = 7;
Console.WriteLine(findLastDigit(f, n));
n = 67;
Console.WriteLine(findLastDigit(f, n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// Program to find last two
// digits of n-th Fibonacci
// number
// Fills f[] with first
// 300 fibonacci numbers
function precomput()
{
/* 0th and 1st number of
the series are 0 and 1*/
$f[0] = 0;
$f[1] = 1;
/* Add the previous 2 numbers
in the series and store last
two digits of result */
for ($i = 2; $i < 300; $i++)
$f[$i] = ($f[$i - 1] +
$f[$i - 2]) % 100;
return $f;
}
// Returns last two digits
// of n'th Fibonacci Number
function findLastDigit($f, $n)
{
return $f[$n % 300];
}
// Driver code
// Precomputing units digit
// of first 300 Fibonacci numbers
$f = precomput();
$n = 1;
echo findLastDigit($f, $n) . "\n";
$n = 61;
echo findLastDigit($f, $n) . "\n";
$n = 7;
echo findLastDigit($f, $n) . "\n";
$n = 67;
echo findLastDigit($f, $n) . "\n";
// This code is contributed by mits.
?>
Javascript
<script>
// Program to find last two digits of n-th
// Fibonacci number
// Fills f[] with first 300 fibonacci numbers
function precomput(f)
{
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
/* Add the previous 2 numbers in the series
and store last two digits of result */
for (let i = 2; i < 300; i++)
f[i] = (f[i-1] + f[i-2])%100;
}
// Returns last two digits of n'th Fibonacci
// Number
function findLastDigit(f, n)
{
return f[n%300];
}
/* Driver program to test above function */
// Precomputing units digit of first 300
// Fibonacci numbers
let f = new Uint8Array(300);
precomput(f);
let n = 1;
document.write(findLastDigit(f, n) + "<br>");
n = 61;
document.write(findLastDigit(f, n) + "<br>");
n = 7;
document.write(findLastDigit(f, n) + "<br>");
n = 67;
document.write(findLastDigit(f, n) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Producción:
1 61 13 53
Complejidad de tiempo: O (300), se ejecutará en tiempo constante.
Espacio auxiliar: O(300), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por Sahil_Chhabra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA