d038 - 00900 - Brick Wall Patterns

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定長度 n 的磚牆有多少種不同的花樣。磚牆的高度固定為 2，磚塊可以水平或垂直放置。問題等價於計算長度為 n 的序列有多少種由 1 和 2 組成的組合，其中 1 代表垂直放置的磚塊，2 代表水平放置的兩個磚塊。

解題思路

這道題目可以被視為一個費氏數列的應用。因為長度為 n 的牆的花樣數量等於長度為 n-1 的牆的花樣數量（在末尾添加一個垂直磚塊）加上長度為 n-2 的牆的花樣數量（在末尾添加兩個水平磚塊）。因此，可以使用迭代的方式計算費氏數列來解決這個問題。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>

using namespace std;

int main (){
	
	
	int n=0;
	long long int m=1,w=2,e=0;
	while(cin >> n){
		
		if(n==1){
			e=1;
		}
		else if(n==2){
			e=2;
		}
		while(n>2){
			e=m+w;
			m=w;
			w=e;
			n--;
		}
	if(e>0){
		cout << e << endl;
	}
	m=1;w=2;e=0;
	}
	
}