Рубрики

Как проверить, является ли данное число числом Фибоначчи?

Учитывая число 'n', как проверить, является ли n числом Фибоначчи . Первые несколько чисел Фибоначчи 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ..

Примеры :

Input : 8
Output : Yes

Input : 34
Output : Yes

Input : 41
Output : No

Простой способ — генерировать числа Фибоначчи, пока сгенерированное число не станет больше или равно 'n'. Ниже приводится интересное свойство о числах Фибоначчи, которое также можно использовать для проверки, является ли данное число Фибоначчи или нет.
Число есть число Фибоначчи тогда и только тогда, когда один или оба из (5 * n 2 + 4) или (5 * n 2 — 4) являются идеальным квадратом (Источник: Wiki ). Ниже приводится простая программа, основанная на этой концепции.

C ++

// C ++ программа для проверки, является ли х идеальным квадратом
#include <iostream>
#include <math.h>

using namespace std;

  
// Вспомогательная функция, которая возвращает true, если x - идеальный квадрат

bool isPerfectSquare(int x)

{

    int s = sqrt(x);

    return (s*s == x);

}

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

bool isFibonacci(int n)

{

    // n - это число Фибиначи, если один из 5 * n * n + 4 или 5 * n * n - 4 или оба

    // является идеальным квадратом

    return isPerfectSquare(5*n*n + 4) ||

           isPerfectSquare(5*n*n - 4);

}

  
// Утилита для проверки вышеуказанных функций

int main()

{

  for (int i = 1; i <= 10; i++)

     isFibonacci(i)? cout << i << " is a Fibonacci Number \n":

                     cout << i << " is a not Fibonacci Number \n" ;

  return 0;

}

Джава

// Java-программа для проверки, является ли х идеальным квадратом

  

class GFG

{

    // Служебный метод, который возвращает true, если x - идеальный квадрат

    static  boolean isPerfectSquare(int x)

    {

        int s = (int) Math.sqrt(x);

        return (s*s == x);

    }

       

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

    static boolean isFibonacci(int n)

    {

        // n - это Фибоначчи, если один из 5 * n * n + 4 или 5 * n * n - 4 или оба

        // идеальный квадрат

        return isPerfectSquare(5*n*n + 4) ||

               isPerfectSquare(5*n*n - 4);

    }

  

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

    public static void main(String[] args)

    {

        for (int i = 1; i <= 10; i++)

             System.out.println(isFibonacci(i) ?  i +  " is a Fibonacci Number" :

                                                  i + " is a not Fibonacci Number");

    }

}
// Этот код предоставлен Никитой Тивари

питон

# python программа для проверки, является ли x идеальным квадратом

import math

  
# Сервисная функция, которая возвращает true, если x - идеальный квадрат

def isPerfectSquare(x):

    s = int(math.sqrt(x))

    return s*s == x

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

def isFibonacci(n):

  

    # n - это число Фибиначи, если один из 5 * n * n + 4 или 5 * n * n - 4 или оба

    # - идеальный квадрат

    return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4)

     
# Полезная функция для проверки вышеуказанных функций

for i in range(1,11):

     if (isFibonacci(i) == True):

         print i,"is a Fibonacci Number"

     else:

         print i,"is a not Fibonacci Number "

C #

// C # программа для проверки
// х идеальный квадрат

using System;

  

class GFG {

  

    // Вспомогательная функция, которая возвращает

    // истина, если х - идеальный квадрат

    static bool isPerfectSquare(int x)

    {

        int s = (int)Math.Sqrt(x);

        return (s * s == x);

    }

  

    // Возвращает true, если n

    // число Фибоначчи, иначе ложь

    static bool isFibonacci(int n)

    {

        // n - это Фибоначчи, если один из

        // 5 * n * n + 4 или 5 * n * n - 4 или

        // оба - идеальный квадрат

        return isPerfectSquare(5 * n * n + 4) || 

               isPerfectSquare(5 * n * n - 4);

    }

  

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

    public static void Main()

    {

        for (int i = 1; i <= 10; i++)

            Console.WriteLine(isFibonacci(i) ? i + 

                              " is a Fibonacci Number" : i +

                              " is a not Fibonacci Number");

    }

}

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

PHP

<?php
// PHP программа для проверки
// х идеальный квадрат

  
// Полезная функция, которая
// возвращает true, если x
// идеальный квадрат

function isPerfectSquare($x)

{

    $s = (int)(sqrt($x));

    return ($s * $s == $x);

}

  
// Возвращает true, если n
// Число Фибоначчи, иначе ложь

function isFibonacci($n)

{

    // n - это Фибиначи, если один из

    // 5 * n * n + 4 или 5 * n * n - 4 или

    // оба - идеальный квадрат

    return isPerfectSquare(5 * $n * $n + 4) || 

           isPerfectSquare(5 * $n * $n - 4);

}

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

for ($i = 1; $i <= 10; $i++)

if(isFibonacci($i))

echo "$i is a Fibonacci Number \n";

else

echo "$i is a not Fibonacci Number \n" ;

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


Выход:

1 is a Fibonacci Number
2 is a Fibonacci Number
3 is a Fibonacci Number
4 is a not Fibonacci Number
5 is a Fibonacci Number
6 is a not Fibonacci Number
7 is a not Fibonacci Number
8 is a Fibonacci Number
9 is a not Fibonacci Number
10 is a not Fibonacci Number

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

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

Как проверить, является ли данное число числом Фибоначчи?

0.00 (0%) 0 votes