Re: [問題] 二維動態陣列 free會錯誤
看板C_and_CPP (C/C++)作者dj533kevin (很久沒唬爛了)時間16年前 (2009/10/22 13:09)推噓2(2推 0噓 0→)留言2則, 2人參與討論串2/2 (看更多)
: 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
推
10/22 13:11, , 1F
10/22 13:11, 1F
感謝，改寫後變這樣
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)
推
10/22 13:47, , 2F
10/22 13:47, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章