Рубрики

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

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

Примеры:

Input  : 2
Output : 3
Explanation:
For n=2, the possible arrays are:
{0, 1} {1, 0} {0, 0}

Input  : 3
Output : 5
Explanation:
For n=3, the possible arrays are:
{0, 0, 0} {1, 0, 0} {0, 1, 0} {0, 0, 1} {1, 0, 1} 

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

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

Эффективный подход:
Если мы немного понаблюдаем, мы можем заметить, что на входе и выходе формируется паттерн.

Для n = 1 количество путей равно 2, т.е. {0}, {1}
при п = 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) -го элементов , и это будет ответом.
Временная сложность O (n)

C ++

// C ++ реализация
// вышеуказанный подход
#include <iostream>

using namespace std;

  

    // Общее количество способов

    // равно (n + 2) -ому

    // термин Фибоначчи, следовательно, мы

    // нужно только найти это.

    int nth_term(int n)

    {

        int a = 1, b = 1, c = 1;

          

        // Построить Фибоначчи до

        // (n + 2) -й член первый

        // два слагаемых: 1 и 1

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

        {

            c = a + b;

            a = b;

            b = c;

        }

          

        return c;

    }

      

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

    int main()

    {

          

        // Взять n

        int n = 10;

        int c = nth_term(n);

          

        // вывод на печать

        cout << c;

    }

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

Джава

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

class Main 

{

   

    // Общее количество способов

    // равно (n + 2) -ому

    // термин Фибоначчи, следовательно, мы

    // нужно только найти это.

    public static int nth_term(int n)

    {

        int a = 1, b = 1, c = 1;

           

        // Построить Фибоначчи до

        // (n + 2) -й член первый

        // два слагаемых: 1 и 1

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

        {

            c = a + b;

            a = b;

            b = c;

        }

           

        return c;

    }

       

    // Драйвер программы

    public static void main(String[] args)

    {

        // Взять n

        int n = 10;

        int c = nth_term(n);

           

        // вывод на печать

        System.out.println(c);

    }

}

python3

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

  
# Общее количество способов
# равно (n + 2) -ому
# Термин Фибоначчи, следовательно, мы
# нужно только найти это.

def nth_term(n) :

      

    a = 1

    b = 1

    c = 1

      

    # Построить Фибоначчи до

    # (n + 2) -й срок первый

    # два слагаемых: 1 и 1

    for i in range(0, n) :

        c = a + b

        a = b

        b = c

    return c

  
Код водителя

  
# Взять n

n = 10

c = nth_term(n)

  
# вывод на печать

print (c)

# Этот код предоставлен
# Маниш Шоу (manishshaw1)

C #

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

using System;

  

class GFG {

      

    // Общее количество способов

    // равно (n + 2) -ому

    // термин Фибоначчи, следовательно, мы

    // нужно только найти это.

    static int nth_term(int n)

    {

        int a = 1, b = 1, c = 1;

          

        // Построить Фибоначчи до

        // (n + 2) -й член первый

        // два слагаемых: 1 и 1

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

        {

            c = a + b;

            a = b;

            b = c;

        }

          

        return c;

    }

      

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

    public static void Main()

    {

          

        // Взять n

        int n = 10;

        int c = nth_term(n);

          

        // вывод на печать

        Console.WriteLine(c);

      

    }

}

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

  

  

  

PHP

<?php
// Реализация PHP
// вышеуказанный подход

  

    // Общее количество способов

    // равно (n + 2) -ому

    // термин Фибоначчи, следовательно, мы

    // нужно только найти это.

    function nth_term($n)

    {

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

          

        // Построить Фибоначчи до

        // (n + 2) -й член первый

        // два слагаемых: 1 и 1

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

        {

            $c = $a + $b;

            $a = $b;

            $b = $c;

        }

          

        return $c;

    }

      

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

          

        // Взять n

        $n = 10;

        $c = nth_term($n);

          

        // вывод на печать

        echo $c;

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


Выход:

144

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

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

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

0.00 (0%) 0 votes