發表新討論
#18962: 加速方法


CSE210617 (A_A)

學校 : 國立臺中高級工業職業學校
編號 : 38161
來源 : [122.116.151.243]
最後登入時間 ：
2020-03-24 10:55:48
d255. 11417 - GCD -- UVa11417 | From: [101.137.24.47] | 發表日期 : 2019-08-18 15:08

用題目提供的雙層迴圈runtime 大概0.3s(C, C++)

 

要加速的話，可以思考看看G(n) 與G(n-1)之間的差異，那就可以用遞迴去解，再另外用一個table去存已知的答案即可

 

int G(int n){
if(table[n]) return table[n];

int ans = G(n-1);
for(){
//計算該層答案...
}
table[n] = ans;
return ans;
}
 
結構大概是這樣，記得建表要初始化為0，另外在初始化一個table[2]的值(G(2) )，如果沒用
 
#18963: Re:加速方法


CSE210617 (A_A)

學校 : 國立臺中高級工業職業學校
編號 : 38161
來源 : [122.116.151.243]
最後登入時間 ：
2020-03-24 10:55:48
d255. 11417 - GCD -- UVa11417 | From: [101.137.24.47] | 發表日期 : 2019-08-18 15:14

用題目提供的雙層迴圈runtime 大概0.3s(C, C++)

 

要加速的話，可以思考看看G(n) 與G(n-1)之間的差異，那就可以用遞迴去解，再另外用一個table去存已知的答案即可

 

int G(int n){
if(table[n]) return table[n];

int ans = G(n-1);
for(){
//計算該層答案...
}
table[n] = ans;
return ans;
}
 
結構大概是這樣，記得建表要初始化為0，另外在初始化一個table[2]的值(G(2) )，如果沒用



結構大概是這樣，記得建表要初始化為0，另外在初始化一個table[2]的值(G(2) )，不然就是要再多加判斷式。

 

這樣的做法實測可以達到7ms~

 
ZeroJudge Forum