Программа для поиска последней цифры 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] +
            

РЕКОМЕНДУЕМЫЕ СТАТЬИ