c874 - 107北二1.雪花片片
題目描述
題目要求計算 Koch 曲線從 N=1 到 N 的等邊三角形總數量。Koch 曲線的三角形數量呈現指數增長，N=1 時有 1 個三角形，N=2 時有 4 個，N=3 時有 16 個，以此類推。
解題思路
題目中，N=1 時三角形數量為 1，N=2 時為 1+4=5，N=3 時為 1+4+16=21。可以觀察到，第 i 個 Koch 曲線的三角形數量為 4^(i-1)。因此，從 1 到 N 的總數量可以表示為一個等比級數的和：1 + 4 + 16 + ... + 4^(N-1)。
程式碼中，a[i] 儲存 4^(i-1) 的值，b[i] 儲存從 1 到 i 的三角形總數。程式先預先計算 a 和 b 陣列，然後根據輸入的 N 輸出 b[N-1]。
程式使用字串來表示大數，並使用 add 函數來進行大數加法。
複雜度分析
- 時間複雜度: O(N) (預計算陣列需要 O(N) 時間，查詢則為 O(1))
- 空間複雜度: O(N) (儲存
a和b陣列)
程式碼
#include <iostream>
#include <string>
using namespace std;
string a[121]={"1"},b[121]={"1"};
inline string add(string x,string y){
int xl=x.length(),yl=y.length();
bool add=0;
for(int i=xl-1,j=yl-1;i>=0;--i,--j){
y[j]+=x[i]-48;
if(y[j]>'9'){
y[j]-=10;
if(j==0)
add=1;
else
++y[j-1];
}
}
if(add)
y='1'+y;
return y;
}
int main(){
for(int i=0;i<120;++i){
a[i+1]=add(a[i],a[i]);
a[i+1]=add(a[i+1],a[i+1]);
b[i+1]=add(b[i],a[i+1]);
}
int n;
while(cin >> n)
cout << b[n-1] << "\n";
}