Программа для поиска последней цифры n-го числа Фибоначчи
Опубликовано: 20 Января, 2022
Учитывая число n, напишите функцию, которая печатает последнюю цифру n-го (n также может быть большим числом) числа Фибоначчи.
Примеры :
Ввод: n = 0 Выход: 0 Ввод: n = 2 Выход: 1 Ввод: n = 7 Выход: 3
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.
Method 1 : (Naive Method)
Simple approach is to calculate the n’th Fibonacci number and printing the last digit.
C++
// C++ Program to find last digit // of nth Fibonacci number #include <bits/stdc++.h> using namespace std; typedef long long int ll; void multiply(ll F[2][2], ll M[2][2]); void power(ll F[2][2], ll n); // Function that returns // nth Fibonacci number ll fib( int n) { ll F[2][2] = {{1, 1}, {1, 0}}; if (n == 0) return 0; power(F, n - 1); return F[0][0]; } // Utility method to find // n"th power of F[][] void power(ll F[2][2], ll n) { // Base cases if (n == 0 || n == 1) return ; ll M[2][2] = {{1, 1}, {1, 0}}; power(F, n / 2); multiply(F, F); if (n % 2 != 0) multiply(F, M); } // Utility function to multiply two // matrices and store result in first. void multiply(ll F[2][2], ll M[2][2]) { ll x = F[0][0] * M[0][0] + F[0][1] * M[1][0]; ll y = F[0][0] * M[0][1] + F[0][1] * M[1][1]; ll z = F[1][0] * M[0][0] + F[1][1] * M[1][0]; ll w = F[1][0] * M[0][1] + F[1][1] * M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } // Returns last digit of // n"th Fibonacci Number int findLastDigit( int n) { return fib(n) % 10; } // Driver code int main() { ll n = 1; cout << findLastDigit(n) << endl; n = 61; cout << findLastDigit(n) << endl; n = 7; cout << findLastDigit(n) << endl; n = 67; cout << findLastDigit(n) << endl; return 0; } |
Java
// Java program to find last digit // of nth Fibonacci number class GFG { // Function that returns // nth Fibonacci number static long fib( long n) { long F[][] = new long [][] {{ 1 , 1 }, { 1 , 0 }}; if (n == 0 ) return 0 ; power(F, n - 1 ); return F[ 0 ][ 0 ]; } // Utility function to multiply two // matrices and store result in first. static void multiply( long F[][], long M[][]) { long x = F[ 0 ][ 0 ] * M[ 0 ][ 0 ] + F[ 0 ][ 1 ] * M[ 1 ][ 0 ]; long y = F[ 0 ][ 0 ] * M[ 0 ][ 1 ] + F[ 0 ][ 1 ] * M[ 1 ][ 1 ]; long z = F[ 1 ][ 0 ] * M[ 0 ][ 0 ] + F[ 1 ][ 1 ] * M[ 1 ][ 0 ]; long w = F[ 1 ][ 0 ] * M[ 0 ][ 1 ] + F[ 1 ][ 1 ] * M[ 1 ][ 1 ]; F[ 0 ][ 0 ] = x; F[ 0 ][ 1 ] = y; F[ 1 ][ 0 ] = z; F[ 1 ][ 1 ] = w; } // Optimized version of power() in method 4 static void power( long F[][], long n) { if ( n == 0 || n == 1 ) return ; long M[][] = new long [][] {{ 1 , 1 }, { 1 , 0 }}; power(F, n / 2 ); multiply(F, F); if (n % 2 != 0 ) multiply(F, M); } // Returns last digit of // n"th Fibonacci Number long findLastDigit( long n) { return (fib(n) % 10 ); } // Driver code public static void main(String[] args) { int n; GFG ob = new GFG(); n = 1 ; System.out.println(ob.findLastDigit(n)); n = 61 ; System.out.println(ob.findLastDigit(n)); n = 7 ; System.out.println(ob.findLastDigit(n)); n = 67 ; System.out.println(ob.findLastDigit(n)); } } |
Python3
# Python3 program to find last digit of # nth Fibonacci number # Function that returns nth Fibonacci number def fib(n): F = [[ 1 , 1 ], [ 1 , 0 ]]; if (n = = 0 ): return 0 ; power(F, n - 1 ); return F[ 0 ][ 0 ]; # Utility function to multiply two # matrices and store result in first. def multiply(F, M): x = F[ 0 ][ 0 ] * M[ 0 ][ 0 ] + F[ 0 ][ 1 ] * M[ 1 ][ 0 ]; y = F[ 0 ][ 0 ] * M[ 0 ][ 1 ] + F[ 0 ][ 1 ] * M[ 1 ][ 1 ]; z = F[ 1 ][ 0 ] * M[ 0 ][ 0 ] + F[ 1 ][ 1 ] * M[ 1 ][ 0 ]; w = F[ 1 ][ 0 ] * M[ 0 ][ 1 ] + F[ 1 ][ 1 ] * M[ 1 ][ 1 ]; F[ 0 ][ 0 ] = x; F[ 0 ][ 1 ] = y; F[ 1 ][ 0 ] = z; F[ 1 ][ 1 ] = w; # Optimized version of power() in # method 4 def power(F, n): if ( n = = 0 or n = = 1 ): return ; M = [[ 1 , 1 ], [ 1 , 0 ]]; power(F, int (n / 2 )); multiply(F, F); if (n % 2 ! = 0 ): multiply(F, M); # Returns last digit of # n"th Fibonacci Number def findLastDigit(n): return (fib(n) % 10 ); # Driver code n = 1 ; print (findLastDigit(n)); n = 61 ; print (findLastDigit(n)); n = 7 ; print (findLastDigit(n)); n = 67 ; print (findLastDigit(n)); # This code is contributed # by chandan_jnu |
C#
// C# program to find last digit // of nth Fibonacci number using System; class GFG { // function that returns // nth Fibonacci number static long fib( long n) { long [,]F = new long [,] {{1, 1}, {1, 0}}; if (n == 0) return 0; power(F, n - 1); return F[0, 0]; } // Utility function to multiply two // matrices and store result in first. static void multiply( long [,]F, long [,]M) { long x = F[0, 0] * M[0, 0] + F[0, 1] * M[1, 0]; long y = F[0, 0] * M[0, 1] + F[0, 1] * M[1, 1]; long z = F[1, 0] * M[0, 0] + F[1, 1] * M[1, 0]; long w = F[1, 0] * M[0, 1] + F[1, 1] * M[1, 1]; F[0, 0] = x; F[0, 1] = y; F[1, 0] = z; F[1, 1] = w; } // Optimized version of power() in method 4 static void power( long [,]F, long n) { if ( n == 0 || n == 1) return ; long [,]M = new long [,] {{1, 1}, {1, 0}}; power(F, n / 2); multiply(F, F); if (n % 2 != 0) multiply(F, M); } // Returns last digit of // n"th Fibonacci Number static long findLastDigit( long n) { return (fib(n) % 10); } // Driver code public static void Main() { int n; n = 1; Console.WriteLine(findLastDigit(n)); n = 61; Console.WriteLine(findLastDigit(n)); n = 7; Console.WriteLine(findLastDigit(n)); n = 67; Console.WriteLine(findLastDigit(n)); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to find last digit of nth // Fibonacci number // Function that returns nth Fibonacci number function fib( $n ) { $F = array ( array (1, 1), array (1, 0)); if ( $n == 0) return 0; power( $F , $n - 1); return $F [0][0]; } // Utility function to multiply two // matrices and store result in first. function multiply(& $F , & $M ) { $x = $F [0][0] * $M [0][0] + $F [0][1] * $M [1][0]; $y = $F [0][0] * $M [0][1] + $F [0][1] * $M [1][1]; $z = $F [1][0] * $M [0][0] + $F [1][1] * $M [1][0]; $w = $F [1][0] * $M [0][1] + $F [1][1] * $M [1][1]; $F [0][0] = $x ; $F [0][1] = $y ; $F [1][0] = $z ; $F [1][1] = $w ; } // Optimized version of power() in method 4 function power(& $F , $n ) { if ( $n == 0 || $n == 1) return ; $M = array ( array (1, 1), array (1, 0)); power( $F , (int)( $n / 2)); multiply( $F , $F ); if ( $n % 2 != 0) multiply( $F , $M ); } // Returns last digit of // n"th Fibonacci Number function findLastDigit( $n ) { return (fib( $n ) % 10); } // Driver code $n = 1; echo findLastDigit( $n ) . "
" ; $n = 61; echo findLastDigit( $n ) . "
" ; $n = 7; echo findLastDigit( $n ) . "
" ; $n = 67; echo findLastDigit( $n ) . "
" ; // This code is contributed // by Akanksha Rai |
Javascript
<script> // Javascript program to find last digit of nth Fibonacci number // Function that returns // nth Fibonacci number function fib(n) { let F = [[1, 1], [1, 0]]; if (n == 0) return 0; power(F, n - 1); return F[0][0]; } // Utility function to multiply two // matrices and store result in first. function multiply(F, M) { let x = F[0][0] * M[0][0] +
РЕКОМЕНДУЕМЫЕ СТАТЬИ |