精华内容
下载资源
问答
  • 大整数乘法分治法
    2021-05-19 17:16:11

    #include

    #include

    using namespace std;

    int num(int u) //计算乘数的位数

    {

    int i,num;

    i=1;

    num=u/10;

    while(num!=0)

    {

    u=num;

    num=u/10;

    i=i+1;

    }

    // cout<

    return i;

    }

    void MUL(int u,int i,int &w,int &x)//将乘数分治

    {

    w=u/(pow(10,i/2));

    x=u-w*pow(10,i/2);

    // cout<

    }

    int main(int argc, char* argv[])

    {

    int multi,multi1;//定义两个乘数

    int number,number1,w,x,y,z,product,product1,product2,product3;

    cout<

    cin>>multi>>multi1;

    number=num(multi);//计算位数

    number1=num(multi1);

    MUL(multi,number,w,x);//将乘数分治

    MUL(multi1,number1,y,z);

    if(number%2!=0)//如果乘数位数是奇数

    {

    product=w*y*pow(10,number-1);

    product1=((w+x)*(y+z)-w*y-x*z)*pow(10,number/2);

    product2=x*z;

    product3=product+product1+product2;

    // cout<

    cout<

    }

    else//如果乘数位数是偶数

    {

    product=w*y*pow(10,number);

    product1=((w+x)*(y+z)-w*y-x*z)*pow(10,number/2);

    product2=x*z;

    product3=product+product1+product2;

    // cout<

    cout<

    }

    return 0;

    }

    更多相关内容
  • 大整数乘法 分治法

    2013-02-23 06:41:26
    大整数乘法 分治法
  • 大整数分解问题:给定两个n位长二进制数x和y,求这两个数的乘积。时间复杂性控制在Θ(n1.6)
  • {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:=...

    function MULT(X,Y,n); {X和Y为2个小于2n的整数,返回结果为X和Y的乘积XY}

    begin

    S:=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}

    X:=ABS(X);

    Y:=ABS(Y); {X和Y分别取绝对值}

    if n=1 then

    if (X=1)and(Y=1) then return(S)

    else return(0)

    else begin

    A:=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=-10

    Y=5327        C=53       D=27        D-C=-26

    AC=(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=2

    C=53        C1=5       D1=3        D1-C1=-2

    A1C1=15     B1D1=3     (A1-B1)(D1-C1)=-4

    AC=1500+(15+3-4)10+3=1643

    B=41        A2=4       B2=1        A2-B2=3

    D=27        C2=2       D2=7        D2-C2=5

    A2C2=8     B2D2=7     (A2-B2)(D2-C2)=15

    BD=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=4

    A3C3=2     B3D3=0     (A3-B3)(D3-C3)=4

    (A-B)(D-C)=200+(2+0+4)10+0=260

    如果将一个大整数分成3段或4段做乘法,计算复杂性会发生会么变化呢?是否优于分成2段做的乘法?这个问题请大家自己考虑。

    展开全文
  • 利用字符串和分治法来实现大整数乘法,内含c++源代码和实验报告说明
  • 分治法大整数乘法(python)

    目录

    一、问题描述

    二、思路分析

    分治法介绍:

    问题分析:

    三、算法伪代码

    四、代码实现效果

    五、源代码 

    六、参考文章


    一、问题描述

    请设计一个有效的算法,可以进行两个n位大整数的乘法。(n=2^k, k=1,2,3....)

    二、思路分析

    分治法介绍:

    分治法: 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

    有两点需要记住:

    (1) 分治法基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。

    (2)递归的解这些子问题,然后将各子问题的解合并得到原问题的解。

    分治法的重点是分析问题是否可以划分为规模较小的子问题,难点是如何划分以及划分之后如何将各个子问题的解合并成最终的解。这一般需要用到数学知识或者其他理论。

    问题分析:

    我们可以把X分成a b两部分, Y分成c d两部分

    那么就有如下操作

     

    我们考虑到这里有4个乘法ac ad bc bd,我们是不是可以通过减少乘法的次数来降低时间复杂度呢?答案是可以的,进行如下操作:

    这两个算法的时间复杂度

    但是要注意a+b, d+c可能得到m+1位的结果,使问题规模扩大,所以我们选择这里面的第一种算法 。

    三、算法伪代码

    四、代码实现效果

     

     

     

    五、源代码 

    # 理想状态下大整数乘法
    # X = a b
    # Y = c d
    # XY = ac10^n + (ad+bc)10^(n/2) + bd    O(n^2)
    # XY = ac10^n(移位操作) + [(a-b)(d-c)+ ac + bd]10^(n/2) + bd     O(n^1.59)
    
    
    def SING(N):
        return 1 if N > 0 else -1
    
    
    def BigNumerMultiply(X, Y, n):
        sign = SING(X) * SING(Y)
        X = abs(X)
        Y = abs(Y)
        # 递归退出条件
        if X == 0 or Y == 0:
            return 0
        elif n == 1:
            return sign * X * Y
        else:
            halfN = int(n / 2)  # 也可以使用字符串切割获取
            a = int(X / pow(10, halfN))
            b = int(X % pow(10, halfN))
            c = int(Y / pow(10, halfN))
            d = int(Y % pow(10, halfN))
            AC = BigNumerMultiply(a, c, halfN)
            BD = BigNumerMultiply(b, d, halfN)
            ABCD = BigNumerMultiply(a-b, d-c, halfN)
            result = AC*pow(10, n)+(ABCD+AC+BD)*pow(10, halfN)+BD
            return sign * result
    
    
    if __name__ == '__main__':
        print('理想状态下用法!')
        X = int(input('请输入第一个n(n=2^k)位整数:'))
        Y = int(input('请输入第二个n(n=2^k)位整数:'))
        n = len(str(X))
        result = BigNumerMultiply(X, Y, n)
        print('分治乘法:{}'.format(result))
        print('普通乘法:{}'.format(str(X * Y)))
    
    
    # 样例输入:
    # 1.          2.
    # 4567        12345678
    # 1234        12345678
    #
    #
    # 错误输入:
    # 1.          2.
    # 123456      123
    # 123456      123
    
    
    
    
    

    六、参考文章

    分治法的经典问题——大整数相乘 - m0w3n - 博客园

    展开全文
  • PYTHON应用分治法实现大整数乘法: 一、实现正常的加法函数: #传入的a,b是字符串 def add(a,b): return str(int(a)+int(b)) 二、应用分治法实现大整数乘法: 具体思想见视频所讲: 算法导引-二分法(四)-10行内实现...

    何为分治法

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

    当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。

    利用分治策略求解时,所需时间取决于分解后子问题的个数、子问题的规模大小等因素,而二分法,由于其划分的简单和均匀的特点,是经常采用的一种有效的方法,例如二分法检索。

    分治法一般解题步骤

    分治法解题的一般步骤(主要采用递归算法):

    (1)分解,将要解决的问题划分成若干规模较小的同类问题;

    (2)求解,当子问题划分得足够小时,用较简单的方法解决;

    (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

    PYTHON应用分治法实现大整数乘法:

    一、实现正常的加法函数:

    #传入的a,b是字符串
    def add(a,b):
        return str(int(a)+int(b))

    二、应用分治法实现大整数乘法:

    具体思想见视频所讲:

    算法导引-二分法(四)-10行内实现大整数乘法(算法导引-二分法(四)-10行内实现大整数乘法_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1xF411e7jv?from=search&seid=2673357468237935346&spm_id_from=333.337.0.0)

     该功能具体的代码:

    def mul(a,b):
        N=3  #正常乘法为三位数乘三位数,以N为限制
        if len(b)>len(a):  #确保是位数大的数乘位数小的数
            a,b=b,a
        if(len(a)<=N):   #递归结束条件,当一个数一直被二分为3位数时,回溯。
            return str(int(a)*int(b))
        mid=len(a)//2  #二分大数
        a1=a[:mid]  #后面需补零
        a2=a[mid:]
        return add(mul(a1,b)+"0"*len(a2),mul(a2,b))

    三、PYTHON源代码:大整数乘法(分治法)

    #传入的参数a,b为字符串
    def mul(a,b):
        N=3  #正常乘法为三位数乘三位数,以N为限制
        if len(b)>len(a):  #确保是位数大的数乘位数小的数
            a,b=b,a
        if(len(a)<=N):   #递归结束条件,当一个数一直被二分为3位数时,回溯。
            return str(int(a)*int(b))
        mid=len(a)//2  #二分大数
        a1=a[:mid]  #后面需补零
        a2=a[mid:]
        return add(mul(a1,b)+"0"*len(a2),mul(a2,b))
    def add(a,b):
        return str(int(a)+int(b))
    a=input("请输入一个大整数a=")
    b=input("请输入一个大整数b=")
    w=mul(a,b)
    print(w)
    
    
    

    四、运行结果:

    展开全文
  • 分治法-大整数乘法

    万次阅读 多人点赞 2019-01-07 18:20:03
    可以将一个整数乘法分而治之,将问题变成小问题,变成简单的小数乘法再进行合并,从而解决上述问题。 当分解到只有一位数时,乘法就很简单了。 算法设计: 分解: 首先将2个整数a(n位)、b(m位)分解...
  • 分治法求解大整数乘法

    千次阅读 2020-12-09 20:49:26
    分治法求解大整数乘法 求解思想 ​ 实现大整数乘法的方法有许多种,其中我们最简单的方法就是小学里面教的竖式算法,这种方法在计算过程中数AAA需要和数BBB中的每一位数相乘,并且最终对每一位进行相加,就整体而言...
  • C++大整数乘法 分治方法

    千次阅读 2018-10-11 17:28:52
    求两个不超过200位的非负整数的积。 Input 有两行,每行是一个不超过200位的非负整数,没有多余的前导0。 Output 一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。 ...
  • 分治算法之大整数乘法】---C++实现

    千次阅读 多人点赞 2020-10-29 20:28:51
    大整数乘法:用分治算法编程实现两个n位十进制整数的乘法运算。 一种较为流行的思路(即分治) 分析 <整数的乘法> 在计算机中,长整形(long int)变量的范围不能超过10位数。 即便用双精度(double)...
  • 大整数乘法分治法)实验报告,包括问题描述、问题分析、复杂度分析、源代码以及运行结果截图,100%可以运行。
  • 分治法 - 大整数乘法 题目描述 求两个不超过200位的非负整数的积。 输入格式 有两行,每行是一个不超过200位的非负整数,没有多余的前导0。 输出格式 一行,即相乘后的结果。结果里不能有多余的前导0,即如果结果是...
  • 在计算机语言中,整数最大可以设置为unsigned long类型的,但是表示有限...本程序使用分治法实现,将n位二进制整数X和Y都分为2段,每段的长为n/2位。对输入的数转化为8的倍数,使用分治法转化为1位,然后递归调用计算。
  • 最近开了算法导论课,上来就是递归分治,大整数乘法就是分治法的典型案例,通过参考网上书上我终于编程实现了大整数乘法,特此纪念 原理 由于两个整数直接相乘太,所以我们可以将它划分成几个小块分别相乘,最后...
  • 首先,普通的X*Y复杂度为O(n^2),这个复杂度是不理想的,所以利用分治思想提高。 如图所示,分成三个子问题后,利用Master定理,发现时间并没有提高。 所以,进一步优化。 子问题变成了3个。E一次,F一次,G一次...
  • VC++ 分治法大整数乘法
  • 分治法实现大整数乘法问题packagealgorithm;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.io.IOException;importjava.math.*;publicclassDemo{publicstaticvoidmain(String[]args){Dem...
  • 分治递归————大整数乘法

    千次阅读 2018-11-30 18:42:50
    大整数乘法分治) 算法分析 设x,y十进制整数,计算乘积xy。 用小学方法设计算法,计算步骤太多,而且效率低。T(n)=O(n^2) 所以用分治方法设计更有效的大整数乘法。将n为十进制整数x,y分为两段,每段长为n/2...
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼#include #include #include #include using ...(a):(b)) //简化后面2个大整数的长度的比较#define Min(a,b) ((a)#define Cha(a,b) (Max(a,b)-Min(a,b))//string类型...
  • 大整数乘法 某些应用,尤其是当代的密码技术,需要对超过100位的十进制整数进行乘法运算。显然,因为这样的整数过于长,现代计算机的一个“字”是装不下的,所以我们需要对它们做特别的处理。这就是研究高效的大整数...
  • 分治法解决大整数乘法问题.docx
  • 分治算法解决大整数乘法问题

    千次阅读 2018-10-18 11:05:09
    整数相乘:小整数相乘在算法时间分析中可以认为是常数时间,但是对于大整数,时间需要考虑。两个N位数的整数X和Y相乘,常规方法花费时间是,因为X的每一位都要和Y的每一位相乘,是两层循环。 分治算法解决整数相乘...
  • 大整数乘法会存在溢出。 用分治法解决。 步骤如下 XXX和YYY是两个大数。 X=ABX=ABX=AB(AAA和BBB分别为XXX的高位和低位) Y=CDY=CDY=CD(CCC和DDD分别为YYY的高位和低位) 分别表示为: X=A×10n/2+BX=A×10^{n/2}+...
  •  我们将n位(为方便讨论简化问题,我们假设n是2的幂)十进制整数(二进制也可以)X、Y都分为2段,每段的长度是n/2位。  如果现在直接用递归或分治进行编程,其算法复杂度为:  其中:T(n)代表规模为n的问题...
  • (2)大整数乘法
  • 式(3)看起来比式(1)复杂,但它仅需做3次n/2位整数乘法:AC,BD和(A-B)(D-C),6次加、减法和2次移位。由此可得:用解递归方程的迭代公式,不妨设n=2^k: T(n)=3T(n/2)+cn =3(3T(n/4)+cn/2)+cn =9(T(n/8)+ cn/4)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,850
精华内容 1,940
关键字:

大整数乘法分治法