下载文档原格式
![计算机算法设计与分析(第4版)[王晓东][电子教案]第2章](https://img.taocdn.com/s1/m/6ef58047f7ec4afe04a1df38.png)
整数相乘算法整数相乘算法是计算机科学中的一个重要问题，它涉及到了很多领域，比如高精度计算、密码学、图像处理等。
在本文中，我们将介绍几种常见的整数相乘算法，并对它们的时间复杂度和空间复杂度进行分析。
一、暴力枚举法暴力枚举法是最简单直接的一种整数相乘算法。
它的思路很简单：将两个整数的每一位都相乘，再将结果累加起来。
具体实现时，可以使用两个嵌套循环分别遍历两个整数的每一位，然后将它们相乘并累加到结果中。
这种算法的时间复杂度为O(n^2)，其中n为两个整数的位数之和。
二、分治法分治法是一种高效的整数相乘算法。
它的思路是将大问题划分成小问题，并递归地解决小问题。
具体实现时，可以将两个整数分别拆成高位和低位两部分，然后用公式(a1 * 10^n + a2) * (b1 * 10^n + b2)= (a1 * b1) * 10^(2n) + ((a1 + a2) * (b1 + b2) - a1 * b1 - a2 * b2) * 10^n + a2 * b2来计算它们的乘积。
这种算法的时间复杂度为O(n^log3)，其中n为两个整数的位数之和。
三、Karatsuba算法Karatsuba算法是一种优化版的分治法。
它的思路是将两个整数分别拆成三部分，然后用公式(a1 * 10^n + a2) * (b1 * 10^n + b2) = (a1 * b1) * 10^(2n) + ((a1 + a2) * (b1 + b2) - a1 * b1 - a2 * b2) *10^n + a2 * b2来计算它们的乘积。
具体实现时，可以将(a1+a2)*(b1+b2)-a1*b1-a2*b2递归地计算出来，然后再用这个结果计算乘积。
这种算法的时间复杂度为O(n^log23)，其中n为两个整数的位数之和。
四、FFT算法FFT（快速傅里叶变换）算法是一种高效的整数相乘算法。
它利用了傅里叶变换中的性质，将乘积转化成卷积，然后使用快速傅里叶变换来计算卷积。
大整数乘法问题描述通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理，即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。
然而，在某些情况下，我们要处理很大的整数，它无法在计算机硬件能直接表示的范围内进行处理。
若用浮点数来表示它，则只能近似地表示它的大小，计算结果中的有效数字也受到限制。
若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。
请设计一个有效的算法，可以进行两个n位大整数的乘法运算。
参考解答大整数的乘法问题描述参考解答设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。
我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。
如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。
下面我们用分治法来设计一个更有效的大整数乘积算法。
图6-3 大整数X和Y的分段我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如图6-3所示。
由此，X=A2n/2+B ，Y=C2n/2+D。
这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。
所有这些加法和移位共用O(n)步运算。
设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有:(2)由此可得T(n)=O(n2)。
因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。
要想改进算法的计算复杂性，必须减少乘法次数。
求最大元和次大元1。
问题描述从多个数中一次性查找出元素最大的值和最小值,查找元素规模即元素的个数n,用分治的思想编制程序,实现分治的最大元和最小元求法。
进一步改进算法，使之能一次性求出最大和和次大元（即第二大元素）. 2.算法设计思想及描述分治发的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题相互独立与原问题相同。
递归地解决这些问题，然后将各个子问题的解合并得到原问题的解。
基于课堂的分析知道，对于本问题k 的值取为2，这样可以使子问题的规模是相同的，有利于算法实现。
为平衡分治时子问题的规模，这里约定需要查找元素的规模n 是2的幂次方。
用数组存储需要查找的元素，用结构体存储返回的最大元和最小元。
每次得到局部的最大元和局部次大元，然后局部最大元和最大元比较得到新的局部最大元，次大元和次大元比较得到新的局部次大元.深入分析，这种方式局部次大元是错误的.如两组元素中，a1〉b1，a2〉b2,当然a1和a2中较大的是新的局部最大元，但是b1和b2中较大的元素不是这四个元素中第二大的。
这样的方法漏掉了b1可能是次大元的情况,也就是说所有的元素中的次大元可能在与最大元比较的时候被漏掉了。
弥补的方法就是每次将每个元素比自身小的元素都用一个淘汰数组保存起来，最后次大元就是最大元的淘汰数组中第二大的那个元素。
3.算法分析运用分治算法解决此问题，是因为这种方法的优越行,下面通过时间复杂度的比较来说明.通常算法，设置一个变量,等于需要比较的数组的第一个元素,然后依次与后面的n —1经行比较,需要比较n-1次得到最大元。
同理，求得最小元的比较次数仍然是n —1次。
设()n T 表示比较的次数则对于这种算法得到()n T 的值为()22n T n =-分治算法求最大元比较1()2()22T n nT ⎧⎪=⎨+⎪⎩ 解方程结果为() 1.52T n n =-,虽然二者都是线性增长的，可是增长率要小一些。
求最大元和次大元1.问题描述从多个数中一次性查找出元素最大的值和最小值，查找元素规模即元素的个数n,用分治的思想编制程序，实现分治的最大元和最小元求法。
进一步改进算法，使之能一次性求出最大和和次大元（即第二大元素）。
2.算法设计思想及描述分治发的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题相互独立与原问题相同。
递归地解决这些问题，然后将各个子问题的解合并得到原问题的解。
基于课堂的分析知道，对于本问题k 的值取为2，这样可以使子问题的规模是相同的，有利于算法实现。
为平衡分治时子问题的规模，这里约定需要查找元素的规模n 是2的幂次方。
用数组存储需要查找的元素，用结构体存储返回的最大元和最小元。
每次得到局部的最大元和局部次大元，然后局部最大元和最大元比较得到新的局部最大元，次大元和次大元比较得到新的局部次大元。
深入分析，这种方式局部次大元是错误的。
如两组元素中，a1>b1,a2>b2,当然a1和a 2中较大的是新的局部最大元，但是b1和b2中较大的元素不是这四个元素中第二大的。
这样的方法漏掉了b1可能是次大元的情况，也就是说所有的元素中的次大元可能在与最大元比较的时候被漏掉了。
弥补的方法就是每次将每个元素比自身小的元素都用一个淘汰数组保存起来，最后次大元就是最大元的淘汰数组中第二大的那个元素。
3.算法分析运用分治算法解决此问题，是因为这种方法的优越行，下面通过时间复杂度的比较来说明。
通常算法，设置一个变量，等于需要比较的数组的第一个元素，然后依次与后面的n-1经行比较，需要比较n-1次得到最大元。
同理，求得最小元的比较次数仍然是n -1次。
设()n T 表示比较的次数则对于这种算法得到()n T 的值为 ()22n T n =-分治算法求最大元比较1()2()22T n n T ⎧⎪=⎨+⎪⎩解方程结果为() 1.52T n n =-,虽然二者都是线性增长的，可是增长率要小一些。
java大数乘法Java大数乘法Java是一种高级编程语言，它的强大之处在于它可以处理各种类型的数据，包括大数。
在Java中，大数是指超过了基本数据类型的范围的数字，例如1000位的整数。
在计算机科学中，大数乘法是一种重要的算法，它可以用来计算大数的乘积。
本文将介绍Java中的大数乘法算法。
一、大数乘法的基本原理大数乘法的基本原理是将两个大数分别拆分成若干个小数，然后将小数相乘，最后将结果相加得到最终的乘积。
例如，要计算123456789012345678901234567890的平方，可以将它拆分成123456789012345678901234567和890，然后将这两个数相乘，最后将结果相加得到最终的乘积。
二、Java中的大数乘法实现在Java中，可以使用BigInteger类来实现大数乘法。
BigInteger类是Java中的一个内置类，它可以处理任意长度的整数。
下面是一个使用BigInteger类实现大数乘法的示例代码：```import java.math.BigInteger;public class BigMultiplication {public static void main(String[] args) {BigInteger a = new BigInteger("123456789012345678901234567");BigInteger b = new BigInteger("890");BigInteger c = a.multiply(b);System.out.println(c);}}```在上面的代码中，我们首先创建了两个BigInteger对象a和b，分别表示要相乘的两个大数。
然后，我们使用multiply()方法将它们相乘，得到一个新的BigInteger对象c，表示它们的乘积。
最后，我们使用println()方法将结果输出到控制台。
分治法-⼤整数乘法和Strassen矩阵乘法4.5.1 ⼤整数乘法对于100位甚⾄更多位的⼗进制之间的乘法运算还是⽐较复杂的。
我们使⽤经典的笔算算法来对两个n位整数相乘，第⼀个数中的n个数字都要被第⼆个数中的n个数字相乘，这样就需要做n2次相乘，⽽使⽤分治技术，我们就能设计出乘法次数少于n2次的算法。
先来看下这个简单公式：令，则我们实际上要处理的就是中间的这⼀部分，就是将这两次乘法转为⼀次乘法，具体实现可由下⾯这个公式得到：我们令，所以，原式为：额，这个算法还是有点复杂，代码不知道该怎么写。
4.5.2 S t rassen矩阵乘法V.Strassen在1969年发表了这个算法，它的成功依赖于这个发现：计算两个2阶⽅阵A和B的积C只需要进⾏7次乘法运算，⽽不是蛮⼒算法所需要的8次。
公式参照如下：其中，因此，对于两个2阶⽅阵相乘时，Strassen算法执⾏了7次乘法和18次加减法，⽽蛮⼒法需要执⾏8次乘法和4次加法。
虽然只是减少了⼀次乘法，但当矩阵的阶趋于⽆穷⼤时，算法卓越的效率就渐渐表现出来了。
代码实现这个算法对我来说感觉还是有点复杂:-)，毕竟考虑的因素有很多，因为进⾏乘法运算的矩阵并不都是2n阶的，⽽且矩阵之间是⽆法进⾏乘法运算的，总之，思路感觉有点多啊。
以下代码是我排除了各种不定因素，且进⾏乘法运算的矩阵都是2n阶的⽅阵（好像是有点low哦，不过不管啦）。
代码实现：/*** Strassen算法进⾏矩阵相乘* @author xiaofeig* @since 2015.9.19* @param marix1 要进⾏相乘的矩阵1* @param marix2 要进⾏相乘的矩阵2* @return返回相乘的结果* */public static int[][] strassenMultiplyMatrix(int[][] marix1, int[][] marix2){if(marix1.length==1){return new int[][]{{marix1[0][0]*marix2[0][0]}};}int xLen=marix1[0].length;int yLen=marix1.length;int[][] a00=copyArrayOfRange(marix1, 0, 0, yLen/2, xLen/2);int[][] a01=copyArrayOfRange(marix1, 0, xLen/2, yLen/2, xLen);int[][] a10=copyArrayOfRange(marix1, yLen/2, 0, yLen, xLen/2);int[][] a11=copyArrayOfRange(marix1, yLen/2, xLen/2, yLen, xLen);xLen=marix2[0].length;yLen=marix2.length;int[][] b00=copyArrayOfRange(marix2, 0, 0, yLen/2, xLen/2);int[][] b01=copyArrayOfRange(marix2, 0, xLen/2, yLen/2, xLen);int[][] b10=copyArrayOfRange(marix2, yLen/2, 0, yLen, xLen/2);int[][] b11=copyArrayOfRange(marix2, yLen/2, xLen/2, yLen, xLen);int[][] m1=strassenMultiplyMatrix(plusMarix(a00, a11), plusMarix(b00, b11));int[][] m2=strassenMultiplyMatrix(plusMarix(a10, a11), b00);int[][] m3=strassenMultiplyMatrix(a00, minusMarix(b01, b11));int[][] m4=strassenMultiplyMatrix(a11, minusMarix(b10, b00));int[][] m5=strassenMultiplyMatrix(plusMarix(a00, a01), b11);int[][] m6=strassenMultiplyMatrix(minusMarix(a10, a00), plusMarix(b00, b01));int[][] m7=strassenMultiplyMatrix(minusMarix(a01, a11), plusMarix(b10, b11));int[][] newMarix1=plusMarix(minusMarix(plusMarix(m1, m4), m5), m7);int[][] newMarix2=plusMarix(m3, m5);int[][] newMarix3=plusMarix(m2, m4);int[][] newMarix4=plusMarix(minusMarix(plusMarix(m1, m3), m2), m6);return mergeMarix(newMarix1, newMarix2, newMarix3, newMarix4);}/*** 复制指定矩阵的某范围内的数据到以新的数组* @author xiaofeig* @since 2015.9.19* @param array ⽬标数组* @param i,j 左上⾓元素下标（包含）* @param m,n 右下⾓元素下标（不包含）* @return返回指定数组某范围的新数组* */public static int[][] copyArrayOfRange(int[][] array,int i,int j,int m,int n){int[][] result=new int[m-i][n-j];int index=0;while(i<m){result[index]=Arrays.copyOfRange(array[i], j, n);index++;i++;}return result;}/*** 进⾏矩阵之间的加法运算* @author xiaofeig* @since 2015.9.19* @param marix1 加数矩阵1* @param marix2 加数矩阵2* @return返回结果矩阵* */public static int[][] plusMarix(int[][] marix1,int[][] marix2){int[][] result=new int[marix1.length][marix1[0].length];for(int i=0;i<marix1.length;i++){for(int j=0;j<marix1[0].length;j++){result[i][j]=marix1[i][j]+marix2[i][j];}}return result;}/*** 进⾏矩阵之间的减法运算* @author xiaofeig* @since 2015.9.19* @param marix1 减数矩阵* @param marix2 被减数矩阵* @return返回结果矩阵* */public static int[][] minusMarix(int[][] marix1,int[][] marix2){int[][] result=new int[marix1.length][marix1[0].length];for(int i=0;i<marix1.length;i++){for(int j=0;j<marix1[0].length;j++){result[i][j]=marix1[i][j]-marix2[i][j];}}return result;}/*** 将四个矩阵合并为⼀个矩阵* @param marix1 数组1* @param marix2 数组2* @param marix3 数组3* @param marix4 数组4* @return返回合并之后的新矩阵* */public static int[][] mergeMarix(int[][] marix1,int[][] marix2,int[][] marix3,int[][] marix4){ int m=marix1.length,n=marix1[0].length;int[][] marix=new int[m*2][n*2];for(int i=0;i<marix.length;i++){for(int j=0;j<marix[i].length;j++){if(i<m){if(j<n){marix[i][j]=marix1[i][j];}else{marix[i][j]=marix2[i][j-n];}}else{if(j<n){marix[i][j]=marix3[i-m][j];}else{marix[i][j]=marix4[i-m][j-n];}}}}return marix;}算法分析：上⾯的代码我⽤了两个23阶的矩阵测试过，结果是正确的，其它阶数的矩阵我没测试，估计会有很多错误。
大数相乘的快速算法
数字乘法运算是每个学生都会接触到的算术基本运算，今天要介绍的是“大数乘法的快速算法”
它可以将两个大数的乘积运算时间从粗略的O（n2）减少到O （nlogn），大大提高了计算效率。
大数乘法的快速算法的原理是分治法。
即将原始的乘法问题分解成几个更小的乘法子问题，将它们分别计算，再把计算结果组合起来，最终得到原始问题的结果
首先，我们把要进行计算的两个大整数分别表示为两个位数m、n的数组A和B，任定一个位数为k的数，使A和B各被划分为k段，即A=a1a2a3a4...ak，B=b1b2b3b4...bk。
这样，原始乘积问题就可以等价地写为：A*B=a1a2a3a4...ak*b1b2b3b4...bk。
接下来，我们令A1=a1a2, A2=a3a4，B1=b1b2, B2=b3b4，则A*B=A1A2*B1B2=(A1*B1)*(A2*B2)+[(A2A1)-(A2*B1)-(A1*B2)]*10k，其中k表示乘数系数。
所以，只要把前半部分的子问题也分解为更小的子问题，便可以递归地求解。
最后，当子乘积问题足够小时，就可以用普通的乘法操作进行计算。
当递归达到最底部，把子问题的解组合成原始问题的解，就可以求得这两个大整数的乘积了。
“大数乘法的快速算法”能够得到分治法的优点，把乘积的计算时间由普通的O（n2）降低到O（nlogn），在实际计算中具有很好的效果。
求最大元和次大元1.问题描述从多个数中一次性查找出元素最大的值和最小值，查找元素规模即元素的个数n,用分治的思想编制程序，实现分治的最大元和最小元求法。
进一步改进算法，使之能一次性求出最大和和次大元（即第二大元素）。
2.算法设计思想及描述分治发的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题相互独立与原问题相同。
递归地解决这些问题，然后将各个子问题的解合并得到原问题的解。
基于课堂的分析知道，对于本问题k 的值取为2，这样可以使子问题的规模是相同的，有利于算法实现。
为平衡分治时子问题的规模，这里约定需要查找元素的规模n 是2的幂次方。
用数组存储需要查找的元素，用结构体存储返回的最大元和最小元。
每次得到局部的最大元和局部次大元，然后局部最大元和最大元比较得到新的局部最大元，次大元和次大元比较得到新的局部次大元。
深入分析，这种方式局部次大元是错误的。
如两组元素中，a1>b1,a2>b2,当然a1和a2中较大的是新的局部最大元，但是b1和b2中较大的元素不是这四个元素中第二大的。
这样的方法漏掉了b1可能是次大元的情况，也就是说所有的元素中的次大元可能在与最大元比较的时候被漏掉了。
弥补的方法就是每次将每个元素比自身小的元素都用一个淘汰数组保存起来，最后次大元就是最大元的淘汰数组中第二大的那个元素。
3.算法分析运用分治算法解决此问题，是因为这种方法的优越行，下面通过时间复杂度的比较来说明。
通常算法，设置一个变量，等于需要比较的数组的第一个元素，然后依次与后面的n-1经行比较，需要比较n-1次得到最大元。
同理，求得最小元的比较次数仍然是n-1次。
设()n T 表示比较的次数则对于这种算法得到()n T 的值为()22n T n =-分治算法求最大元比较1()2()22T n nT ⎧⎪=⎨+⎪⎩ 解方程结果为() 1.52T n n =-,虽然二者都是线性增长的，可是增长率要小一些。
实际编程时的实现有细微差距。
另外，求最大元，次大元的时候次大元总是在最大元的淘汰数组中，所以求次大元时，多了从最大元数组中找次大元的情形，n取对数，增长率仍然是比较小的。
4.代码#include "iostream.h"#define N 10int max(int a,int b){return((a>b)?a:b);}int min(int a,int b){return((a<b)?a:b);}void Search(int a[],int *max0,int *second0,int n){int g[30];int i,m;int max1,max2,second1,second2;if(n==1){*max0=a[0];*second0=a[0];}else if(n==2){*max0=max(a[0],a[1]);*second0=min(a[0],a[1]);}else{m=n/2;for(i=0;i<m;i++)g[i]=a[i];Search(g,&max1,&second1,m);for(i=0;i<n-m;i++)g[i]=a[i+m];Search(g,&max2,&second2,n-m);*max0=max(max1,max2);*second0=max(min(max1,max2),max(second1,second2));}}void main(){cout<<"用分治法同时求最大元和次大元\n";int a[N];int i,max,second;cout<<"输入"<<N<<"个数:\n";for(i=0;i<N;i++)cin>>a[i];Search(a,&max,&second,N);cout<<"输出结果:\n";cout<<"max="<<max<<"\n";cout<<"second="<<second<<"\n";}两个n位大整数相乘算法（1）问题的描述通过分治法求两个大整数的乘法（2）算法设计思想及算法分析设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。
我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。
如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。
下面我们用分治法来设计一个更有效的大整数乘积算法。
x = |A|B| y=|C|D| 大整数X和Y的分段我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如上由此，X=A2n/2+B ，Y=C2n/2+D。
这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。
所有这些加法和移位共用O(n)步运算。
设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有:T(1)=1(2)由此可得T(n)=O(n2)。
因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。
要想改进算法的计算复杂性，必须减少乘法次数。
为此我们把XY写成另一种形式:XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。
由此可得:T(1)=1T(n)=3T(n/2)+cn (4)用解递归方程的套用公式法马上可得其解为T(n)=O(n log3)=O(n1.59)。
利用式(3)，并考虑到X 和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下:function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY} beginS:=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}X:=ABS(X);Y:=ABS(Y); {X和Y分别取绝对值}if n=1 thenif (X=1)and(Y=1) then return(S)else return(0)else beginA:=X的左边n/2位;B:=X的右边n/2位;C:=Y的左边n/2位;D:=Y的右边n/2位;ml:=MULT(A,C,n/2);m2:=MULT(A-B,D-C,n/2);m3:=MULT(B,D,n/2);S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return(S);end;end;上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
下面的例子演示了算法的计算过程。
设X=314l,Y=5327，用上述算法计算XY的计算过程可列表如下，其中带'号的数值是在计算完成AC，BD，和(A-B)(D-C)之后才填入的。
X=3141 A=31 B=41 A-B=-10Y=5327 C=53 D=27 D-C=-26AC=(1643)'BD=(1107)'(A-B)(D-C)=(260)'XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'=(16732107)'A=31 A1=3 B1=1 A1-B1=2C=53 C1=5 D1=3 D1-C1=-2A1C1=15 B1D1=3 (A1-B1)(D1-C1)=-4AC=1500+(15+3-4)10+3=1643B=41 A2=4 B2=1 A2-B2=3D=27 C2=2 D2=7 D2-C2=5A2C2=8 B2D2=7 (A2-B2)(D2-C2)=15BD=800+(8+7+15)10+7=1107|A-B|=10 A3=1 B3=0 A3-B3=1|D-C|=26 C3=2 D3=6 D3-C3=4A3C3=2 B3D3=0 (A3-B3)(D3-C3)=4(A-B)(D-C)=200+(2+0+4)10+0=260（3）代码/************************************************************************///函数功能：分治法求两个N为的整数的乘积//输入参数：X,Y分别为两个N为整数//算法思想：//时间复杂度为：T(n)=O(nlog3)=O(n1.59)/************************************************************************/#define SIGN(A) ((A > 0) ? 1 : -1)double doubleegerMultiply(double X, double Y, double N){double sign = SIGN(X) * SIGN(Y);double x = abs(X);double y = abs(Y);if((0 == x) || (0 == y))return 0;if (1 == N)return x*y;else{double XL = x / (double)pow(10., (double)N/2);double XR = x - XL * (double)pow(10., N/2);double YL = y / (double)pow(10., (double)N/2);double YR = y - YL * (double)pow(10., N/2);double XLYL = IntegerMultiply(XL, YL, N/2);double XRYR = IntegerMultiply(XR, YR, N/2);double XLYRXRYL = IntegerMultiply(XL - XR, YR - YL, N/2) + XLYL + XRYR;return sign * (XLYL * (double)pow(10., N) + XLYRXRYL * (double)pow(10., N/2) + XRYR);}}double _tmain(double argc, _TCHAR* argv[]){double x = 1234;double y = 4321;cout<<"x * y = "<<IntegerMultiply(x, y, 4)<<endl;cout<<"x * y = "<<x*y<<endl;return 0;}。
