作者dj533kevin (很久沒唬爛了)
看板C_and_CPP
標題Re: [問題] 二維動態陣列 free會錯誤
時間Thu Oct 22 13:09:21 2009
: int catalan(void){
: int i,Cn=1,c=1;
: for (i=n+1;i<=2*n;i++){
: Cn=Cn*i;
: c=c*(i-n);
: }
: Cn=Cn/((n+1)*c);
: printf("\nThere are %d sequence in Cn! \n",Cn);
: return Cn;
: }
對不起我自回一下
我想要得到Catalan數列的第n項，但一開始用的碼(如上)，當n很大時
，變數cn就會溢位(應該是它沒錯)
就算我用unsigned int 也沒好多少。
但若我改用遞迴
unsigned int catalan(unsigned int t){
unsigned int i;
unsigned int Cn=0;
if (t>1){
for (i=1;i<=t;i++){
Cn=Cn+catalan(i-1)*catalan(t-i);
}
return Cn;
}else{
return 1;
}
return Cn;
}
似乎不會有溢位，但是當n>15之後，計算時間就很明顯的拉長
請問這程式碼要怎樣改進比較好？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 124.8.155.103
1F：推 ckclark:用個陣列記住 catalan[i] 算過就不用重算 10/22 13:11
感謝，改寫後變這樣
cata[n]是設成全域變數的動態陣列
unsigned int catalan(unsigned int t){
unsigned int i;
unsigned int Cn=0;
if (cata[t]==1){
if (t>1){
for (i=1;i<=t;i++){
Cn=Cn+catalan(i-1)*catalan(t-i);
}
cata[t]=Cn;
return Cn;
}else{
return 1;
}
}else{
return cata[t];
}
return Cn;
}
※ 編輯: dj533kevin 來自: 124.8.155.103 (10/22 13:26)
2F：推 LPH66:順帶一提, Catalan 數是成指數成長, 所以在n=20左右會溢位 10/22 13:47