นับวิธีที่เป็นไปได้ในการสร้างอาคาร

ต่อไปนี้คือจำนวนส่วน 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 different ways.

อัลกอริทึม

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

   //set counting values for place at the end and end with space
   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;
   }

   //possible ways to end with space and building at the end
   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) <<" different ways." ;
}

ผลลัพธ์

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