Количество способов, которыми массив может быть заполнен нулями и единицами, так что ни один последовательный элемент не равен 1
Учитывая число 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.