b810 - 九○七四二的問題之(二)
題目描述
題目要求模擬一個數字金字塔的生成過程。金字塔的頂層有 y 個數字，從 1 到 y 依次填充。後續每一層都由上一層的相鄰數字相加得到，層數減少 1，直到只剩一個數字。輸出最終的數字。由於數字可能非常大，需要使用大數運算。
解題思路
這題的核心在於模擬金字塔的生成過程，並處理大數相加。程式碼使用字串來表示大數，並實現了一個大數相加的函數 add。主函數中，程式碼模擬了金字塔的生成過程，每次將上一層的相鄰數字相加，直到只剩一個數字。這個過程可以看作是一個貪心演算法，每次都將相鄰的數字相加。雖然題目描述中提到可能有公式解，但程式碼採用了模擬的方法。
複雜度分析
- 時間複雜度: O(n * m^2)，其中 n 是輸入的整數 y，m 是字串的長度。每次相加操作的時間複雜度是 O(m^2)，而相加操作的次數與 n 成正比。
- 空間複雜度: O(m)，其中 m 是字串的長度。空間複雜度主要用於儲存大數字串。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
string x="1",y="1",ba="1";
int n;
string add(string a,string b){
int tmp[701]={0},al=a.length(),bl=b.length();
string c;
for(int i=0;i<al;++i)tmp[al-i-1]+=a[i]-48;
for(int i=0;i<bl;++i)tmp[bl-i-1]+=b[i]-48;
for(int i=0;i<bl+1;++i){
if(tmp[i]>9){
++tmp[i+1];
tmp[i]-=10;
}
}
for(int i=al+1;i>=0;--i)
if(tmp[i]){
al=i;
break;
}
for(int i=al;i>=0;--i)c+=tmp[i]+'0';
return c;
}
string tos(int v){
string a;
while(v){
a+=v%10+'0';
v/=10;
}
reverse(a.begin(),a.end());
return a;
}
int main(){
cin >> n;
while(n-->1){
y=add(x,ba);
ba=add(ba,ba);
x=add(x,y);
}
cout << x;
}