分治法
參考書目:《算法的樂趣》作者: 王曉華
分治法,分而治之
設計思想:将無法解決的大問題分解成一系列規模較小的相同問題,然後逐個解決小問題
應用目的:
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分解成如下形式:
則,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快速相乘算法