利用卷积计算两个数的乘积.txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

利用卷积计算两个数的乘积[原创] 
设a=999，b=999，把两个数看作是由0、1、2、3、4、5、6、7、8、9组成的序列，则两个数相乘可以看作是一种卷积运算。如a*b=998001。而序列卷积结果为81、162、243、162、81，把这些数分别看作乘积结果的万位、千位、百位、十位、个位数，然后做运算（当前数和进位之和对10的余数即为当前位最终结果，对10的商为对前一位的进位），处理后得998001，即两数相乘最终结果。

代码如下，简单模拟：

＃i nclude <conio.h>
＃i nclude <stdlib.h>

void juanji(int x[],int y[],int z[],int n,int m)
{
  int i,j;
  for(i=0;i<=n+m;i++)
  {
     int t=0;
     for(j=0;j<=n;j++)
       if(i-j>=0&&i-j<=m)
              t+=x[j]*y[i-j];
     z[i]=t;
  }
}

void output(int array[],int n)
{
  int i;
  for(i=0;i<=n;i++)
    printf("%4d",array[i]);
  printf("\n\n");
}

void chuli(int array[],int result[],int n)
{
   int i,c=0;
   for(i=n-1;i>=0;i--)
   {
      result[i+1]=(array[i]+c)%10;
      c=(array[i]+c)/10;
   }
   result[0]=c;
}

void main()
{
  int x[3]={9,9,9},y[3]={9,9,9},z[5]={0},result[6];
  int i;
  juanji(x,y,z,2,2);
  chuli(z,result,5);
  output(x,2);
  output(y,2);
  printf("\nThe product is:\n");
  for(i=0;i<6;i++)
    printf("%d",result[i]);
}

 

有兴趣的朋友请参考我以前写过的一个计算两数相乘的代码：

user1/20989/archives/2005/256643.shtml