Подсчитайте числа Фибоначчи в заданном диапазоне за время O (Log n) и пространство O (1)

Опубликовано: 21 Января, 2022

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

 Ввод: низкий = 10, высокий = 100
Выход: 5
Приведены пять чисел Фибоначчи.
диапазона, числа 13, 21, 34, 55 и 89.

Ввод: низкий = 10, высокий = 20
Выход: 1
Есть только одно число Фибоначчи, 13.

Вход: низкий = 0, высокий = 1
Выход: 3
Числа Фибоначчи 0, 1 и 1

Мы настоятельно рекомендуем вам свернуть браузер и сначала попробовать это самостоятельно.
Решение грубой силы состоит в том, чтобы одно за другим найти все числа Фибоначчи и подсчитать все числа Фибоначчи в заданном диапазоне.
Эффективное решение - использовать предыдущее число Фибоначчи для генерации следующего, используя простую формулу Фибоначчи: f _n = f _n-1 + f _n-2 .

C++

// C++ program to count Fibonacci numbers in given range
#include <bits/stdc++.h>
using namespace std;
 
// Returns count of fibonacci numbers in [low, high]
int countFibs(int low, int high)
{
    // Initialize first three Fibonacci Numbers
    int f1 = 0, f2 = 1, f3 = 1;
 
    // Count fibonacci numbers in given range
    int result = 0;
 
    while (f1 <= high)
    {
        if (f1 >= low)
        result++;
        f1 = f2;
        f2 = f3;
        f3 = f1 + f2;
    }
 
    return result;
}
 
// Driver program
int main()
{
int low = 10, high = 100;
cout << "Count of Fibonacci Numbers is "
        << countFibs(low, high);
return 0;
}

Python3

# Python3 program to count Fibonacci
# numbers in given range
 
# Returns count of fibonacci
# numbers in [low, high]
def countFibs(low, high):
     
    # Initialize first three
    # Fibonacci Numbers
    f1, f2, f3 = 0, 1, 1
 
    # Count fibonacci numbers in
    # given range
    result = 0
 
    while (f1 <= high):
        if (f1 >= low):
            result += 1
        f1 = f2
        f2 = f3
        f3 = f1 + f2
 
    return result
 
# Driver Code
low, high = 10, 100
print("Count of Fibonacci Numbers is",
                 countFibs(low, high))
 
# This code is contributed
# by mohit kumar

C#

// C# program to count Fibonacci
// numbers in given range
using System;
 
public class GFG
{
     
    // Returns count of fibonacci
    // numbers in [low, high]
    static int countFibs(int low,
                        int high)
    {
         
        // Initialize first three
        // Fibonacci Numbers
        int f1 = 0, f2 = 1, f3 = 1;
     
        // Count fibonacci numbers
        // in given range
        int result = 0;
     
        while (f1 <= high)
        {
            if (f1 >= low)
            result++;
            f1 = f2;
            f2 = f3;
            f3 = f1 + f2;
        }
     
        return result;
    }
     
    // Driver Code
    public static void Main(String []args)
    {
        int low = 10, high = 100;
        Console.WriteLine("Count of Fibonacci Numbers is "
                        + countFibs(low, high));
    }
}
     
// This code is contributed by Sam007.

PHP

<?php
// PHP program to count
// Fibonacci numbers in
// given range
 
// Returns count of fibonacci
// numbers in [low, high]
function countFibs($low, $high)
{
    // Initialize first
    // three Fibonacci Numbers
    $f1 = 0; $f2 = 1; $f3 = 1;
 
    // Count fibonacci
    // numbers in given range
    $result = 0;
 
    while ($f1 <= $high)
    {
        if ($f1 >= $low)
        $result++;
        $f1 = $f2;
        $f2 = $f3;
        $f3 = $f1 + $f2;
    }
 
    return $result;
}
 
// Driver Code
$low = 10; $high = 100;
echo "Count of Fibonacci Numbers is ",
               countFibs($low, $high);
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// JavaScript program to count Fibonacci
// numbers in given range
 
    // Returns count of fibonacci
    // numbers in [low, high]
    function countFibs(low, high)
    {
           
        // Initialize first three
        // Fibonacci Numbers
        let f1 = 0, f2 = 1, f3 = 1;
       
        // Count fibonacci numbers
        // in given range
        let result = 0;
       
        while (f1 <= high)
        {
            if (f1 >= low)
            result++;
            f1 = f2;
            f2 = f3;
            f3 = f1 + f2;
        }
       
        return result;
    }
 
// Driver program
 
        let low = 10, high = 100;
        document.write("Count of Fibonacci Numbers is "
                           + countFibs(low, high));
 
// This code is contributed by susmitakundugoaldanga.
</script>

Выход :

 Счетчик чисел Фибоначчи - 5

Анализ сложности времени:
Учтите, что числа Фибоначчи можно записать следующим образом:

Таким образом, значение чисел Фибоначчи растет экспоненциально. Это означает, что цикл while растет экспоненциально, пока не достигнет «высокого» значения. Таким образом, цикл выполняется O (Log (high)) раз.
Одним из решений может быть прямое использование приведенной выше формулы для подсчета чисел Фибоначчи, но это практически невозможно (подробности см. Здесь).
Вспомогательное пространство: O (1)
Эта статья предоставлена Судханшу Гуптой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

Подсчитайте числа Фибоначчи в заданном диапазоне за время O (Log n) и пространство O (1)

C++

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ