【常用算法】分治法

分治法

參考書目：《算法的樂趣》作者: 王曉華

分治法，分而治之

設計思想：将無法解決的大問題分解成一系列規模較小的相同問題，然後逐個解決小問題

應用目的：

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快速相乘算法