如何加快函数“递归调用”的速度???
这是一个递归调用的例子,怎么样能使调用更快?请高手们多多指导!
#include<math.h>
#include<string.h>
#include<stdio.h>
age(int n)
{int c;
if(n==1) c=122020;
else c=age(n-1)+2;
return(c);
}
void main()
{
printf("%d\n",age(154962));
}
----------------解决方案--------------------------------------------------------
改递归为迭代,这里直接改成乘法算了
int age(int n){return 122018+n*2;}
----------------解决方案--------------------------------------------------------
对了,楼主的程序可以运行吗?我在VC2005上面运行都栈溢出呢……154962这数字的确大了点……上面的程序可能会溢出,建议改成long long 或者unsigned long long……
----------------解决方案--------------------------------------------------------
本人愚笨 没明白您的意思
还请详细说明!
----------------解决方案--------------------------------------------------------
具体的数字不是主要的,关键是如何加快速度,我把数字便小一点!
#include<math.h>
#include<string.h>
#include<stdio.h>
age(int n)
{int c;
if(n==1) c=1220;
else c=age(n-1)+2;
return(c);
}
void main()
{
printf("%d\n",age(1549);
}
----------------解决方案--------------------------------------------------------
就是说,把递归变成循环,省掉递归的过程。比如你的程序,变成迭代就是
int age(int n){
int i,sum=120;
for(int i=0;i<n-1;i++)
sum+=2;
return sum;
}
注意到其实就是个循环相加的过程,可以用相乘来实现,就可以写成乘法
sum=120+(n-1)*2;
化简得
sum=118+n*2;
其实还可以进一步优化。移位通常比乘法快。
sum=118+(n<<1);
就是这么优化的。
----------------解决方案--------------------------------------------------------
我有点明白了!
StarWing83 说的非常好! 感谢您的帮助!
----------------解决方案--------------------------------------------------------
请帮忙再看一下这个程序如何简化!
StarWing83 说的非常好!您的上个程序我已经理解了,能在把以下这个程序便一下吗?
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 18
//计算原矩阵的行列式 |A|
double nm(double s[N][N],double n)
{
int z,j,k;
double r;
double total=0;
double b[N][N];
if(n>2)
{
for(z=0;z<n;z++)
{
for(j=0;j<n-1;j++)
for(k=0;k<n-1;k++)
if(k>=z) b[j][k]=s[j+1][k+1];
else b[j][k]=s[j+1][k];
if(z%2==0) r=s[0][z]*nm(b,n-1);
else r=(-1)*s[0][z]*nm(b,n-1);
total=total+r;
}
}
else if(n==2) total=s[0][0]*s[1][1]-s[0][1]*s[1][0];
return total;
}
void main()
{
double r;
int z,j;
double A[N][N]={216.080575,64.334189,81.390948,18.961460,68.975034,27.294921,51.867969,45.292775,35.914893,7.521622,281.840523,85.170013,113.368330,43.404363,};
r=nm(A,N);
printf("\nThe is:r== %f \n",r);
}
----------------解决方案--------------------------------------------------------
具体的数字不是关键
A[N][N]数组里具体的数字不是大事!关键是怎么改进这个调用函数! ----------------解决方案--------------------------------------------------------
程序代码:
double Surplus(double A[],int m,int n) { /*求矩阵行列式*/
int i,j,k,p,r;
double X,temp=1,temp1=1,s=0,s1=0;
if (n==2) {
for (i=0;i<m;i++)
for (j=0;j<n;j++)
if ((i+j)%2) temp1*=A[i*n+j];
else temp*=A[i*n+j];
X=temp-temp1;
} else {
for (k=0;k<n;k++) {
for (i=0,j=k;i<m,j<n;i++,j++)
temp*=A[i*n+j];
if (m-i) {
for (p=m-i,r=m-1;p>0;p--,r--)
temp*=A[r*n+p-1];
}
s+=temp;
temp=1;
}
for (k=n-1;k>=0;k--) {
for (i=0,j=k;i<m,j>=0;i++,j--)
temp1*=A[i*n+j];
if (m-i) {
for (p=m-1,r=i;r<m;p--,r++)
temp1*=A[r*n+p];
}
s1+=temp1;
temp1=1;
}
X=s-s1;
}
return X;
}
网上找的行列式算法,人家的是O(n2)的,你的是O(n3)的,估计会快一点点……其实我也不懂…… int i,j,k,p,r;
double X,temp=1,temp1=1,s=0,s1=0;
if (n==2) {
for (i=0;i<m;i++)
for (j=0;j<n;j++)
if ((i+j)%2) temp1*=A[i*n+j];
else temp*=A[i*n+j];
X=temp-temp1;
} else {
for (k=0;k<n;k++) {
for (i=0,j=k;i<m,j<n;i++,j++)
temp*=A[i*n+j];
if (m-i) {
for (p=m-i,r=m-1;p>0;p--,r--)
temp*=A[r*n+p-1];
}
s+=temp;
temp=1;
}
for (k=n-1;k>=0;k--) {
for (i=0,j=k;i<m,j>=0;i++,j--)
temp1*=A[i*n+j];
if (m-i) {
for (p=m-1,r=i;r<m;p--,r++)
temp1*=A[r*n+p];
}
s1+=temp1;
temp1=1;
}
X=s-s1;
}
return X;
}
----------------解决方案--------------------------------------------------------