分治法
参考书目:《算法的乐趣》作者: 王晓华
分治法,分而治之
设计思想:将无法解决的大问题分解成一系列规模较小的相同问题,然后逐个解决小问题
应用目的:
1.通过分解问题,将无法解决的大问题变成容易解决的小问题
2.通过减少问题的规模,降低解决问题的复杂度(计算量)
步骤: 分解->解决->合并
针对不同的问题有不同的解决方案
快速排序:选择一个标兵数,将待排序的序列分成两个子序列,其中一个子序列中的数都小于标兵数,另一个子序列的数都大于标兵数,然后分贝对这两个子序列排序,合并时将已经排序好的子序列一前一后拼接,合成一个完整的有序序列。
快速傅里叶变换:将一个N点离散傅里叶变换,按奇偶关系分成N/2点离散傅里叶变换,合并时将两个N。2点离散傅里叶变换的结果按照蝶形运算(这里不是很明白,mark以下)的位置关系重新排列成一个N点序列。
Karatsuba乘法算法
将n位大数分成两部分:a+b,利用乘法公式:(a+b)(c+d)=ac+ad+bc+bd,合并时利用几次加法对小规模乘法的结果进行求和,得到原始问题饿解。
这种快速乘法算法将原来的O(n^2)变成了O(3n log3)=O(3n^1.585)
Karatsuba快速乘法原理
假如有两个n位的M进制大整数x,y,利用一个小于n的正数k(通常k的取值为n/2左右),将x,y分解成如下形式:
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVPVNjWmZVbiBXMyMGbwJDTwYVbiVHNHpleO1GTulzRilWO5x0LcRHelR3LcJzLctmch1mclRXY39zN3cjN0kzMwETMyMDM4EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
则,x,y的乘积可计算为:
下面有两种输入形式进行实现,一种是长整型,另一种是字符串形式。
/*
2018-3-18
分治法实现Karatsuba乘法算法
Part 1 以长整型的形式输入
copyright @GCN
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int length(long x,long y)
{
int temp,count=0;
if(x>y)
temp=x;
else
temp=y;
while((temp/10)!=0)
{
count+=1;
temp=temp/10;
}
count+=1;
//printf("此时的位数为:%d\n",count);
return count;
}
int getHigh(long x,int m)
{
int temp;
temp=x/pow(10,m);
return temp;
}
int getLow(long x,int m)
{
int temp;
temp=x-getHigh(x,m)*pow(10,m);
return temp;
}
long Karatsuba(long x,long y)
{
long x0,x1,y0,y1,result;
int m;
long k1,k2,k3;
if(x<=10&&y<=10)
return x*y;
m=length(x,y);
m=m/2;
x0=getHigh(x,m);
x1=getLow(x,m);
y0=getHigh(y,m);
y1=getLow(y,m);
printf("拆分后的x0=%ld\n",x0);
printf("拆分后的x1=%ld\n",x1);
printf("拆分后的y0=%ld\n",y0);
printf("拆分后的y1=%ld\n",y1);
printf("-------分割线-------\n\n");
k1=Karatsuba(x0,y0);
//printf("此时的k1=%ld\n",k1);
k2=Karatsuba(x1,y1);
//printf("此时的k2=%ld\n",k2);
//printf("x0+x1=%ld\n",(x0+x1));
//printf("y0+y1=%ld\n",(y0+y1));
k3=Karatsuba((x0+x1),(y0+y1));
//printf("此时的k3=%ld\n",k3);
result=k1*pow(10,2*m)+k2+(k3-k1-k2)*pow(10,m);
return result;
}
int main()
{
long num1=12345;
long num2=6789;
printf("num1=%ld\nnum2=%ld\n\n",num1,num2);
long result=Karatsuba(num1,num2);
printf("result=%ld\n\n",result);
return 0;
}
————————————————分割线,未完待续————————————————
贴上参考博文:是c++版的。
[算法系列之九]Karatsuba快速相乘算法