精华内容
下载资源
问答
  • 分治法求解大整数相乘问题 【问题描述】 设X和Y都是n位的大整数,现在要计算它们的乘积XY。 【提示】采用分治法求解两个十进制大整数的乘法,以提高乘法的效率,减少乘法次数。 计算公式为: XY=AC10n+[(A-B)(D-C)+...

    分治法求解大整数相乘问题

    【问题描述】 设X和Y都是n位的大整数,现在要计算它们的乘积XY。

    【提示】采用分治法求解两个十进制大整数的乘法,以提高乘法的效率,减少乘法次数。
    计算公式为:
    XY=AC10n+[(A-B)(D-C)+AC+BD]10n/2+BD
    下面的例子演示了分治算法的计算过程。
    设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次n/2位整数的乘法(AC,BD和(A-B)(D-C)),6次加、减法和2次移位的运算。所以,该算法时间复杂度为:
    T(n)=O(nlog3)=O(n1.59)

    //代码如下
    /*
    函数功能:分治法求两个N为的整数的乘积
    输入参数:X,Y分别为两个N位整数
    算法思想:
    时间复杂度为:T(n)=O(nlog3)=O(n1.59)
    */
    
    #include<iostream>
    #include<math.h>
    using namespace std;
    
    #define SIGN(A) ((A > 0) ? 1 : -1)			
    int IntegerMultiply(int X, int Y, int N)	//参数为大整数 X,Y及它们相同的位数 N 
    {
    	int sign = SIGN(X) * SIGN(Y);			//确定两数乘积的正负 
    	int x = abs(X);							//将两数化为绝对值,之后计算再加入正负号 
    	int y = abs(Y);
    	if((x == 0) || (y == 0))				//乘数有一个为 0,两数相乘为 0 
    		return 0;
    	if (N == 1)								//只剩一位时,返回 
    		return x*y;
    	else
    	{
    		int A = x / pow(10, N/2);     		
    		int B = x - A * pow(10, N/2); 
    		int C = y / pow(10, N/2);    
    		int D = y - C * pow(10, N/2);
    		
    		int AC = IntegerMultiply(A, C, N/2);   
    		int BD = IntegerMultiply(B, D, N/2);
    		int ADBC = IntegerMultiply(A - B, D - C, N/2) + AC + BD;
    		return sign * (AC * pow(10, N) + ADBC * pow(10, N/2) + BD); //可根据公式化简 
    	}
    }
    
    int main()
    {
    	int x, y, z, n = 0;
    	cin >> x >> y;
    	
    	z = x;
    	while(z != 0)			// 求 X,Y有多少位 
    	{
    		z = z / 10;
    		++n;
    	}
    
    	cout << "x * y = " << IntegerMultiply(x, y, n) << endl;
    	cout << "x * y = " << x * y << endl;
    	return 0;
    }
    
    展开全文
  • 整数相乘问题

    2019-04-17 14:43:52
    两个不超过200位的大整数相乘 #include<iostream> #include<string> using namespace std; int main() { string s1,s2; cin>>s1; cin>>s2; int a1[202],a2[202],s[404]={0}; int i,j=0...
    两个不超过200位的大整数相乘
    #include<iostream>
    #include<string>
    using namespace std;
    int main()
    {
    	string s1,s2;
    	cin>>s1;
    	cin>>s2;
    	int a1[202],a2[202],s[404]={0};
    	int i,j=0;
    	for(i=s1.length()-1;i>=0;i--)
    	{
    		a1[j]=s1[i]-'0';
    		j++;
    	}
    	int k=0;
    	for(i=s2.length()-1;i>=0;i--)
    	{
    		a2[k]=s2[i]-'0';
    		k++;
    	}
    	int count=0;
    	for(i=0;i<s1.length();i++)
    	{
    		for(int j=0;j<s2.length();j++)
    		{
    			int temp=s[i+j]+a1[i]*a2[j];
    			if(temp>9)
    			{
    				s[j+i+1]=s[i+j+1]+temp/10;
    				s[j+i]=temp%10;
    			}
    			else
    				s[j+i]=temp;
    			//cout<<a1[j]<<"--"<<a2[i]<<endl;
    			//cout<<s[j+i]<<"*";
    		}
    	}
    	int l=400;
    	while(s[l-1]==0)
    		l--;
    	for(i=l-1;i>=0;i--)
    		cout<<s[i];
    	return 0;
    }
    
    展开全文
  • 求解最大整数相乘问题 题目描述 : 有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。 输入描述: 空格分隔的两个字符串,代表输入的两个大整数 输出...


    题目描述 :


    有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。
    输入描述:
    空格分隔的两个字符串,代表输入的两个大整数
    输出描述:
    输入的乘积,用字符串表示
    输入:
    72106547548473106236 982161082972751393
    输出:
    70820244829634538040848656466105986748

    
    # include <bits/stdc++.h>
    # define N 10000
    using namespace std;
    
    int main() {
    	string s1,s2;
    	cin >> s1 >> s2;
    	reverse(s1.begin(),s1.end()); // 【千】【百】【十】【个】 --> 【个】【十】【百】【千】
    	reverse(s2.begin(),s2.end());
    
    	int a[N] = {0};
    
    	for(int i =0; i < s1.length(); i++) {
    		for(int j = 0; j < s2.length(); j++) {
    			a[i+j] += (s1[i] - '0') * (s2[j] - '0');
    		}
    	// 【个】【十】【百】【千】
    	}
    	
    	for(int i = 0; i < N-1; i++) {
    		a[i+1] += a[i]/10; // 低位除10后,向高位进位
    		a[i] = a[i]%10;
    	}
    	// 消除最后 【个】【十】【百】【千】- - - - - - 【0】【0】【0】中的0 
    	int i = N - 1;
    	while(a[i] == 0)
    		i--;
    	// 【千】【百】【十】【个】
    	for(int j=i; j >= 0; j--) {
    		cout << a[j];
    	}
    
    	return 0;
    }
    
    
    
    展开全文
  • 分治算法之大整数相乘问题

    千次阅读 2016-10-22 19:18:56
    2.问题分析(1)100位以上的整数,用整数变量直接存储装不下所以,中间运算时,牵扯到大数肯定当做字符串来存储(2)A和B直接乘操作肯定是操作不了,必须是分开来处理可以二分法,将AB转换A=A1*10^(n1/2) +A0 —– n1为a...

    1.问题描述

    求两个大数A、B乘积的准确结果

    其中A和B均为100位以上的十进制整数

    A和B的位数可以不相等


    2.问题分析

    (1)

    100位以上的整数,用整数变量直接存储装不下

    所以,中间运算时,牵扯到大数肯定当做字符串来存储

    (2)

    A和B直接乘操作肯定是操作不了,必须是分开来处理

    可以二分法,将AB转换

    A=A1*10^(n1/2) +A0 —– n1为a的位数

    B=B1*10^(n2/2)+B0 —–n2为b的位数

    那么 A*B={A1*10^(n1/2)+A0}*{B1*10^(n2/2)+B0}

    化简得

     A*B= 
    (A1*B1)*10^[(n1+n2)/2] 
    +(A1*B0)*10^(n1/2) 
    +(A0*B1)*10^(n2/2) 
    +(A0*B0)
    

    那么就把 n1 位的整数与 n2位的整数相乘的问题转化为

    1.四个`n1/2`位的整数和`n2/2`位的整数相乘
    
    2.三次移位
    
    3.四次“大数”加法
    

    3.问题解决

    (1)n1/2位的整数和n2/2位的大整数相乘

    问题又回到了原点——大整数相乘问题

    问题的解决需要调用自身来解决——递归

    (2)移位

    移位相当于是在后边补0

    那么就在要移位的数(字符串)后面添加一定量的0即可

    (3)“大数”加法

    因为中间操作的都是比较大的数,因此即使是中间值的相加,也是比较大的数,故要采用大数相加

    大数相加 问题 参见 大数相加


    4.代码实现

    import java.math.BigInteger;
    import java.util.Scanner;
    import org.stone.stack.MyBigAdd;
    /**
     * @ClassName_MyBigIntegerMutiply
     * @author_Stone6762
     * @CreationTime_2016年10月22日 下午3:39:57
     * @Description_ 大整数乘法A x B    AB可以为不同的位数 
     * 采用的是: 分治的思想,二分 
     */
    public class MyBigIntegerMutiply1 {
    
        /**
         * @Description:未优化的大数相乘
         * @param a
         * @param b
         * @return a*b={a1*10^(n1/2)+a0}*{b1*10^(n2/2)+b0} 
         */
        public static String Mutiply1(String a, String b)// 用字符串读入2个大整数
        {
            String result = "";
            if (a.length() == 1 || b.length() == 1)// 递归结束的条件
                           //其中一个长度为1,另一个不一定
                result = "" + Long.valueOf(a) * Long.valueOf(b);
            else// 如果2个字符串的长度都 >= 2
            {
                //1.分割成  a1  a0  b1  b0
                int lengthA0 = a.length() / 2;
                int lengthA1=a.length()-lengthA0;
                String a1 = a.substring(0, lengthA1); // 截取前一半的字符串(较短的一半)
                String a0 = a.substring(lengthA1, a.length()); // 截取后一半的字符串
    
                int lengthB0 = b.length() / 2;
                int lengthB1=b.length()-lengthB0;
                String b1 = b.substring(0, lengthB1);
                String b0 = b.substring(lengthB1, b.length());
                // * a*b=
                // * (a1*b1)* 10^[(n1+n2)/2 ]
                // * +(a1*b0)*10^(n1/2)
                // * +(a0*b1)*10^(n2/2)
                // * +(a0*b0)
                //2.计算展开式中的乘法
                String a1b1 = Mutiply1(a1, b1);
                String a1b0 = Mutiply1(a1, b0);
                String a0b1 = Mutiply1(a0, b1);
                String a0b0 = Mutiply1(a0, b0);
    
                //3.模拟移位
                String resulta1b1 = a1b1;
                for (int i = 0; i < lengthA0+lengthB0; i++) {
                    resulta1b1 += "0";
                }
                String resulta1b0 = a1b0;
                for (int i = 0; i <lengthA0; i++) {
                    resulta1b0 += "0";
                }
                String resulta0b1 = a0b1;
                for (int i = 0; i < lengthB0; i++) {
                    resulta0b1 += "0";
                }   
                //4.大数相加
                result = MyBigAdd.add(resulta1b1, resulta1b0);
                result = MyBigAdd.add(result, resulta0b1);
                result = MyBigAdd.add(result, a0b0);
            }
            return result;
        }
    
        /** 
         * @Description拿BigInteger自身大数相乘来判断自身算法的正确与否
         * @param args
         */
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while (scan.hasNext()) {
    
                String aString=scan.next();
                String bString=scan.next();
    
                BigInteger aBigInteger=new BigInteger(aString);
                BigInteger bBigInteger=new BigInteger(bString);
    
                String reslut1=aBigInteger.multiply(bBigInteger).toString();
                String result2=Mutiply1(aString, bString);
    
                System.out.println("标准答案:  "+reslut1);
                System.out.println("计算结果:  "+result2);
    
                System.out.println("结果是否正确:  "+reslut1.equals(result2));
            }
    
        }
    }

    5.缺点

    1. A和B的位数可以不相同
    
    但是相差不能太大,不能超过long的范围
    
    2.时间复杂度和空间复杂度比较高,没有优化
    

    6.更简单大数相乘大数相加

    java 类库自带 BigInteger和BigDecimal可以处理大整数和大浮点数
    其中有处理相加和相乘的函数


    如果仅仅是为了处理大数的相加和相乘,而不是为了研究,可以直接调用其封装好的函数即可


    (1)调用java类库的大数相加

    public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while (scan.hasNext()) {    
                String aString=scan.next();
                String bString=scan.next();
                BigInteger aBigInteger=new BigInteger(aString);
                BigInteger bBigInteger=new BigInteger(bString);
                String resultString=aBigInteger.add(bBigInteger).toString();    
                System.out.println("a加上b等于 "+resultString);
            }
        }

    (2)调用java类库的大数相乘

    public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            while (scan.hasNext()) {    
                String aString=scan.next();
                String bString=scan.next();
                BigInteger aBigInteger=new BigInteger(aString);
                BigInteger bBigInteger=new BigInteger(bString);
                String reslut1=aBigInteger.multiply(bBigInteger).toString();    
                System.out.println("a乘以b等于 "+reslut1);
            }
        }

    欢迎一起讨论其优化问题


    展开全文
  • 整数相乘.cpp

    2019-07-02 19:21:41
    假定有两个字符串表示的整形数,要求写一个函数,实现两个数字字符串的乘积,函数返回值也是字符串。我们不能直接将整形字符串转换为数字后去相乘,因为字符串表示的数字可能相当大,直接转换成数字会导致信息丢失,
  • 整数相乘算法

    千次阅读 2020-03-28 11:44:08
    求两个整数相乘的算法 算法分析 24 * 13 第一步计算4 * 13: 4 * 3 = 12(3在个位,不需要补零) 4 * 1 = 4(1在十位,需要补1个零) 4在个位,则结果不需要补零 结果:12 + 4 * 10 = 52 第二步计算2 * 13: 2 * 3 =...
  • 1 问题有两个n位大整数,,它们数值之分大,如。现在要计算它们的乘积...分治1复杂度分析:X乘Y,一共有4次位大整数相乘,3次加法,2次移位。这种分治的复杂度与传统计算方法相比并没有改进。分治2复杂度分析:X乘Y...
  • 分治法求两个大整数相乘C++实现。
  • 分治法的经典问题——大整数相乘

    万次阅读 多人点赞 2016-12-03 17:13:27
    通过大整数相乘问题来了解分治法假如现在我们要求两个大整数相乘的乘积,如1234 * 1234(这里为了了分析简便,所以不举形如1234567891234567这样的大整数,不必要在此纠结),那么按照我们小学学的乘法,就是用乘数...
  • 在Python中本来不存在所谓大整数溢出问题。但是,我看到了一个叫做阿拉伯乘法的方法,是一个古老的计算两个数相乘的问题。于是用它来计算两个大整数相乘,感觉还不错。
  • 有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。 输入描述: 空格分隔的两个字符串,代表输入的两个大整数 输出描述: 输入的乘积,用字符串表示 示例1 输入 ...
  • 这个东西还是很不错的,我们正在学习算法,学完之后,对这个问题有了很深的理解,希望大家能够从中获益。
  • [编程题] 大整数相乘  时间限制:1秒  空间限制:32768K  有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。  输入描述:  空格分隔的两个字符串,代表输入...
  • [Python]大整数相乘

    2021-01-30 05:32:16
    今天室友面试了,居然挂到了ByteDance的二面,其中考了一个大整数相乘,那么我就尝试借助Python再来写一遍吧!实现思路很简单,平时我们咋计算乘法的,就按照公式计算就好了,程序中就是要考虑好边界条件与此同时,...
  • 利用分治法思想,提出一种大整数相乘快速算法,减少乘法运算次数,使2个数相乘的计算复杂度从O(n)降低到O(1)。根据不同的加法思路,提出累加求和及统一求和2种改进算法,给出2种改进算法的形式化描述,并通过实验给出改进...
  • 整数相乘

    2019-06-23 18:39:01
    有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。 输入描述: 空格分隔的两个字符串,代表输入的两个大整数 输出描述: 输入的乘积,用字符串表示 示例1 ...
  • 问题整数相乘思路说明对于大整数计算,一般都要用某种方法转化,否则会溢出。但是python无此担忧了。Python支持“无限精度”的整数,一般情况下不用考虑整数溢出的问题,而且Python Int类型与任意精度的Long整数类...
  • 对于大整数计算,一般都要用某种方法转化,否则会溢出。但是python无此担忧了...问题整数相乘思路说明对于大整数计算,一般都要用某种方法转化,否则会溢出。但是python无此担忧了。Python支持“无限精度”的整数...
  • #include <iostream> #include <cstring> using namespace std; int main() { char sz1[100], sz2[100]; cin >> sz1 >> sz2; int len1 = strlen(sz1);... int len2 = strlen(...
  • JAVA实现大整数相乘

    2009-08-08 22:21:21
    JAVA实现的两个特大整数相乘的算法,可以达到1000位数相乘。
  • 我试图构建一个有理数类,它将基于输入值执行各种算术函数,而不使用fractions模块。当我使用两个不同的分数时,代码运行得很好...在我已经包含了下面的代码-有问题的操作是__radd__,但是当这包含在我的代码中时,...
  • 算法分析与设计 用递归分治算法解决大整数乘积问题(用java语言)
  • [编程题]大整数相乘 时间限制:1秒 空间限制:32768K 有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。 输入描述: 空格分隔的两个字符串,代表输入的两个大...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,206
精华内容 26,482
关键字:

整数相乘问题