作者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