《趣学算法》第三章 分治法源代码

标签：i+1   二分   记录   递归   数组   quick   head   string   cst   

分治法代码实现

1、猜数游戏——二分搜索技术

//program 3-1
#include
#include
#include
using namespace std;
const int M=10000;
int x,n,i;
int s[M];

int BinarySearch(int n,int s[],int x)
{
   int low=0,high=n-1;  //low指向有序数组的第一个元素，high指向有序数组的最后一个元素
   while(lows[middle])   //x大于查找范围的中间元素，则从左半部分查找
              low=middle+1;
            else   //x小于查找范围的中间元素，则从右半部分查找
              high=middle-1;
    }
    return -1;
}

int main()
{
    cout>n)
    {
        cout>s[i];
        sort(s,s+n);
        cout>x;
        i=BinarySearch(n,s,x);
        if(i==-1)
          cout

2、合久必分，分久必合——合并排序

//program 3-2
#include 
#include 
using namespace std;
void Merge(int A[], int low, int mid, int high)
{
    int *B=new int[high-low+1];//申请一个辅助数组
    int i=low, j=mid+1, k=0;
    while(i>n;
    cout>A[i];
    MergeSort(A,0,n-1);
    cout

3、兵贵神速——快速排序

//program 3-3
#include 
using namespace std;
int Partition(int r[],int low,int high)//划分函数
{
    int i=low,j=high,pivot=r[low];//基准元素
    while(ipivot) j--;//向左扫描
        if(ipivot) j--;//向左扫描
        while(ipivot)
    {
        swap(r[i-1],r[low]);//r[i-1]和r[low]交换
        return i-1;//返回最终划分完成后基准元素所在的位置
    }
    swap(r[i],r[low]);//r[i]和r[low]交换
    return i;//返回最终划分完成后基准元素所在的位置
}

void QuickSort(int R[],int low,int high)//实现快排算法
{
    int mid;
    if(low>N;
    cout>a[i];
    cout

4、效率至上——大整数乘法

//program 3-4
#include 
#include 
#include 
using namespace std;

#define M 100

char sa[1000];
char sb[1000];

typedef struct _Node
{
    int s[M];
    int l;            //代表字符串的长度
    int c;
} Node,*pNode;

void cp(pNode src, pNode des, int st, int l)
{
    int i, j;
    for(i=st, j=0; is[j] = src->s[i];
    }
    des->l = l;
    des->c = st + src->c;  //次幂

}

/*
分治法 大数乘法
X = A*10^n + B
Y = C*10^m + D
X*Y = A*C*10^(n+m) + A*D*10^n + B*C*10^m + B*D
*/

void add(pNode pa, pNode pb, pNode ans)
{
    int i,cc,k,palen,pblen,len;
    int ta, tb;
    pNode temp;
    if((pa->cc))   //保证Pa的次幂大
    {
        temp = pa;
        pa = pb;
        pb = temp;
    }
    ans->c = pb->c;
    cc = 0;
    palen=pa->l + pa->c;
    pblen=pb->l + pb->c;
    if(palen>pblen)
        len=palen;
    else
        len=pblen;
    k=pa->c - pb->c;
    for(i=0; ic; i++) //结果的长度最长为pa，pb之中的最大长度减去最低次幂
    {
        if(is[i-k];//次幂高的补0，大于低的长度后与0进行计算
        if(il)
            tb = pb->s[i];
        else
            tb = 0;
        if(i>=pa->l+k)
            ta = 0;
        ans->s[i] = (ta + tb + cc)%10;
        cc = (ta + tb + cc)/10;
    }
    if(cc)
        ans->s[i++] = cc;
    ans->l = i;
}

void mul(pNode pa, pNode pb, pNode ans)
{
    int i, cc, w;
    int ma = pa->l>>1, mb = pb->l>>1; //长度除2
    Node ah, al, bh, bl;
    Node t1, t2, t3, t4, z;
    pNode temp;

    if(!ma || !mb) //如果其中个数为1
    {
        if(!ma)   //如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度
        {
            temp = pa;
            pa = pb;
            pb = temp;
        }
        ans->c = pa->c + pb->c;
        w = pb->s[0];
        cc = 0;     //此时的进位为c
        for(i=0; i l; i++)
        {
            ans->s[i] = (w*pa->s[i] + cc)%10;
            cc= (w*pa->s[i] + cc)/10;
        }
        if(cc)
            ans->s[i++] = cc; //如果到最后还有进位，则存入结果
        ans->l = i;          //记录结果的长度
        return;
    }
    //分治的核心
    cp(pa, &ah, ma, pa->l-ma);  //先分成4部分al,ah,bl,bh
    cp(pa, &al, 0, ma);
    cp(pb, &bh, mb, pb->l-mb);
    cp(pb, &bl, 0, mb);

    mul(&ah, &bh, &t1);     //分成4部分相乘
    mul(&ah, &bl, &t2);
    mul(&al, &bh, &t3);
    mul(&al, &bl, &t4);

    add(&t3, &t4, ans);
    add(&t2, ans, &z);
    add(&t1, &z, ans);
}

int main()
{
    Node ans,a,b;
    cout > sa;
    cout > sb;
    a.l=strlen(sa);//sa,sb以字符串进行处理
    b.l=strlen(sb);
    int z=0,i;
    for(i = a.l-1; i >= 0; i--)
        a.s[z++]=sa[i]-‘0‘;             //倒向存储
    a.c=0;
    z=0;
    for(i = b.l-1; i >= 0; i--)
        b.s[z++] = sb[i]-‘0‘;
    b.c = 0;
    mul(&a, &b, &ans);
    cout = 0; i--)
        cout 

//program 3-4-1
#include 
#include 
#include 
using namespace std;

#define M 100

char sa[1000];
char sb[1000];

typedef struct _Node
{
    int s[M];
    int l;            //代表字符串的长度
    int c;
} Node,*pNode;


void add(pNode pa, pNode pb, pNode ans)
{
    int i,cc,k,palen,pblen,len;
    int ta, tb;
    pNode temp;
    if((pa->cc))   //保证Pa的次幂大
    {
        temp = pa;
        pa = pb;
        pb = temp;
    }
    ans->c = pb->c;
    cc = 0;
    k=pa->c - pb->c;
    palen=pa->l + pa->c;
    pblen=pb->l + pb->c;
    if(palen>pblen)
        len=palen;
    else
        len=pblen;
    len=len-ans->c;
    for(i=0; is[i-k];//次幂高的补0，大于低的长度后与0进行计算
        if(il)
            tb = pb->s[i];
        else
            tb = 0;
        if(i>=pa->l+k)
            ta = 0;
        ans->s[i] = (ta + tb + cc)%10;
        cc = (ta + tb + cc)/10;
    }
    if(cc)
        ans->s[i++] = cc;
    ans->l = i;
}

int main()
{
    Node ans,a,b;//ans用来存储结果，倒向存储
    cout > sa;
    cout > a.c;
    cout > sb;
    cout > b.c;
    a.l=strlen(sa);//sa,sb以字符串进行处理
    b.l=strlen(sb);
    int z=0,i;
    for(i = a.l-1; i >= 0; i--)
        a.s[z++]=sa[i]-‘0‘;             //倒向存储
    z=0;
    for(i = b.l-1; i >= 0; i--)
        b.s[z++] = sb[i]-‘0‘;
    cout = 0; i--)
        cout = 0; i--)
        cout =0; i--)
        cout 

《趣学算法》第三章 分治法源代码

标签：i+1   二分   记录   递归   数组   quick   head   string   cst   

原文地址：https://www.cnblogs.com/self-confidence/p/13604551.html