Рубрики

Нахождение количества цифр в n-м числе Фибоначчи

Учитывая число n, найдите количество цифр в n-ых числах Фибоначчи. Первые несколько чисел Фибиначи — это 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,….

Примеры:

Input : n = 6
Output : 1
6'th Fibonacci number is 8 and it has 
1 digit.

Input : n = 12
Output : 3
12'th Fibonacci number is 144 and it has 
3 digits.

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

Прямой способ — подсчитать количество цифр в n-м числе Фибоначчи, используя приведенную ниже формулу Бине.

fib(n) = (Φn - Ψ-n) / √5
where
Φ = (1 + √5) / 2
Ψ = (1 - √5) / 2

The above formula can be simplified, 
fib(n) = round(Φn / ? 5) 
Here round function indicates nearest integer.

Count of digits in Fib(n) = Log10Fib(n)
                          = Log10n / √5)
                          = n*Log10(Φ) - Log10√5
                          = n*Log10(Φ) - (Log105)/2

Как упомянуто в этом G-Fact, эта формула, кажется, не работает и производит правильные числа Фибоначчи из-за ограничений арифметики с плавающей запятой. Тем не менее, выглядит целесообразным использовать эту формулу, чтобы найти количество цифр в n-м числе Фибоначчи.

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

C ++

/ * C ++ программа для поиска количества цифр в nth

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

#include<bits/stdc++.h>

using namespace std;

  
// Эта функция возвращает количество цифр
// в n-м числе Фибоначчи после потолка
// Используемая формула (n * log (phi) - (log 5) / 2)

long long numberOfDigits(long long n)

{

    if (n == 1)

        return 1;

  

    // используя phi = 1.6180339887498948

    long double d = (n * log10(1.6180339887498948)) -

                    ((log10(5)) / 2);

  

    return ceil(d);

}

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

int main()

{

    long long i;

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

    cout << "Number of Digits in F("

         << i <<") - "

         << numberOfDigits(i) << "n";

  

    return 0;

}

Джава

// Java-программа для поиска числа цифр в n-ом
// число Фибоначчи

  

class GFG 

{

    // Эта функция возвращает количество цифр

    // в n-м числе Фибоначчи после потолка

    // Используемая формула (n * log (phi) - (log 5) / 2)

    static double numberOfDigits(double n)

    {

        if (n == 1)

            return 1;

      

        // используя phi = 1.6180339887498948

        double d = (n * Math.log10(1.6180339887498948)) -

                   ((Math.log10(5)) / 2);

      

        return Math.ceil(d);

    }

  

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

    public static void main (String[] args)

    {

        double i;

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

        System.out.println("Number of Digits in F("+i+") - " 

                           +numberOfDigits(i));

    }

}

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

python3

# Python программа для поиска
количество цифр в nth
Число Фибоначчи

import math

  
# хранение значения
# золотое сечение ака фи

phi = (1 + 5**.5) / 2

  
# функция для поиска номера
Количество цифр в F (n) This
# функция возвращает номер
Количество цифр в Фибоначчи
число после потолка
# Используемая формула (n * log (phi) -
№ (журнал 5) / 2)

def numberOfDig (n) :

    if n == 1 :

        return 1

    return math.ceil((n * math.log10(phi) - 

                      .5 * math.log10(5)))

  

// Driver Code

for i in range(1, 11) :

    print("Number of Digits in F(" + 

                   str(i) + ") - " + 

                str(numberOfDig(i)))

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

C #

// C # программа для поиска номера
// цифры в n-м числе Фибоначчи

using System;

  

class GFG {

      

    // Эта функция возвращает количество цифр

    // в n-м числе Фибоначчи после потолка

    // Используемая формула (n * log (phi) - (log 5) / 2)

    static double numberOfDigits(double n)

    {

        if (n == 1)

            return 1;

      

        // используя phi = 1.6180339887498948

        double d = (n * Math.Log10(1.6180339887498948)) -

                   ((Math.Log10(5)) / 2);

      

        return Math.Ceiling(d);

    }

  

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

    public static void Main ()

    {

        double i;

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

        Console.WriteLine("Number of Digits in F("+ i +") - "

                           + numberOfDigits(i));

    }

}

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

PHP

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

  
// Эта функция возвращает
// количество цифр в nth
// число Фибоначчи после
// потолок это формула используется
// (n * log (phi) - (log 5) / 2)

function numberOfDigits($n)

{

    if ($n == 1)

        return 1;

  

    // используя phi = 1.6180339887498948

    $d = ($n * log10(1.6180339887498948)) -

                          ((log10(5)) / 2);

  

    return ceil($d);

}

  

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

    $i;

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

    echo "Number of Digits in F($i) - "

         , numberOfDigits($i), "\n";

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


Выход:

Number of Digits in F(1) - 1
Number of Digits in F(2) - 1
Number of Digits in F(3) - 1
Number of Digits in F(4) - 1
Number of Digits in F(5) - 1
Number of Digits in F(6) - 1
Number of Digits in F(7) - 2
Number of Digits in F(8) - 2
Number of Digits in F(9) - 2
Number of Digits in F(10) - 2

Ссылки:
http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section2
https://en.wikipedia.org/wiki/Fibonacci_number

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

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

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

Нахождение количества цифр в n-м числе Фибоначчи

0.00 (0%) 0 votes