Рубрики

n-е кратное число в серии Фибоначчи

Даны два целых числа n и k. Найдите положение n-го кратного K в ряду Фибоначчи.

Примеры :

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
5'th multiple of 5 in Fibonacci Series is 832040 
which appears at position 30.

Серия Фибоначчи (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… (пренебрегая первым 0).

Простое решение — пройти по числам Фибоначчи, начиная с первого числа. Во время обхода следите за количеством кратных k. Когда счет становится n, верните позицию.

Эффективное решение основано на следующем интересном свойстве.
Ряд Фибоначчи всегда периодичен при модульном представлении. Ниже приведены примеры.

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.

Почему серия Фибоначчи периодична по модулю?
При модульном представлении мы знаем, что каждое число Фибоначчи будет представлено как некоторый остаток 0? F (мод м) <м. Таким образом, существует только m возможных значений для любого заданного F (mod m) и, следовательно, m * m = m ^ 2 возможных пар последовательных членов в последовательности. Поскольку m ^ 2 конечно, мы знаем, что некоторая пара терминов должна в конечном итоге повториться. Кроме того, поскольку любая пара членов в последовательности Фибоначчи определяет остальную часть последовательности, мы видим, что ряд Фибоначчи по модулю m должен повторяться в некоторой точке и, следовательно, должен быть периодическим.
Источник: https://www.whitman.edu/Documents/Academics/Matmatics/clancy.pdf.

Основываясь на вышеизложенном факте, мы можем быстро найти положение n-го мультипликатора K, просто найдя первый мультипликатор. Если позиция первого кратного равна i, мы возвращаем позицию как n * i.

Ниже приведена реализация:

C ++

// C ++ программа для поиска позиции
// из n-го кратного числа
// k в серии Фибоначчи
# include <bits/stdc++.h>

using namespace std;

  

const int MAX = 1000;

  
// Возвращает позицию n-го множества
// из k в серии Фибоначчи

int findPosition(int k, int n)

{

    // перебирать все

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

    unsigned long long int f1 = 0, 

                           f2 = 1, 

                           f3;

    for (int i = 2; i <= MAX; i++)

    {

        f3 = f1 + f2;

        f1 = f2;

        f2 = f3;

  

        // Найден первый кратный

        // k в положении i

        if (f2 % k == 0)

  

        // n-й кратный будет в

        // позиция n * i с использованием Периодического

        // свойство чисел Фибоначчи

        // по модулю.

        return n * i;

    }

}

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

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-программа для поиска позиции
// из n-го кратного числа
// k в серии Фибоначчи

  

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;

    }

  

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

    public static void main(String[] args)

    {

        // Множественный номер

        int n = 5;

  

        // Номер которого кратен

        // мы находим

        int k = 4;

  

        System.out.print("Position of n'th multiple" +

                     " of k in Fibonacci Series is ");

  

        System.out.println(findPosition(k, n));

    }

}

  
// Этот код добавлен
// Мохит Гупта_OMG

python3

# Программа Python для поиска позиции
число n-го кратного числа k
# в серии Фибоначчи

  

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

  

  
# Несколько

n = 5;

# Количество которых кратно
# мы находим

k = 4;

  

print("Position of n'th multiple of k in"

      "Fibonacci Seires is", findPosition(k, n));

  
# Этот код добавлен
# от Mohit Gupta_OMG

C #

// C # Программа для поиска позиции
// n кратное число m в k
// Серия Фибоначчи

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;

    }

      

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

    public static void Main()

    {

        // Множественный номер

        int n = 5;

  

        // Номер которого кратен

        // мы находим

        int k = 4;

  

        Console.Write("Position of n'th multiple " +  

                      "of k in Fibonacci Series is ");

          

        // вызов функции

        Console.WriteLine(findPosition(k, n));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска позиции
// из n-го кратного числа mumber
// k в серии Фибоначчи

$MAX = 1000;

  
// Возвращает позицию n-го множества
// из k в серии Фибоначчи

function findPosition($k, $n)

{

    global $MAX;

      

    // перебирать все

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

    $f1 = 0; $f2 = 1; $f3;

    for ($i = 2; $i <= $MAX; $i++)

    {

        $f3 = $f1 + $f2;

        $f1 = $f2;

        $f2 = $f3;

  

        // Найден первый кратный

        // k в положении i

        if ($f2 % $k == 0)

  

        // n-й кратный будет в

        // позиция n * i с использованием Периодического

        // свойство чисел Фибоначчи

        // по модулю

        return $n * $i;

    }

}

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

$n = 5; $k = 4;

echo("Position of n'th multiple of k"

           " in Fibonacci Series is "

                 findPosition($k, $n));

  
// Этот код предоставлен Ajit.
?>


Выход :

Position of n'th multiple of k in Fibonacci Series is 30

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

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

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

n-е кратное число в серии Фибоначчи

0.00 (0%) 0 votes