建物を建設するための可能な方法を数える

ここでは、n個のセクションが示されています。各セクションには、建物を建設するための2つの側面があります。 2つの家の間に1つの空きスペースが必要な場合、プロット内に建物を構築するための可能な方法はいくつありますか。

建物を建てるには4つの可能性があります

• 道路の片側
• 道路の反対側
• 建物は建設できません
• 道路の両側

入力と出力

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.