计算建造建筑物的可能方法-yiteyi-C++库

给定输入的路段数量，每个路段在道路两侧各有2个地块。找到所有可能的方法在地块上建造建筑物，使任意两栋建筑物之间有一个空间。

null

例子：

N = 1Output = 4Place a building on one side.Place a building on other sideDo not place any building.Place a building on both sides.N = 3 Output = 253 sections, which means possible ways for one side are BSS, BSB, SSS, SBS, SSB where B represents a building and S represents an empty spaceTotal 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

我们强烈建议您尽量减少浏览器，并先自己尝试 我们可以把问题简化为只计算一面。如果我们知道一边的结果，我们总是可以做结果的平方，得到两边的结果。

新建筑可以放置在一个截面上，如果该截面正好在它有空间之前。空间可以放在任何地方（不管前一部分是否有建筑）。

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)

下面是上述想法的实施。

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

输出：

Count of ways for 3 sections is 25

时间复杂度：O（N）辅助空间：O（1）算法范式：动态规划

另一种思考方式： （一方面是因为另一方面是一样的）

让我们把建筑看作是一系列的 N （因为两边都有N个图） 长度二进制字符串 （每个数字为0或1），其中：

1 => Represents building has been made on the ith plot0 => Represents building has not been made on the ith plot

现在问题是，我们必须找到很多方法，使得我们的地块上没有连续的建筑，在二进制字符串中，它可以被解释为， 我们需要找到一些方法，使二进制字符串中没有连续的1（1表示正在建造的建筑）

例子：

N = 3 Total Combinations = 2ⁿ = 2³= 8This will contain some combination in there will be consecutive building, so we have to reject that000 (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

所以现在我们的问题是找到表示N个长度的二进制字符串，使其不具有连续1的方法的数量这是一个相当标准的问题

优化解决方案： 请注意，上述解决方案可以进一步优化。如果我们仔细观察结果，对于不同的值，我们可以注意到两边的结果是平方斐波那契数 . N=1，结果=4[一侧的结果=2] N=2，结果=9[一侧的结果=3] N=3，结果=25[一侧的结果=5] N=4，结果=64[一侧的结果=8] N=5，结果=169[一侧的结果=13] ……………………. ……………………. 一般来说，我们可以说

  result(N) = fib(N+2)²    fib(N) is a function that returns N'th          Fibonacci Number.

因此，我们可以使用斐波那契数的O（LogN）实现找到O（logN）时间内的方法数。本文由 戈皮纳特 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章