Рубрики

Подсчитайте количество способов заполнить сетку «nx 4», используя плитки «1 x 4»

Учитывая число n, подсчитайте количество способов заполнить тревогу 4 сеткой, используя 1 x 4 плитки.

Примеры:

Input : n = 1
Output : 1

Input : n = 2
Output : 1
We can only place both tiles horizontally

Input : n = 3
Output : 1
We can only place all tiles horizontally.

Input : n = 4
Output : 2
The two ways are : 
  1) Place all tiles horizontally 
  2) Place all tiles vertically.

Input : n = 5
Output : 3
We can fill a 5 x 4 grid in following ways : 
  1) Place all 5 tiles horizontally
  2) Place first 4 vertically and 1 horizontally.
  3) Place first 1 horizontally and 4 horizontally.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Эта проблема в основном является расширением этой проблемы листов

Пусть «count (n)» будет количеством способов разместить плитки на сетке «nx 4» , следующие два случая возникают, когда мы размещаем первую плитку.

  1. Поместите первую плитку горизонтально : если мы поместим первую плитку горизонтально, проблема сводится к «считать (n-1)»
  2. Поместите первую плитку вертикально : если мы поместим первую плитку вертикально, то мы должны разместить еще 3 плитки вертикально. Таким образом, проблема сводится к «считать (n-4)»

Следовательно, count (n) можно записать так, как показано ниже.

   count(n) = 1 if n = 1 or n = 2 or n = 3   
   count(n) = 2 if n = 4
   count(n) = count(n-1) + count(n-4) 

Это повторение аналогично числам Фибоначчи и может быть решено с помощью динамического программирования.

C / C ++

// Программа на C ++ для подсчета способов размещения плиток размером 1 x 4
// на сетке nx 4.
#include<iostream>

using namespace std;

  
// Возвращает количество способов разместить плитки размером 1 x 4
// на сетке nx 4.

int count(int n)

{

    // Создать таблицу для хранения результатов подзадач

    // dp [i] хранит количество путей для сетки ix 4.

    int dp[n+1];

    dp[0] = 0;

  

    // Заполняем таблицу от d [1] до dp [n]

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

    {

        // Базовые случаи

        if (i >= 1 && i <= 3)

            dp[i] = 1;

        else if (i==4)

            dp[i] = 2 ;

  

        else 

            // dp (i-1): разместить первую плитку горизонтально

            // dp (n-4): Поместить первую плитку вертикально

            // что означает, что еще 3 плитки имеют

            // для вертикального размещения.

            dp[i] = dp[i-1] + dp[i-4];

    }

  

    return dp[n];

}

  
// Программа драйвера для тестирования выше

int main()

{

    int n = 5;

    cout << "Count of ways is " << count(n);

    return 0;

}

Джава

// Java-программа для подсчета способов размещения плиток 1 х 4
// на сетке nx 4

import java.io.*;

  

class Grid 

    // Функция, которая подсчитывает количество способов разместить плитки размером 1 x 4

    // на сетке nx 4.

    static int count(int n)

    {

        // Создать таблицу для хранения результатов подзадач

        // dp [i] хранит количество путей для сетки ix 4.

        int[] dp = new int[n+1];

        dp[0] = 0;

        // Заполняем таблицу от d [1] до dp [n]

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

        {

            // Базовые случаи

            if (i >= 1 && i <= 3)

                dp[i] = 1;

            else if (i==4)

                dp[i] = 2 ;

  

            else

            {

                    // dp (i-1): разместить первую плитку горизонтально

                    // dp (i-4): Поместить первую плитку вертикально

                    // что означает, что еще 3 плитки имеют

                    // для вертикального размещения.

                    dp[i] = dp[i-1] + dp[i-4];

            }

        }

        return dp[n];

    }

      

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

    public static void main (String[] args)

    {

        int n = 5;

        System.out.println("Count of ways is: " + count(n));

    }

}

  
// Предоставлено Прамод Кумар

питон

# Python программа для подсчета способов размещения 1 х 4 тайлов
# на сетке nx 4.

  
# Возвращает количество способов размещения 1 х 4 тайлов
# на сетке nx 4.

def count(n):

  

    # Создать таблицу для хранения результатов подзадач

    # dp [i] хранит количество путей для сетки ix 4.

    dp = [0 for _ in range(n+1)]

  

    # Заполните таблицу от d [1] до dp [n]

    for i in range(1,n+1):

  

        # Базовые случаи

        if i <= 3:

            dp[i] = 1

        elif i == 4:

            dp[i] = 2

        else:

            # dp (i-1): разместить первый тайл горизонтально

            # dp (n-4): разместить первую плитку вертикально

            # что означает, что еще 3 плитки имеют

            # быть размещенным вертикально.

            dp[i] = dp[i-1] + dp[i-4]

  

    return dp[n]

  
# Код драйвера для проверки выше

n = 5

print ("Count of ways is"),

print (count(n))

C #

// C # программа для подсчета путей
// разместить 1 х 4 плитки
// сетка nx 4

using System;

  

class GFG

{

      

    // Функция, которая считает число

    // способов размещения 1 х 4 тайлов

    // на сетке nx 4.

    static int count(int n)

    {

          

        // Создать таблицу для хранения результатов

        // подзадач магазинов dp [i]

        // количество путей для сетки ix 4.

        int[] dp = new int[n + 1];

        dp[0] = 0;

          

        // Заполняем таблицу из d [1]

        // в дп [п]

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

        {

              

            // Базовые случаи

            if (i >= 1 && i <= 3)

                dp[i] = 1;

            else if (i == 4)

                dp[i] = 2 ;

  

            else

            {

                  

                // dp (i-1): разместить первую плитку

                // горизонтально dp (i-4):

                // Поместить первую плитку вертикально

                // что означает, что еще 3 плитки имеют

                // для вертикального размещения.

                dp[i] = dp[i - 1] + 

                        dp[i - 4];

            }

        }

        return dp[n];

    }

      

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

    public static void Main ()

    {

        int n = 5;

        Console.WriteLine("Count of ways is: "

                           + count(n));

    }

}

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

PHP

<?php
// PHP программа для подсчета путей
// размещаем плитки размером 1 x 4 на сетке nx 4.

  
// Возвращает количество путей
// разместить 1 х 4 плитки
// на сетке nx 4.

function countt($n)

{

      

    // Создать таблицу для хранения

    // результаты подзадач

    // dp [i] хранит количество

    // пути для сетки ix 4.

    $dp[$n + 1] = 0;

    $dp[0] = 0;

  

    // Заполнить таблицу

    // от d [1] до dp [n]

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

    {

          

        // Базовые случаи

        if ($i >= 1 && $i <= 3)

            $dp[$i] = 1;

        else if ($i == 4)

            $dp[$i] = 2 ;

  

        else

            // dp (i-1): разместить первую плитку горизонтально

            // dp (n-4): Поместить первую плитку вертикально

            // что означает, что еще 3 плитки имеют

            // для вертикального размещения.

            $dp[$i] = $dp[$i - 1] + $dp[$i - 4];

    }

  

    return $dp[$n];

}

  

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

    $n = 5;

    echo "Count of ways is " , countt($n);

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

Выход :

Count of ways is 3

Сложность времени: O (n)
Вспомогательное пространство: O (n)

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

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

Подсчитайте количество способов заполнить сетку «nx 4», используя плитки «1 x 4»

0.00 (0%) 0 votes