Рубрики

Эффективный способ проверить, является ли n-е число Фибоначчи кратным 10

Нам дана переменная n, нам нужно выяснить, будет ли число Фибоначчи кратно 10 или нет.

Примеры:

Input : 15
Output : Yes

Input : 17
Output : No

Простой метод состоит в том, чтобы найти n-е число Фибоначчи и проверить, делится ли оно на 10 или нет.

C ++

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

  

int fibonacci(int n)

{

    int a = 0, b = 1, c;

    if (n <= 1)

        return n;

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

    {

        c = a + b;

        a = b;

        b = c;

    }

    return c;

}

  
// Возвращает истину, если n-е число Фибоначчи
// кратно 10.

bool isMultipleOf10(int n)

{

    int f = fibonacci(30);

    return  (f % 10 == 0);

}

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

int main()

{

    int n = 30;

    if (isMultipleOf10(n))

        printf("Yes\n");

    else

        printf("No\n");

}

Джава

// Простая Java-программа для проверки
// n-е число Фибоначчи кратно
// из 10.

class Fibonacci

{

    static int fibonacci(int n)

    {

        int a = 0;

        int b=1;

        int c=0;

        if (n <= 1)

            return n;

          

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

        {

            c = a + b;

            a = b;

            b = c;

        }

          

        return c;

    }

      

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

    // кратно 10.

    static boolean isMultipleOf10(int n)

    {

        int f = fibonacci(30);

        return  (f % 10 == 0);

    }

      

    // основная функция

    public static void main (String[] args) 

    {

        int n = 30;

        if (isMultipleOf10(n))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

Python 3

# Простая программа на Python 3, чтобы проверить,
# n-е число Фибоначчи кратно
№ 10

  

def fibonacci(n):

  

    a = 0

    b = 1

    if (n <= 1):

        return n

    for i in range(2, n + 1):

      

        c = a + b

        a = b

        b = c

      

    return c

  
# Возвращает истину, если n-й Фибоначчи
# число кратно 10.

def isMultipleOf10(n):

    f = fibonacci(30)

    return (f % 10 == 0)

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

if __name__ =="__main__":

      

    n = 30

    if (isMultipleOf10(n)):

        print("Yes")

    else:

        print("No")

  
# Этот код предоставлен ita_c

C #

// Простая программа на C # для проверки
// n-е число Фибоначчи кратно
// из 10.

using System;

  

class GFG {

      

    static int fibonacci(int n)

    {

        int a = 0;

        int b = 1;

        int c = 0;

        if (n <= 1)

            return n;

          

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

        {

            c = a + b;

            a = b;

            b = c;

        }

          

        return c;

    }

      

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

    // число кратно 10.

    static bool isMultipleOf10(int n)

    {

        int f = fibonacci(30);

        return (f % 10 == 0);

    }

      

    // основная функция

    public static void Main () 

    {

        int n = 30;

          

        if (isMultipleOf10(n))

            Console.Write("Yes");

        else

            Console.Write("No");

    }

}

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

PHP

<?php

  
// Простая PHP-программа для
// проверяем n-й Фибоначчи
// число кратно 10.

  

function fibonacci($n)

{

    $a = 0; $b = 1; $c;

    if ($n <= 1)

        return $n;

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

    {

        $c = $a + $b;

        $a = $b;

        $b = $c;

    }

    return $c;

}

  
// Возвращает истину, если n-й Фибоначчи
// число кратно 10.

function isMultipleOf10($n)

{

    $f = fibonacci(30);

    return ($f % 10 == 0);

}

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

    $n = 30;

      

    if (isMultipleOf10($n))

        echo "Yes\n";

    else

        echo "No\n";

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


Выход:

Yes

Эффективный метод:

Приведенное выше решение может не работать, если n очень большое, тогда невозможно найти число Фибоначчи. Более того, мы можем проверить, не найдя число Фибоначчи, посмотрев на шаблон. Посмотрим как!

Если число делится на 10, то оно должно делиться на 5 и 2 оба.

Кратные 2 в серии Фибоначчи:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 ….
Число, показанное жирным шрифтом, делится на 2. При тщательном наблюдении мы обнаруживаем, что каждое третье число делится на 2.

Кратные 5 в серии Фибоначчи:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 ……

Числа, выделенные жирным шрифтом, делятся на 5. При тщательном наблюдении мы обнаруживаем, что каждое 5-е число делится на 5.

Теперь LCM из 3 и 5 равно 15. Итак, каждое 15-е число Фибоначчи будет делиться на 10. Итак, нам не нужно находить число Фибоначчи, просто мы должны проверить, делится ли n на 15 или нет. Ниже приведена реализация.

C ++

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

  
// Возвращает истину, если n-е число Фибоначчи
// кратно 10.

bool isMultipleOf10(int n)

{

    return  (n % 15 == 0);

}

  

int main()

{

    int n = 30;

    if (isMultipleOf10(n))

        printf("Yes\n");

    else

        printf("No\n");

    return 0;

}

Джава

// Простая Java-программа для проверки
// n-е число Фибоначчи кратно
// из 10.

class Fibonacci

{

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

    // кратно 10.

    static boolean isMultipleOf10(int n)

    {

        if(n%15 == 0)

            return  true;

          

        return false;    

    }

      

    // основная функция

    public static void main (String[] args) 

    {

        int n = 30;

        if (isMultipleOf10(n))

            System.out.println("Yes");

        else

            System.out.println("No");

    }

python3

# Простая программа на Python 3, чтобы проверить,
# n-е число Фибоначчи кратно
№ 10

  
# Возвращает true, если n-е число Фибоначчи
# кратно 10.

def isMultipleOf10(n):

  

    return (n % 15 == 0)

  
Код водителя

n = 30

  

if (isMultipleOf10(n)):

    print("Yes");

else:

    print("No");

  
# Этот код добавлен
# от Akanksha Rai

C #

// Простая программа на C # для проверки
// n-е число Фибоначчи кратно
// из 10.

using System;

  

class GFG {

  

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

    // кратно 10.

    static bool isMultipleOf10(int n)

    {

        if(n % 15 == 0)

            return  true;

           

        return false;    

    }

       

    // основная функция

    public static void Main () 

    {

        int n = 30;

        if (isMultipleOf10(n))

            Console.Write("Yes");

        else

            Console.Write("No");

    }

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

PHP

<?php
// Простая PHP-программа для
// проверяем n-й Фибоначчи
// число кратно 10.

  
// Возвращает true если n-й
// число Фибоначчи
// кратно 10.

function isMultipleOf10($n)

{

    return ($n % 15 == 0);

}

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

$n = 30;

if (isMultipleOf10($n))

    echo "Yes\n";

else

    echo "No\n";

      
// Этот код добавлен
// от akt_mit
?>


Выход:

Yes

Этот код выполняется за O (1) раз.

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

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

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

Эффективный способ проверить, является ли n-е число Фибоначчи кратным 10

0.00 (0%) 0 votes