计算建造建筑物的可能方式
dynamic programmingalgorithmsdata structure
这里给出了 n 个路段，每个路段中，道路上有两边可以建造建筑物。如果两栋房子之间需要有一个空地，那么在该地块中有多少种建造建筑物的可能方式。
建造建筑物有四种可能
- 道路的一侧
- 道路的另一侧
- 无法建造任何建筑物
- 道路的两侧
输入和输出
输入: 建造建筑物需要路段数。假设输入为 3。 输出: 输入路段数:3 建筑物可以用 25 种不同的方式建造。
算法
constructionWays(n)
输入: 有 n 个部分。
输出 − 可能的方法数。
开始 如果 n = 1，则 返回 4 countEnd := 1 countEndSpace := 1 对于 i := 2 到 n，执行 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) //如果有一个部分
return 4; //在该部分建造建筑物的 4 种可能方法
//设置末尾位置的计数值并以空间结尾
int countEnd=1, countEndSpace=1, prevCountEnd, prevCountEndSpace;
for (int i=2; i<=n; i++) { //从第二部分到第 n 部分
prevCountEnd = countEnd;
prevCountEndSpace = countEndSpace;
countEndSpace = countEnd + prevCountEndSpace;
countEnd = prevCountEndSpace;
}
//可能以空间结尾并在末尾建造建筑物的方式
int answer = countEndSpace + countEnd;
return (answer*answer); //对于两边，答案将是平方
}
int main() {
int n;
cout << "输入部分数:";
cin >> n;
cout << "建筑物可以用<<< constructionWays(n) <<" 多种不同方式建造。" ;
}
输出
输入部分数:3 建筑物可以用 25 种不同的方式建造。
