Количество способов, которыми массив может быть заполнен нулями и единицами, так что ни один последовательный элемент не равен 1

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

Учитывая число N, найдите количество способов построить массив размера N, который содержал бы только единицы и нули, но ни один из двух последовательных индексов не имел в них значения 1.

Примеры:

 Ввод: 2
Выход: 3
Объяснение:
Для n = 2 возможными массивами являются:
{0, 1} {1, 0} {0, 0}

Ввод: 3
Выход: 5
Объяснение:
Для n = 3 возможные массивы:
{0, 0, 0} {1, 0, 0} {0, 1, 0} {0, 0, 1} {1, 0, 1}

Наивный подход:
Базовый подход грубой силы состоит в том, чтобы построить все возможные способы заполнения массива единицами и нулями, а затем проверить, есть ли какие-либо две последовательные единицы в массиве, если они есть, не подсчитывать эти массивы.
Поскольку каждый элемент имеет 2 возможных значения, 1 и 0, и всего n элементов, общее количество массивов без каких-либо ограничений будет экспоненциального порядка, то есть 2 n .

Эффективный подход:
Если присмотреться, можно заметить, что на входе и выходе формируется шаблон.
Для n = 1 количество способов равно 2, т. Е. {0}, {1}
для n = 2 количество способов равно 3
Сходным образом,
для n = 3 количество путей равно 5
для n = 4 количество путей 8
и так далее…

Пусть T () - функция, которая дает количество способов заполнения массива размера n, тогда мы получим следующее рекуррентное соотношение

T(n) = T(n-1) + T(n-2)

И это рекуррентное соотношение ряда Фибоначчи <.
Следовательно, выход для любого n равен (n + 2) члену ряда Фибоначчи, начиная с 1.
т.е. 1 1 2 3 5 8 11…
Итак, теперь нам просто нужно вычислить последовательность Фибоначчи с точностью до (n + 2) -го элементов, и это будет ответ.

Time complexity is O(n) 

C++

// C++ implementation of the
// above approach
#include <iostream>
using namespace std;
 
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    int nth_term(int n)
    {
        int a = 1, b = 1, c = 1;
         
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for (int i = 0; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
         
        return c;
    }
     
    // Driver Code
    int main()
    {
         
        // Take input n
        int n = 10;
        int c = nth_term(n);
         
        // printing output
        cout << c;
    }
 
// This code is contributed by Sumit Sudhakar.

Java

// Java implementation of the
// above approach
class Main
{
  
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    public static int nth_term(int n)
    {
        int a = 1, b = 1, c = 1;
          
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for (int i = 0; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
          
        return c;
    }
      
    // Driver program
    public static void main(String[] args)
    {
        // Take input n
        int n = 10;
        int c = nth_term(n);
          
        // printing output
        System.out.println(c);
    }
}

Python3

# Python3 implementation of
# the above approach
 
# The total number of ways
# is equal to the (n+2)th
# Fibonacci term, hence we
# only need to find that.
def nth_term(n) :
     
    a = 1
    b = 1
    c = 1
     
    # Construct fibonacci upto
    # (n+2)th term the first
    # two terms being 1 and 1
    for i in range(0, n) :
        c = a + b
        a = b
        b = c
    return c
 
# Driver Code
 
# Take input n
n = 10
c = nth_term(n)
 
# printing output
print (c)
# This code is contributed by
# Manish Shaw (manishshaw1)

C#

// C# implementation of the
// above approach
using System;
 
class GFG {
     
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    static int nth_term(int n)
    {
        int a = 1, b = 1, c = 1;
         
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for (int i = 0; i < n; i++)
        {
            c = a + b;
            a = b;
            b = c;
        }
         
        return c;
    }
     
    // Driver Code
    public static void Main()
    {
         
        // Take input n
        int n = 10;
        int c = nth_term(n);
         
        // printing output
        Console.WriteLine(c);
     
    }
}
     
// This code is contributed by Sam007

PHP

<?php
// PHP implementation of the
// above approach
 
    // The total number of ways
    // is equal to the (n+2)th
    // Fibonacci term, hence we
    // only need to find that.
    function nth_term($n)
    {
        $a = 1; $b = 1; $c = 1;
         
        // Construct fibonacci upto
        // (n+2)th term the first
        // two terms being 1 and 1
        for ($i = 0; $i < $n; $i++)
        {
            $c = $a + $b;
            $a = $b;
            $b = $c;
        }
         
        return $c;
    }
     
        // Driver Code
         
        // Take input n
        $n = 10;
        $c = nth_term($n);
         
        // printing output
        echo $c;
     
// This code is contributed by nitin mittal
?>

Javascript

<script>
 
// Javascript implementation of the
// above approach
 
// The total number of ways
// is equal to the (n+2)th
// Fibonacci term, hence we
// only need to find that.
function nth_term(n)
{
    let a = 1, b = 1, c = 1;
       
    // Construct fibonacci upto
    // (n+2)th term the first
    // two terms being 1 and 1
    for(let i = 0; i < n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
 
// Driver code
 
// Take input n
let n = 10;
let c = nth_term(n);
 
// Printing output
document.write(c);
 
// This code is contributed by rameshtravel07
 
</script>

Выход:

 144

Мы можем дополнительно оптимизировать вышеуказанное решение для работы в O (Log n), используя решение матричного возведения в степень для нахождения n-го числа Фибоначчи (см. Методы 4, 5 и 6 Программы для чисел Фибоначчи).

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

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