건물을 건설할 수 있는 가능한 방법 계산

여기에는 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.