我试图通过递归调用实现Karatsuba乘法。下面的代码应该工作,但我一直得到零作为答案。任何想法吗?
#define ll long long int
ll kmul(ll p, ll q)
{
ll a,b,c,d,ans;
ll n=0;
while(p)
{
p=p/10;
n++;
}
//cout<<n<<endl;
if(n<2)
{
return p*q;
}
else
{
int k=n/2;
ll j=pow(10,k);
a=p/j;
b=p%j;
c=q/(j);
b=q%j;
ans=(pow(10,n)*(kmul(a,c)))+(j*kmul(a,d)*kmul(b,c))+kmul(b,d);
return ans;
}
}
循环结束后:
while(p)
{
p=p/10;
n++;
}
p
的值为0。递归在
if(n<2)
{
return p*q;
}
因此,无论输入是什么,结果都是0。
您可能需要使用p
的副本来计算while
循环中的n
。这样就可以保留p的值。例如:
ll pd = p;
while(pd)
{
pd=pd/10;
n++;
}