Рубрики

GCD и числа Фибоначчи

Вы дали два положительных числа M и N. Задача состоит в том, чтобы напечатать наибольший общий делитель из M'th и n'th чисел Фибоначчи .

Первые несколько чисел Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,….
Обратите внимание, что 0 считается 0-м числом Фибоначчи.

Примеры:

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

Простое решение состоит в том, чтобы выполнить следующие шаги.
1) Найти M'th число Фибоначчи.
2) Найдите N-е число Фибоначчи.
3) Вернуть ГКД из двух чисел.

Лучшее решение основано на нижеследующей идентичности

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

Шаги:
1) Найти GCD из M и N. Пусть GCD — g.
2) Верните Fib (g).

Ниже приведены реализации вышеуказанной идеи.

C ++

// C ++ Программа для поиска GCD Fib (M) и Fib (N)
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000;

  
// Создать массив для запоминания

int f[MAX] = {0};

  
// Возвращает n-е число Фибоначчи, используя таблицу f [].
// Подробности см. В методе 6 ниже.
// https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/amp/

int fib(int n)

{

    // Базовые случаи

    if (n == 0)

        return 0;

    if (n == 1 || n == 2)

        return (f[n] = 1);

  

    // Если fib (n) уже вычислен

    if (f[n])

        return f[n];

  

    int k = (n & 1)? (n+1)/2 : n/2;

  

    // Применение рекурсивной формулы [Примечание: значение n & 1 равно 1

    // если n нечетно, иначе 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];

}

  
// Функция для возврата gcd из a и b

int gcd(int M, int N)

{

    if (M == 0)

        return N;

    return gcd(N%M, M);

}

  
// Возвращает GCD Fib (M) и Fib (N)

int findGCDofFibMFibN(int M,  int N)

{

    return fib(gcd(M, N));

}

  
// Код драйвера

int main()

{

   int M = 3, N = 12;

   cout << findGCDofFibMFibN(M, N);

   return 0;

}

Джава

// Java-программа для поиска GCD Fib (M) и Fib (N)

class gcdOfFibonacci

{

    static final int MAX = 1000;

    static int[] f;

  

    gcdOfFibonacci()  // Конструктор

    {

        // Создать массив для запоминания

        f = new int[MAX];

    }

  

    // Возвращает n-е число Фибоначчи, используя таблицу f [].

    // Подробности см. В методе 6 ниже.

    // https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/amp/

    private static int fib(int n)

    {

        // Базовые случаи

        if (n == 0)

            return 0;

        if (n == 1 || n == 2)

            return (f[n] = 1);

  

        // Если fib (n) уже вычислен

        if (f[n]!=0)

            return f[n];

  

        int k = ((n & 1)==1)? (n+1)/2 : n/2;

  

        // Применение рекурсивной формулы [Примечание: значение n & 1 равно 1

        // если n нечетно, иначе 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];

    }

  

    // Функция для возврата gcd из a и b

    private static int gcd(int M, int N)

    {

        if (M == 0)

            return N;

        return gcd(N%M, M);

    }

  

    // Этот метод возвращает GCD Fib (M) и Fib (N)

    static int findGCDofFibMFibN(int M,  int N)

    {

        return fib(gcd(M, N));

    }

  

    // Метод драйвера

    public static void main(String[] args)

    {

        // Возвращает GCD Fib (M) и Fib (N)

        gcdOfFibonacci obj = new gcdOfFibonacci();

        int M = 3, N = 12;

        System.out.println(findGCDofFibMFibN(M, N));

    }

}
// Этот код предоставлен Панкаджем Кумаром

python3

# Программа Python для поиска
# GCD Fib (M) и Fib (N)

  

MAX = 1000

   
# Создать массив для запоминания

f=[0 for i in range(MAX)]

   
# Возвращает n-й Фибоначчи
# число с использованием таблицы f [].
# См. Способ 6 ниже
# пост для подробностей.
# https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/amp/

def fib(n):

  

    # Базовые случаи

    if (n == 0):

        return 0

    if (n == 1 or n == 2):

        f[n] = 1

   

    # Если fib (n) уже вычислен

    if (f[n]):

        return f[n]

   

    k = (n+1)//2 if(n & 1) else n//2

   

    # Применение рекурсивного

    # формула [Примечание: значение n & 1 равно 1

    # если n нечетно, иначе 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]

  

   
# Функция для возврата
# gcd a и b

def gcd(M, N):

  

    if (M == 0):

        return N

    return gcd(N % M, M)

  

   
# Возвращает GCD из
# Fib (M) и Fib (N)

def findGCDofFibMFibN(M, N):

  

    return fib(gcd(M, N))

  

   
# Код драйвера

  

M = 3

N = 12

  

print(findGCDofFibMFibN(M, N))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # Программа для поиска GCD из
// Fib (M) и Fib (N)

using System;

  

class gcdOfFibonacci {

      

    static int MAX = 1000;

    static int []f;

  

    // Конструктор

    gcdOfFibonacci() 

    {

        // Создать массив

        // для запоминания

        f = new int[MAX];

    }

  

    // Возвращает n-е число Фибоначчи

    // используя таблицу f []. Обратитесь метод

    // 6 ниже сообщения для деталей.

    // https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/amp/

    private static int fib(int n)

    {

        // Базовые случаи

        if (n == 0)

            return 0;

        if (n == 1 || n == 2)

            return (f[n] = 1);

  

        // Если fib (n)

        // уже вычислено

        if (f[n]!=0)

            return f[n];

  

        int k = ((n & 1)==1)? (n+1)/2 : n/2;

  

        // Применение рекурсивной формулы

        // [Примечание значение n & 1 равно 1

        // если n нечетно, иначе 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];

    }

  

    // Функция для возврата gcd из a и b

    private static int gcd(int M, int N)

    {

        if (M == 0)

            return N;

        return gcd(N%M, M);

    }

  

    // Этот метод возвращает GCD из

    // Fib (M) и Fib (N)

    static int findGCDofFibMFibN(int M, int N)

    {

        return fib(gcd(M, N));

    }

  

    // Метод драйвера

    public static void Main()

    {

        // Возвращает GCD Fib (M) и Fib (N)

        new gcdOfFibonacci();

        int M = 3, N = 12;

        Console.Write(findGCDofFibMFibN(M, N));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска
// GCD Fib (M) и Fib (N)

$MAX = 1000;

  
// Создать массив для запоминания

$f = array_fill(0, $MAX, 0);

  
// Возвращает n-е число Фибоначчи
// используя таблицу f []. Обратитесь метод
// 6 ниже сообщения для деталей.

function fib($n)

{

    global $f;

      

    // Базовые случаи

    if ($n == 0)

        return 0;

    if ($n == 1 or $n == 2)

        $f[$n] = 1;

  

    // Если fib (n) уже вычислен

    if ($f[$n])

        return $f[$n];

  

    $k = ($n & 1) ? ($n + 1) / 2 : $n / 2;

  

    // Применение рекурсивной формулы [Примечание

    // значение n & 1 равно 1, если n нечетно, иначе 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];

}

  
// Функция для возврата gcd из a и b

function gcd($M, $N)

{

    if ($M == 0)

        return $N;

    return gcd($N % $M, $M);

}

  
// Возвращает GCD Fib (M) и Fib (N)

function findGCDofFibMFibN($M, $N)

{

    return fib(gcd($M, $N));

}

  
// Код драйвера

$M = 3;

$N = 12;

  

print(findGCDofFibMFibN($M, $N))

  
// Этот код добавлен
// по миц
?>


Выход:

2

Эта статья предоставлена Shubham Agrawal . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

GCD и числа Фибоначчи

0.00 (0%) 0 votes