Dado un número de entrada de secciones y cada sección tiene 2 parcelas a ambos lados de la carretera. Encuentre todas las formas posibles de construir edificios en las parcelas de modo que haya un espacio entre 2 edificios cualesquiera.
Ejemplo :
N = 1 Output = 4 Place a building on one side. Place a building on other side Do not place any building. Place a building on both sides. N = 3 Output = 25 3 sections, which means possible ways for one side are BSS, BSB, SSS, SBS, SSB where B represents a building and S represents an empty space Total possible ways are 25, because a way to place on one side can correspond to any of 5 ways on other side. N = 4 Output = 64
https://practice.geeksforgeeks.org/problems/count-possible-ways-to-construct-buildings5007/1
Recomendamos enfáticamente minimizar su navegador y probarlo usted mismo primero.
Podemos simplificar el problema para calcular primero solo para un lado. Si conocemos el resultado de un lado, siempre podemos hacer el cuadrado del resultado y obtener el resultado de dos lados.
Se puede colocar un nuevo edificio en una sección si la sección justo antes de que tenga espacio. Un espacio se puede colocar en cualquier lugar (no importa si la sección anterior tiene un edificio o no).
Let countB(i) be count of possible ways with i sections
ending with a building.
countS(i) be count of possible ways with i sections
ending with a space.
// A space can be added after a building or after a space.
countS(N) = countB(N-1) + countS(N-1)
// A building can only be added after a space.
countB[N] = countS(N-1)
// Result for one side is sum of the above two counts.
result1(N) = countS(N) + countB(N)
// Result for two sides is square of result1(N)
result2(N) = result1(N) * result1(N)
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to count all possible way to construct buildings
#include<iostream>
using namespace std;
// Returns count of possible ways for N sections
int countWays(int N)
{
// Base case
if (N == 1)
return 4; // 2 for one side and 4 for two sides
// countB is count of ways with a building at the end
// countS is count of ways with a space at the end
// prev_countB and prev_countS are previous values of
// countB and countS respectively.
// Initialize countB and countS for one side
int countB=1, countS=1, prev_countB, prev_countS;
// Use the above recursive formula for calculating
// countB and countS using previous values
for (int i=2; i<=N; i++)
{
prev_countB = countB;
prev_countS = countS;
countS = prev_countB + prev_countS;
countB = prev_countS;
}
// Result for one side is sum of ways ending with building
// and ending with space
int result = countS + countB;
// Result for 2 sides is square of result for one side
return (result*result);
}
// Driver program
int main()
{
int N = 3;
cout << "Count of ways for " << N
<< " sections is " << countWays(N);
return 0;
}
Java
class Building
{
// Returns count of possible ways for N sections
static int countWays(int N)
{
// Base case
if (N == 1)
return 4; // 2 for one side and 4 for two sides
// countB is count of ways with a building at the end
// countS is count of ways with a space at the end
// prev_countB and prev_countS are previous values of
// countB and countS respectively.
// Initialize countB and countS for one side
int countB=1, countS=1, prev_countB, prev_countS;
// Use the above recursive formula for calculating
// countB and countS using previous values
for (int i=2; i<=N; i++)
{
prev_countB = countB;
prev_countS = countS;
countS = prev_countB + prev_countS;
countB = prev_countS;
}
// Result for one side is sum of ways ending with building
// and ending with space
int result = countS + countB;
// Result for 2 sides is square of result for one side
return (result*result);
}
public static void main(String args[])
{
int N = 3;
System.out.println("Count of ways for "+ N+" sections is "
+countWays(N));
}
}/* This code is contributed by Rajat Mishra */
Python3
# Python 3 program to count all possible
# way to construct buildings
# Returns count of possible ways
# for N sections
def countWays(N) :
# Base case
if (N == 1) :
# 2 for one side and 4
# for two sides
return 4
# countB is count of ways with a
# building at the end
# countS is count of ways with a
# space at the end
# prev_countB and prev_countS are
# previous values of
# countB and countS respectively.
# Initialize countB and countS
# for one side
countB=1
countS=1
# Use the above recursive formula
# for calculating
# countB and countS using previous values
for i in range(2,N+1) :
prev_countB = countB
prev_countS = countS
countS = prev_countB + prev_countS
countB = prev_countS
# Result for one side is sum of ways
# ending with building
# and ending with space
result = countS + countB
# Result for 2 sides is square of
# result for one side
return (result*result)
# Driver program
if __name__ == "__main__":
N = 3
print ("Count of ways for ", N
," sections is " ,countWays(N))
# This code is contributed by
# ChitraNayal
C#
// C# program to count all
// possible way to construct
// buildings
using System;
class GFG
{
// Returns count of possible
// ways for N sections
static int countWays(int N)
{
// Base case
if (N == 1)
// 2 for one side and
// 4 for two sides
return 4;
// countB is count of ways
// with a building at the
// end, countS is count of
// ways with a space at the
// end, prev_countB and
// prev_countS are previous
// values of countB and countS
// respectively.
// Initialize countB and
// countS for one side
int countB = 1, countS = 1,
prev_countB, prev_countS;
// Use the above recursive
// formula for calculating
// countB and countS using
// previous values
for (int i = 2; i <= N; i++)
{
prev_countB = countB;
prev_countS = countS;
countS = prev_countB +
prev_countS;
countB = prev_countS;
}
// Result for one side is sum
// of ways ending with building
// and ending with space
int result = countS + countB;
// Result for 2 sides is
// square of result for
// one side
return (result * result);
}
// Driver Code
public static void Main()
{
int N = 3;
Console.Write(countWays(N));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to count all possible
// way to construct buildings
// Returns count of possible
// ways for N sections
function countWays( $N)
{
// Base case
if ($N == 1)
// 2 for one side and
// 4 for two sides
return 4;
// countB is count of ways
// with a building at the end
// countS is count of ways
// with a space at the end
// prev_countB and prev_countS
// are previous values of
// countB and countS respectively.
// Initialize countB and
// countS for one side
$countB = 1; $countS = 1;
$prev_countB; $prev_countS;
// Use the above recursive
// formula for calculating
// countB and countS using
// previous values
for ($i = 2; $i <= $N; $i++)
{
$prev_countB = $countB;
$prev_countS = $countS;
$countS = $prev_countB +
$prev_countS;
$countB = $prev_countS;
}
// Result for one side is
// sum of ways ending with
// building and ending with
// space
$result = $countS + $countB;
// Result for 2 sides is square
// of result for one side
return ($result*$result);
}
// Driver Code
$N = 3;
echo "Count of ways for " , $N
, " sections is " , countWays($N);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to count all
// possible way to construct buildings
// Returns count of possible ways for N sections
function countWays(N)
{
// Base case
if (N == 1)
// 2 for one side and
// 4 for two sides
return 4;
// countB is count of ways with a building at the end
// countS is count of ways with a space at the end
// prev_countB and prev_countS are previous values of
// countB and countS respectively.
// Initialize countB and countS for one side
let countB = 1, countS = 1, prev_countB, prev_countS;
// Use the above recursive formula for calculating
// countB and countS using previous values
for(let i = 2; i <= N; i++)
{
prev_countB = countB;
prev_countS = countS;
countS = prev_countB + prev_countS;
countB = prev_countS;
}
// Result for one side is sum of
// ways ending with building
// and ending with space
let result = countS + countB;
// Result for 2 sides is square
// of result for one side
return (result*result);
}
// Driver code
N = 3;
document.write("Count of ways for " + N +
" sections is " + countWays(N));
// This code is contributed by avanitrachhadiya2155
</script>
Count of ways for 3 sections is 25
Producción :
Count of ways for 3 sections is 25
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Paradigma algorítmico: Programación dinámica
Otra Forma de Pensar: (de un lado solo porque para el otro lado será igual)
Pensemos en los edificios como la secuencia de N (porque hay N parcelas en cada lado) string binaria de longitud (cada dígito 0 o 1) donde:
1 => Represents building has been made on the ith plot 0 => Represents building has not been made on the ith plot
Ahora, como dice el problema, tenemos que encontrar el número de formas en que no tenemos edificios consecutivos en las parcelas, en la string binaria, se puede interpretar como que necesitamos encontrar el número de formas en que no tenemos 1 consecutivo en la string binaria (ya que 1 representaba un edificio en construcción)
Ejemplo :
N = 3 Total Combinations = 2n = 23 = 8 This will contain some combination in there will be consecutive building, so we have to reject that 000 (No building) (Possible) 001 (Building on 3rd plot) (Possible) 010 (Building on 2nd plot) (Possible) 011 (Building on 2nd and 3rd plot) (Not Possible as there are consecutive buildings) 100 (Building on 1st plot) (Possible) 101 (Building on 1st and 3rd plot) (Possible) 110 (Building on 1st and 2nd plot) (Not Possible as there are consecutive buildings) 111 (Building on 1st, 2nd, 3rd plot) (Not Possible as there are consecutive buildings) Total Possible Ways = 5 These are only on one side, on other side it will also be same as there are N plots and same condition, so Answer = Total Possible Ways * Total Possible Ways = 25
Así que ahora nuestro problema se reduce a encontrar el número de formas de representar una string binaria de longitud N tal que no tenga un 1 consecutivo, que es un problema bastante estándar.
Solución optimizada:
tenga en cuenta que la solución anterior se puede optimizar aún más. Si observamos más de cerca los resultados, para diferentes valores, podemos notar que los resultados para los dos lados son cuadrados de Números de Fibonacci .
N = 1, resultado = 4 [resultado para un lado = 2]
N = 2, resultado = 9 [resultado para un lado = 3]
N = 3, resultado = 25 [resultado para un lado = 5]
N = 4, resultado = 64 [resultado para un lado = 8]
N = 5, resultado = 169 [resultado para un lado = 13]
…………………….
…………………….
En general, podemos decir
result(N) = fib(N+2)2 fib(N) is a function that returns N'th Fibonacci Number.
Por lo tanto, podemos usar la implementación O(LogN) de los números de Fibonacci para encontrar el número de formas en el tiempo O(logN).
Este artículo es una contribución de GOPINATH . 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