Dado un piso de tamaño nxm y baldosas de tamaño 1 x m. El problema es contar el número de formas de embaldosar el suelo dado utilizando baldosas de 1 x m. Un azulejo se puede colocar horizontal o verticalmente.
Tanto n como m son números enteros positivos y 2 < = m.
Ejemplos:
Input : n = 2, m = 3 Output : 1 Only one combination to place two tiles of size 1 x 3 horizontally on the floor of size 2 x 3. Input : n = 4, m = 4 Output : 2 1st combination: All tiles are placed horizontally 2nd combination: All tiles are placed vertically.
Este problema es principalmente un enfoque más generalizado del problema del mosaico .
Método: Para un valor dado de n y m, el número de formas de embaldosar el piso se puede obtener de la siguiente relación.
| 1, 1 < = n < m
count(n) = | 2, n = m
| count(n-1) + count(n-m), m < n
C++
// C++ implementation to count number of ways to
// tile a floor of size n x m using 1 x m tiles
#include <bits/stdc++.h>
using namespace std;
// function to count the total number of ways
int countWays(int n, int m)
{
// table to store values
// of subproblems
int count[n + 1];
count[0] = 0;
// Fill the table upto value n
for (int i = 1; i <= n; i++) {
// recurrence relation
if (i > m)
count[i] = count[i - 1] + count[i - m];
// base cases and for i = m = 1
else if (i < m || i == 1)
count[i] = 1;
// i = = m
else
count[i] = 2;
}
// required number of ways
return count[n];
}
// Driver program to test above
int main()
{
int n = 7, m = 4;
cout << "Number of ways = "
<< countWays(n, m);
return 0;
}
Java
// Java implementation to count number
// of ways to tile a floor of size
// n x m using 1 x m tiles
import java.io.*;
class GFG {
// function to count the total number of ways
static int countWays(int n, int m)
{
// table to store values
// of subproblems
int count[] = new int[n + 1];
count[0] = 0;
// Fill the table upto value n
int i;
for (i = 1; i <= n; i++) {
// recurrence relation
if (i > m)
count[i] = count[i - 1] + count[i - m];
// base cases
else if (i < m || i == 1)
count[i] = 1;
// i = = m
else
count[i] = 2;
}
// required number of ways
return count[n];
}
// Driver program
public static void main(String[] args)
{
int n = 7;
int m = 4;
System.out.println("Number of ways = "
+ countWays(n, m));
}
}
// This code is contributed by vt_m.
Python3
# Python implementation to
# count number of ways to
# tile a floor of size n x m
# using 1 x m tiles
def countWays(n, m):
# table to store values
# of subproblems
count =[]
for i in range(n + 2):
count.append(0)
count[0] = 0
# Fill the table upto value n
for i in range(1, n + 1):
# recurrence relation
if (i > m):
count[i] = count[i-1] + count[i-m]
# base cases
elif (i < m or i == 1):
count[i] = 1
# i = = m
else:
count[i] = 2
# required number of ways
return count[n]
# Driver code
n = 7
m = 4
print("Number of ways = ", countWays(n, m))
# This code is contributed
# by Anant Agarwal.
C#
// C# implementation to count number
// of ways to tile a floor of size
// n x m using 1 x m tiles
using System;
class GFG {
// function to count the total
// number of ways
static int countWays(int n, int m)
{
// table to store values
// of subproblems
int[] count = new int[n + 1];
count[0] = 0;
// Fill the table upto value n
int i;
for (i = 1; i <= n; i++) {
// recurrence relation
if (i > m)
count[i] = count[i - 1]
+ count[i - m];
// base cases and i = m = 1
else if (i < m || i == 1)
count[i] = 1;
// i = = m
else
count[i] = 2;
}
// required number of ways
return count[n];
}
// Driver program
public static void Main()
{
int n = 7;
int m = 4;
Console.Write("Number of ways = "
+ countWays(n, m));
}
}
// This code is contributed by parashar.
PHP
<?php
// PHP implementation to count
// number of ways to tile a
// floor of size n x m using
// 1 x m tiles
// function to count the
// total number of ways
function countWays($n, $m)
{
// table to store values
// of subproblems
$count[0] = 0;
// Fill the table
// upto value n
for ($i = 1; $i <= $n; $i++)
{
// recurrence relation
if ($i > $m)
$count[$i] = $count[$i - 1] +
$count[$i - $m];
// base cases
else if ($i < $m or $i == 1)
$count[$i] = 1;
// i = = m
else
$count[$i] = 2;
}
// required number of ways
return $count[$n];
}
// Driver Code
$n = 7;
$m = 4;
echo "Number of ways = ", countWays($n, $m);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript implementation to count number
// of ways to tile a floor of size
// n x m using 1 x m tiles
// function to count the total
// number of ways
function countWays(n, m)
{
// table to store values
// of subproblems
let count = new Array(n + 1);
count[0] = 0;
// Fill the table upto value n
let i;
for (i = 1; i <= n; i++) {
// recurrence relation
if (i > m)
count[i] = count[i - 1] + count[i - m];
// base cases and i = m = 1
else if (i < m || i == 1)
count[i] = 1;
// i = = m
else
count[i] = 2;
}
// required number of ways
return count[n];
}
let n = 7;
let m = 4;
document.write("Number of ways = " + countWays(n, m));
// This code is contributed by rameshtravel07.
</script>
Producción:
Number of ways = 5
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA