计算建造建筑物的可能方法

这里给出n个路段，每个路段在建造建筑物的过程中有两个侧面。如果需要在两栋房屋之间留出一个空的空间，那么有多少种方法可以在地块中建造建筑物。

建造建筑物有四种可能性

•  路的一侧

•  路的另一边

•  不能建造建筑物

•  道路两边

输入输出

Input:
It takes the number of sections to construct buildings. Say the input is 3.
Output:
Enter Number of sections: 3
Buildings can be constructed in 25 不同的方法。

算法

constructionWays(n)

输入：有n个部分。

输出-可能的方法数量。

Begin
   if n = 1, then
      return 4
   countEnd := 1
   countEndSpace := 1

   for i := 2 to n, do
      prevCountEnd := countEnd
      prevCountEndSpace := countEndSpace
      countEndSpace := countEnd + prevCountEndSpace
      countEnd := prevCountEndSpace
   done

   answer := countEndSpace + countEnd
   return answer^2
End

示例

#include<iostream>
using namespace std;

int constructionWays(int n) {
   if (n == 1)        //if there is one section
      return 4;       //4 possible ways to construct building in that section

   //设置末端的计数值，并以空格结尾
   int countEnd=1, countEndSpace=1, prevCountEnd, prevCountEndSpace;

   for (int i=2; i<=n; i++) {       //fot the second section to nth section
      prevCountEnd = countEnd;
      prevCountEndSpace = countEndSpace;

      countEndSpace = countEnd + prevCountEndSpace;
      countEnd = prevCountEndSpace;
   }

   //以空间和建筑结尾的可能方法
   int answer = countEndSpace + countEnd;

   return (answer*answer);     //for two sides the answer will be squared
}

int main() {
   int n;
   cout << "Enter Number of sections: ";
   cin >> n;
   cout << "Buildings can be constructed in " << constructionWays(n) <<" 不同的方法。" ;
}

输出结果

Enter Number of sections: 3
Buildings can be constructed in 25 不同的方法。