Đếm số cách xây dựng nhà có thể

Ở đây có n khu vực (sections) được cho, ở mỗi khu vực, có hai bên đường để xây dựng nhà. Nếu cần một khoảng trống giữa hai ngôi nhà, thì có bao nhiêu cách có thể để xây dựng nhà trên đất đó.

Có bốn khả năng để xây dựng nhà:

• Một bên đường
• Bên kia của đường
• Không xây nhà nào
• Cả hai bên đường

Đầu vào và Đầu ra

Đầu vào: Nhận số khu vực để xây dựng nhà. Giả sử đầu vào là 3.
Đầu ra: Enter Number of sections: 3
Buildings can be constructed in 25 different ways.

Thuật toán

constructionWays(n)
Đầu vào: Có n số khu vực.
Đầu ra: Số cách có thể.
Bắt đầu
  nếu n = 1 thì
    trả về 4
  countEnd := 1
  countEndSpace := 1
  với i := 2 đến n, làm
    prevCountEnd := countEnd
    prevCountEndSpace := countEndSpace
    countEndSpace := countEnd + prevCountEndSpace
    countEnd := prevCountEndSpace
  kết thúc
  answer := countEndSpace + countEnd
  trả về answer^2
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

int constructionWays(int n) {
  if (n == 1)
    // nếu chỉ có một khu vực
    return 4; // 4 cách có thể để xây nhà trong khu vực đó
  
  // đặt giá trị đếm cho nơi kết thúc bằng nhà và kết thúc bằng khoảng trống
  int countEnd = 1, countEndSpace = 1, prevCountEnd, prevCountEndSpace;
  
  for (int i = 2; i <= n; i++) {
    // cho khu vực thứ hai đến khu vực thứ n
    prevCountEnd = countEnd;
    prevCountEndSpace = countEndSpace;
    countEndSpace = countEnd + prevCountEndSpace;
    countEnd = prevCountEndSpace;
  }
  
  // các cách có thể kết thúc bằng khoảng trống và kết thúc bằng nhà
  int answer = countEndSpace + countEnd;
  return (answer * answer); // cho hai bên đường, kết quả sẽ bình phương
}

int main() {
  int n;
  cout << "Enter Number of sections: "; cin >> n;
  cout << "Buildings can be constructed in " << constructionWays(n) << " different ways.";
}

Đầu ra

Enter Number of sections: 3
Buildings can be constructed in 25 different ways.