นับวิธีก่อสร้างอาคาร (Count Ways to Construct Buildings)

มี n ส่วน (Section) แต่ละส่วนมี 2 ด้านถนน สร้างอาคารได้ แต่ต้องมีที่ว่างอย่างน้อย 1 ช่องระหว่างอาคาร ต้องการหาจำนวนวิธีก่อสร้างที่เป็นไปได้

แต่ละส่วนมี 4 รูปแบบ: สร้างด้านซ้าย, สร้างด้านขวา, ไม่สร้าง, สร้างทั้งสองด้าน

การรับค่าและแสดงผล

Input: จำนวนส่วน = 3
Output: Buildings can be constructed in 25 different ways.

อัลกอริทึม

constructionWays(n)

Begin
  if n = 1 then return 4
  
  countEnd := 1      // จบด้วยอาคาร
  countEndSpace := 1 // จบด้วยที่ว่าง
  
  for i := 2 ถึง n do
    prevCountEnd := countEnd
    prevCountEndSpace := countEndSpace
    countEndSpace := countEnd + prevCountEndSpace
    countEnd := prevCountEndSpace
  done
  
  answer := countEndSpace + countEnd
  return answer^2  // ยกกำลัง 2 เพราะมี 2 ด้านถนน
End

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int constructionWays(int n) {
  if (n == 1) return 4;
  
  int countEnd = 1, countEndSpace = 1;
  int prevCountEnd, prevCountEndSpace;
  
  for (int i = 2; i <= n; i++) {
    prevCountEnd = countEnd;
    prevCountEndSpace = countEndSpace;
    countEndSpace = countEnd + prevCountEndSpace;
    countEnd = prevCountEndSpace;
  }
  
  int answer = countEndSpace + countEnd;
  return (answer * answer);
}

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

ผลลัพธ์

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