精华内容
参与话题
问答
  • 大整数乘法

    2020-02-03 19:19:17
    大整数乘法 【分析】 一般情况下,求两个大整数相乘往往利用分治法解决,理解起来较为困难,这里我们使用的方法是模拟人类大脑计算两个整数相乘的方式进行求解大整数相乘,中间结果和最后结果仍然使用数组来存储。...

    大整数乘法

    【分析】

    一般情况下,求两个大整数相乘往往利用分治法解决,理解起来较为困难,这里我们使用的方法是模拟人类大脑计算两个整数相乘的方式进行求解大整数相乘,中间结果和最后结果仍然使用数组来存储。

    假设A为被乘数,B为乘数,分别从A和B的最低位开始,将B的最低位分别与A的个位数依次相乘,乘积的最低位存放在数组元素a[门]中,高位(进位)存放在临时变量d中;再将B的次低位与A的个位数相乘,并加上得到的进位d和a[],就是B中该位数字与A中对应位上数字的乘积,其中a[i]是之前得到乘积的第i位数字。依此类推,即可得到两个整数的乘积。

    code:

    #include <stdio.h>   
    #include <string.h>   
    #include <iostream>
    void main()
    {
    	long b, d;
    	int i, i1, i2, j, k, n, n1, n2, a[256];
    	char s1[256], s2[256];
    	printf("输入一个整数:");
    	scanf("%s", &s1);
    	printf("再输入一个整数:");
    	scanf("%s", &s2);
    	for (i = 0; i < 255; i++)
    		a[i] = 0;
    	n1 = strlen(s1);
    	n2 = strlen(s2);
    	d = 0;
    	for (i1 = 0, k = n1 - 1; i1 < n1; i1++, k--)
    	{
    		for (i2 = 0, j = n2 - 1; i2 < n2; i2++, j--)
    		{
    			i = i1 + i2;
    			b = a[i] + (s1[k] - 48)*(s2[j] - 48) + d;
    			a[i] = b % 10;
    			d = b / 10;
    		}
    		if (d > 0)
    		{
    			i++;
    			a[i] = a[i] + d % 10;
    			d = d / 10;
    		}
    		n = i;
    	}
    	printf("%s * %s= ", s1, s2);
    	for (i = n; i >= 0; i--)
    		printf("%d", a[i]);
    	printf("\n");
    	system("pause");
    }
    

    结果:

     

    展开全文
  • 大整数乘法 c++ 代码

    2011-07-25 18:27:52
    大整数乘法 c++ 代码 大整数乘法 c++ 代码 大整数乘法 c++ 代码 大整数乘法 c++ 代码 大整数乘法 c++ 代码 大整数乘法 c++ 代码 大整数乘法 c++ 代码 大整数乘法 c++ 代码
  • 大整数乘法(分治法)实验报告,包括问题描述、问题分析、复杂度分析、源代码以及运行结果截图,100%可以运行。
  • 大整数乘法C语言版本

    2014-09-24 19:11:14
    分治思想大整数乘法 基于王晓东版 算法设计与分析
  • 对算法分析与设计课程中大整数乘法的实现,并实现不同位数的大整数相乘
  • 大整数乘法的实现

    2016-01-13 19:01:57
    大整数乘法的分治法实现,编程语言使用C++.doc
  • 大整数乘法——算法思想及java实现

    千次阅读 2014-08-31 04:13:16
    参考了: http://blog.csdn.net/oh_maxy/article/details/10903929

    参考了:

    http://blog.csdn.net/oh_maxy/article/details/10903929

    但是该博主的实现并没有考虑时间效率,在博主代码的基础上了做了一点点改进,提高了时间效率。(由原来的O(n2)提高到O(n1.59))

    感谢博主提供的代码。最后附上我改进的版本。

    package algrithm.divideAndConquer;
    
    import java.util.Scanner;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;
    
    /**
     * 分治法例子:
     * 大整数乘法
     * @author tcj
     *
     */
    public class TwoBigIntegerMiltiply {
    		private final static int SIZE = 4;
    		//进制,这里处理输入10进制的大整数(在减法函数里面用到)
    		private final static int Dec = 10;
    	
    		//自己第一次写的,思路不清晰
    /*		public static boolean IsInteger(Object obj){
    			return (obj instanceof Integer);
    		}
    		
    		public static int[] BigIntegerMlt(int[] a,int[] b,int beginA,int endA,int beginB,int endB){
    			//如果输入为空
    			if(a == null || b == null){
    				return null;
    			}
    			//如果a,b或者元素为小数
    			
    			//如果a,b中有元素为负数
    			int[] result = null;
    			
    			return result;
    		}	*/	
    		
    		private static String BigIntegerMultiply(String X,String Y){
    			//最终返回结果
    			String  str = "";
    			int len1 = X.length();
    			int len2 = Y.length();
    			int len = Math.max(len1, len2);
    			//补齐X、Y,使之长度相同
    			X = formatNum(X,len);
    			Y = formatNum(Y,len);
    			
    			//少于4位数,可直接计算
    			if(len <= SIZE){
    				return "" + (Integer.parseInt(X) * Integer.parseInt(Y));
    			}
    			
    			int len3 = len/2;
    			int len4 = len - len3;
    			
    			//处理乘数,分块处理
    			String A = X.substring(0,len3);
    			String B = X.substring(len3);
    			String C = Y.substring(0,len3);
    			String D = Y.substring(len3);
    			
    			//递归求解分块
    			int lenM = Math.max(len3, len4);
    			String AC = BigIntegerMultiply(A,C);
    			String BD = BigIntegerMultiply(B,D);
    			//提高时间效率关键在这一步:
    			//将AC+BD --> (A-B)(D-C)+AC+BD
    			//这样仅需做3次n/2位整数的乘法,减少了一次
    			//之前的总时间T(n) = 4T(n/2) + O(n) --> O(n2)
    			//现在的总时间T(n) = 3T(n/2) + O(n) --> O(n1.59)
    			String AMinusB  = minus(A,B);
    			String DMinusC = minus(D,C);
    			String ABDC = BigIntegerMultiply(AMinusB,DMinusC);
    			ABDC = addition(addition(ABDC,AC),BD);
    			
    			//处理BD,得到原位及进位
    			String[] sBD = dealString(BD,len3);
    			
    			//加上BD的进位
    			if(!"0".equals(sBD[1])){
    				ABDC = addition(ABDC,sBD[1]);
    			}
    			
    			//处理ABDC,得到原位及进位
    			String[] sABDC = dealString(ABDC,len3);
    			
    			//AC加上ADBC的进位
    			if(!"0".equals(sABDC[1])){
    				AC = addition(AC,sABDC[1]);
    			}
    			
    
    			//最终结果
    			str = AC + sABDC[0] + sBD[0];	
    			
    			//之前写错了,下面是处理二进制大整数的算法
    //			String temp1 = "" + (Integer.parseInt(AC) >> len);
    //			String temp2 = "" + (Integer.parseInt(ABDC) >> len3);
    //			String temp3 = "" + (Integer.parseInt(AC) >> len3) ;
    //			String temp4 = "" + (Integer.parseInt(BD) >> len3) + BD;
    //			String temp1 = BigIntegerMultiply(AC,expOfTwo(len));
    //			String temp2 = BigIntegerMultiply(ABDC,expOfTwo(len3));
    //			String temp3 = BigIntegerMultiply(AC,expOfTwo(len3));
    //			String temp4 = BigIntegerMultiply(BD,expOfTwo(len3));
    //			String temp5 = addition(temp1,temp2);
    //			String temp6 = addition(temp3,temp4);
    			//最终结果
    //			str = addition(temp5,temp6);
    			return str;
    			
    		}
    		
    		private static String formatNum(String x,int len){
    			while(len > x.length()){
    				x = "0" + x;
    			}
    			
    			return x;
    		}
    		
    		private static String minus(String a,String b){
    			int lenA = a.length();
    			int lenB = b.length();	
    			int len = Math.max(lenA, lenB);
    			if(lenA != lenB){
    				a = formatNum(a,len);
    				b = formatNum(b,len);
    			}
    			String str = "";
    			//借位,用t存储
    			int flag = 0;
    			
    			//从后往前按位相加
    			for(int i = len - 1;i >=0;i--){
    			//	int t = 0;
    				int tempA = a.charAt(i) - '0';
    				int tempB = b.charAt(i) - '0';
    				int temp;
    				if(tempA - flag - tempB < 0 && i != 0){
    					temp = tempA + Dec - flag - tempB;
    					flag = 1;
    				}else{
    					temp = tempA - flag - tempB;
    					flag = 0;
    				}
    //				if(Integer.parseInt(a.substring(i,i+1)) < Integer.parseInt(b.substring(i,i+1))){
    //					flag = 1;
    //					t = flag*Dec + Integer.parseInt(a.substring(i,i+1)) - Integer.parseInt(b.substring(i,i+1));		
    	
    //				}else{
    //					flag = 0;
    //					t = Integer.parseInt(a.substring(i,i+1)) - Integer.parseInt(b.substring(i,i+1));	
    //				}
    				
    				str = "" + temp+ str;
    			}
    			
    			//去掉前面的0
    			while(str.length() > 1 && str.charAt(0) == '0'){
    				str = str.substring(1);
    			}
    			
    			return str;
    		}
    		
    		//两个数字串按位加
    		private static String addition(String a,String b){
    			int lenA = a.length();
    			int lenB = b.length();	
    			int len = Math.max(lenA, lenB);
    			if(lenA != lenB){
    				a = formatNum(a,len);
    				b = formatNum(b,len);
    			}
    			String str = "";
    			//进位,用t存储
    			int flag = 0;
    			
    			//从后往前按位相加
    			for(int i = len - 1;i >= 0;i--){
    				
    				int t = flag + Integer.parseInt(a.substring(i,i+1)) + Integer.parseInt(b.substring(i,i+1));
    				
    				if(t > 9){
    					flag = 1;
    					t -= 10;
    				}else{
    					flag = 0;
    				}
    				
    				str = "" + t + str;
    			}
    			//最高位是否有进位
    			if(flag != 0){
    				str = "" + flag + str;
    			}
    			
    			return str;
    		}
    		
    		private static String[] dealString(String ac,int len){
    			String[] str = {ac,"0"};
    			if(ac.length() > len){
    				int t = ac.length() - len;
    				str[0] = ac.substring(t);
    				str[1] = ac.substring(0,t);
    			}
    			else{
    				//要保证结果的length与入参len一致,少于则高位补0
    				String result = str[0];
    				for(int i = result.length();i < len;i++){
    					result = "0" + result;
    				}
    				str[0] = result;
    			}
    			return str;
    		}
    		private static String  expOfTwo(int len){
    			int result = 1;
    			for(int i = 0;i < len;i++){
    				result *= 2; 
    			}
    			return result+"";
    		}
    		public static void main(String[] args){
    			//正则表达式,不以0开头的数字串
    			String pat = "^[1-9]\\d*$";
    			Pattern p = Pattern.compile(pat);
    			
    			//获得乘数A
    			System.out.println("请输入乘数A(不以0开头的正整数):");
    			Scanner sc = new Scanner(System.in);
    			String A = sc.nextLine();
    			Matcher m = p.matcher(A);
    			if(!m.matches()){
    				System.out.println("数字不合法!");
    				return;
    			}
    			
    			//获得乘数B
    			System.out.println("请输入乘数B(不以0开头的正整数:");
    			sc = new Scanner(System.in);
    			String B = sc.nextLine();
    			m = p.matcher(B);
    			if(!m.matches()){
    				System.out.println("数字不合法!");
    				return;
    			}
    			
    //		System.out.println(minus("320","139"));
    			System.out.println(A + "*" +B + " = "
    					+ BigIntegerMultiply(A,B));
    //			System.out.println(
    //					 BigIntegerMultiply("1234","5678"));
    					
    		}
    
    }
    

    最后的最后,为了方便自己以后查看,附上原博主的分析:

    大整数乘法,就是乘法的两个乘数比较大,最后结果超过了整型甚至长整型的最大范围,此时如果需要得到精确结果,就不能常规的使用乘号直接计算了。没错,就需要采用分治的思想,将乘数“分割”,将大整数计算转换为小整数计算。

    在这之前,让我们回忆一下小学学习乘法的场景吧。个位数乘法,是背诵乘法口诀表度过的,不提也罢;两位数乘法是怎么做的呢?现在就来一起回忆下12*34吧:
       3  4  (是不是很多小朋友喜欢将大的整数作为被乘数的,呵呵)
     *1  2 
    ---------
       6  8
    3 4
    ---------
    4 0  8

    接下来就是找规律了。其实大家多做几个两位数的乘法,都会发现这个规律:AB * CD = AC (AD+BC) BD 。没错,这里如果BD相乘超过一位数,需要进位(这里二四得八,没有进位);(AD+BC+低位进位)如果超过一位数,需要进位(就像刚才的3*1,最后+1得4的操作)。

    到这里可以看出,我们任意位数的整数相乘,最终都是可以转化为两位数相乘。当然,不同位的两位数乘的结果,最后应该如何拼接呢?这需要我们来找下更深层次的规律了。这下来个四位数的乘法,找找感觉:
                 1  2  3  4
              *  5  6  7  8
    ------------------------
                  9  8  7  2
              8  6  3  8
          7  4  0  4
     6  1  7  0
    ------------------------
     7  0  0  6  6  5  2

    这个结果看起来也没什么特别的,如果按照我们分治的思想,转换为两位数相乘,之间能否有些关系呢?
    1234分为 12(高位)和34(低位);5678分为56(高位)和78(低位)
    高位*高位结果:12*56=672
    高位*低位+低位*高位:12*78+34*56=936+1094=2840
    低位*低位结果:34*78=2652

    这里要拼接了。需要说明的是,刚才我们提到两位数分解成一位数相乘的规则:超过一位数,需要进位。同理(这里就不证明了),两位数乘以两位数,结果超过两位数,也要进位。
    从低位开始:低两位:2652,26进位,低位保留52;中间两位,2840+26(低位进位)=2866,28进位,中位保留66;高位,672+28(进位)=700,7进位,高位保留00。再往上就没有了,现在可以拼接起来:最高位进位7,高两位00,中位66,低位52,最后结果:7006652。

    规律终于找到了!任意位数(例如N位整数相乘),都可以用这种思想实现:低位保留N位数字串,多余高位进位;高位要加上低位进位,如果超过N位,依然只保留N位,高位进位。(如果是M位整数乘以N位整数怎么办?高位补0,凑成一样位数的即可,不赘述。)

    分治的规律找到了,接下来就是具体实现的思想了。
    没啥新花样,依然是递归思想(这里为了简化,就不递归到两位数相乘了,4位数相乘,计算机还是能够得到精确值的):
    1. 如果两个整数M和N的长度都小于等于4位数,则直接返回M*N的结果的字符串形式。
    2. 如果如果M、N长度不一致,补齐M高位0(不妨设N>M),使都为N位整数。
    3. N/2取整,得到整数的分割位数。将M、N拆分成m1、m2,n1,n2。
    4. 将m1、n1;m2、n1;m1、n2;m2、n2递归调用第1步,分别得到结果AC(高位)、BC(中位)、AD(中位)、BD(低位)。
    5. 判断BD位是否有进位bd,并截取bd得到保留位BD';判断BC+AD+bd是否有进位abcd,并截取进位得到保留位ABCD';判断AC+abcd是否有进位ac,并截取进位得到保留位AC'。
    6. 返回最终大整数相乘的结果:ac AC' ABCD' BD'。

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

    千次阅读 2016-11-15 16:30:04
    大整数乘法:就是乘法的两个乘数比较大,最后结果超过了整型甚至长整型的最大范围,此时如果需要得到精确结果,就不能常规的使用乘号直接计算了。没错,就需要采用分治的思想,将乘数“分割”,将大整数计算转换为小...

    大整数乘法:就是乘法的两个乘数比较大,最后结果超过了整型甚至长整型的最大范围,此时如果需要得到精确结果,就不能常规的使用乘号直接计算了。没错,就需要采用分治的思想,将乘数“分割”,将大整数计算转换为小整数计算。

    可以通过列表的形式来进行大整数的乘法,通过数组来保存列表中的数据。结合http://blog.csdn.net/tjsinor2008/article/details/5625849

    计算8765*234的结果:
    (1)
    这里写图片描述
    (2)
    这里写图片描述
    (3)
    这里写图片描述

    最后算出的结果即为2051010。
    根据以上思路 就可以编写C程序了,再经分析可得:

    1,一个m位的整数与一个n位的整数相乘,乘积为m+n-1位或m+n位。

    2,程序中,用三个字符数组分别存储乘数,被乘数与乘积。由第1点分析知,存放乘积的字符数组饿长度应不小于存放乘数与被乘数的两个数组的长度之和。

    3,可以把第二步“计算填表”与第三四步“累加进位”放在一起完成,可以节省存储表格2所需的空间。

    4,程序关键部分是两层循环,内层循环累计一数组的和,外层循环处理保留的数字和进位。

    效率的提升:
    当然在计算生成这个二维表时,不必一位一位的乘,而可以三位三位的乘;在累加时也是满1000进位。这样,我们计算m位整数乘以n位整数,只需要进行m*n/9次乘法运算,再进行约(m+n)/3次加法运算和(m+n)/3次去摸运算。总体看来,效率是前一种算法的9倍。
    有人可能会想:既然能用三位三位的乘,为什么不能4位4位的乘,甚至5位。听我解来:本算法在累加表中斜线间的数字时,如果用无符号长整数(范围0至~4294967295)作为累加变量,在最不利的情况下(两个乘数的所有数字均为9),能够累加约4294967295/(999*999)=4300次,也就是能够准确计算任意两个约不超过12900(每次累加的结果“值”三位,故4300*3=12900)位的整数相乘。如果4位4位地乘,在最不利的情况下,能过累加月4294967295/(9999*9999)=43次,仅能够确保任意两个不超过172位的整数相乘,没什么实用价值,更不要说5位了。

    下面用Java实现该算法。

    package com.example;
    import java.util.Scanner;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;
    
    
    /**
     * 大整数乘法
     * @author 
     *
     */
    public class 大整数乘法
    {
    
        //规模只要在这个范围内就可以直接计算了
        private final static int SIZE = 4;
    
        // 此方法要保证入参len为X、Y的长度最大值
        private static String bigIntMultiply(String X, String Y, int len)
        {
            // 最终返回结果
            String str = "";
            // 补齐X、Y,使之长度相同
            X = formatNumber(X, len);
            Y = formatNumber(Y, len);
    
            // 少于4位数,可直接计算
            if (len <= SIZE)
            {
                return "" + (Integer.parseInt(X) * Integer.parseInt(Y));
            }
    
            // 将X、Y分别对半分成两部分
            int len1 = len / 2;
            int len2 = len - len1;
            String A = X.substring(0, len1);
            String B = X.substring(len1);
            String C = Y.substring(0, len1);
            String D = Y.substring(len1);
    
            // 乘法法则,分块处理
            int lenM = Math.max(len1, len2);
            String AC = bigIntMultiply(A, C, len1);
            String AD = bigIntMultiply(A, D, lenM);
            String BC = bigIntMultiply(B, C, lenM);
            String BD = bigIntMultiply(B, D, len2);
    
            // 处理BD,得到原位及进位
            String[] sBD = dealString(BD, len2);
    
            // 处理AD+BC的和
            String ADBC = addition(AD, BC);
            // 加上BD的进位
            if (!"0".equals(sBD[1]))
            {
                ADBC = addition(ADBC, sBD[1]);
            }
    
            // 得到ADBC的进位
            String[] sADBC = dealString(ADBC, lenM);
    
            // AC加上ADBC的进位
            AC = addition(AC, sADBC[1]);
    
            // 最终结果
            str = AC + sADBC[0] + sBD[0];
    
            return str;
        }
    
        // 两个数字串按位加
        private static String addition(String ad, String bc)
        {
            // 返回的结果
            String str = "";
    
            // 两字符串长度要相同
            int lenM = Math.max(ad.length(), bc.length());
            ad = formatNumber(ad, lenM);
            bc = formatNumber(bc, lenM);
    
            // 按位加,进位存储在temp中
            int flag = 0;
    
            // 从后往前按位求和
            for (int i = lenM - 1; i >= 0; i--)
            {
                int t =
                    flag + Integer.parseInt(ad.substring(i, i + 1))
                        + Integer.parseInt(bc.substring(i, i + 1));
    
                // 如果结果超过9,则进位当前位只保留个位数
                if (t > 9)
                {
                    flag = 1;
                    t = t - 10;
                }
                else
                {
                    flag = 0;
                }
    
                // 拼接结果字符串
                str = "" + t + str;
            }
            if (flag != 0)
            {
                str = "" + flag + str;
            }
            return str;
        }
    
        // 处理数字串,分离出进位;
        // String数组第一个为原位数字,第二个为进位
        private static String[] dealString(String ac, int len1)
        {
            String[] str = {ac, "0"};
            if (len1 < ac.length())
            {
                int t = ac.length() - len1;
                str[0] = ac.substring(t);
                str[1] = ac.substring(0, t);
            }
            else
            {
                // 要保证结果的length与入参的len一致,少于则高位补0
                String result = str[0];
                for (int i = result.length(); i < len1; i++)
                {
                    result = "0" + result;
                }
                str[0] = result;
            }
            return str;
        }
    
        // 乘数、被乘数位数对齐
        private static String formatNumber(String x, int len)
        {
            while (len > x.length())
            {
                x = "0" + x;
            }
            return x;
        }
    
        //测试桩
        public static void main(String[] args)
        {
            // 正则表达式:不以0开头的数字串
            String pat = "^[1-9]\\d*$";
            Pattern p = Pattern.compile(pat);
    
            // 获得乘数A
            System.out.println("请输入乘数A(不以0开头的正整数):");
            Scanner sc = new Scanner(System.in);
            String A = sc.nextLine();
            Matcher m = p.matcher(A);
            if (!m.matches())
            {
                System.out.println("数字不合法!");
                return;
            }
    
            // 获得乘数B
            System.out.println("请输入乘数B(不以0开头的正整数):");
            sc = new Scanner(System.in);
            String B = sc.nextLine();
            m = p.matcher(B);
            if (!m.matches())
            {
                System.out.println("数字不合法!");
                return;
            }
            System.out.println(A + " * " + B + " = "
                + bigIntMultiply(A, B, Math.max(A.length(), B.length())));
        }
    }
    

    运行结果:
    这里写图片描述

    http://blog.csdn.net/ydx115600497/article/details/53172122

    展开全文
  • 二进制的大整数乘法

    2011-11-22 22:30:47
    设计二进制的大整数乘法,要求利用分治的思想编写递归算法,并可以实现多位数(位数n是2的整数幂)的乘法(利用数组实现),给出程序的正确运行结果。
  • 大整数乘法求解

    2015-09-29 08:18:27
    输入两大整数(都是200位内 非负 没前导零) 求其相乘 没看出什么问题 提交网站却显示WA 求点拨
  • 分治法实现大整数乘法

    千次阅读 2011-05-11 21:49:00
    前言:前几天老师让我们利用分治法实现大整数乘法,想了好久,感觉网上提供的利用分治法实现大整数乘法的方式不太对,因此决定自己写段代码试试,好在勉强完成,现在共享出来,希望志同道合的朋友闲暇之余一起改进...

    前言:前几天老师让我们利用分治法实现大整数乘法,想了好久,感觉网上提供的利用分治法实现大整数乘法的方式不太对,因此决定自己写段代码试试,好在勉强完成,现在共享出来,希望志同道合的朋友闲暇之余一起改进完善其中的不足或冗余之处!

    注:看到有网友问我为什么用其它的方式实现大整数乘法(特别是位数比较多的时候)要比我写的这个分治法快很多,我解释一下:实在抱歉,让大家见笑了。的确有很多方法实现大整数乘法,我这里当时只是为了完成用分治法的实现功能。如果朋友们有更好的用分治法实现的方式(记得是实现无限长度的大整数乘法)而且是效率比较高的,还望不吝赐教,谢谢。

     

    下面程序关于分治法和大整数乘法的具体解释,由于内容比较多,所以我把老师给我们的PPT上传上来了,感兴趣的读者可以到下面的地址去下载(免费的,呵呵)。

    http://download.csdn.net/source/3271129

     



    #include <iostream> 

    #include <sstream> 

    #include <string> 

     

    using namespace std; 

     

    //string类型转换成int类型

    int string_to_num(string k)//string字符串变整数型例如str="1234",转换为整数的1234. 

        int back; 

        stringstream instr(k); 

     

        instr>>back; 

     

        return back; 

     

     

    //整形数转换为string类型

    string num_to_string(int intValue)

    {

    string result;

    stringstream stream;

    stream << intValue;//将int输入流

    stream >> result;//从stream中抽取前面放入的int值

    return result;

    }

     

    //在字符串str前添加s个零

    string stringBeforeZero(string str,int s)

    {

    for(int i=0;i<s;i++)

    {

    str.insert(0,"0");

    }

    return str;

    }

     

    //两个大整数字符串相加,超出计算机表示范围的数也能实现相加(本函数可以实现大整数加法运算)

    string stringAddstring(string str1,string str2)

    {

    //假定str1和str2是相等的长度,不相等时在前面自动补零,使两个字符串长度相等

    if (str1.size() > str2.size()) 

    {

    str2 = stringBeforeZero(str2,str1.size() - str2.size());

    }else if (str1.size() < str2.size()) 

    {

    str1 = stringBeforeZero(str1,str2.size() - str1.size());

    }

     

    string result;

    int flag=0;//前一进位是否有标志,0代表无进位,1代表有进位

    for(int i=str1.size()-1;i>=0;i--)

    {

    int c = (str1[i] - '0') + (str2[i] - '0') + flag;//利用ASCII码对字符进行运算,这里加上flag代表的是:当前一位有进位时加1,无进位时加0

    flag = c/10;//c大于10时,flag置为1,否则为0

    c %= 10;//c大于10时取模,否则为其本身

     

    result.insert(0,num_to_string(c));//在result字符串最前端插入新生成的单个字符

    }

    if (0 != flag) //最后一为(最高位)判断,如果有进位则再添一位

    {

    result.insert(0,num_to_string(flag));

    }

     

    return result;

    }

     

     

    /*两个大整数字符串相减,超出计算机表示范围的数也能实现相减(在这里比较特殊,第一个参数一定大于第二个参数,

    因为:a1*b0+a0*b1=(a1+a0)*(b1+b0)-(a1*b1+a0*b0) > 0 ,所以(a1+a0)*(b1+b0) > (a1*b1+a0*b0)

    这个函数的两个参数,第一个代表的其实就是(a1+a0)*(b1+b0),第二个代表的其实就是(a1*b1+a0*b0)

    所以本函数里不用考虑最终得到结果为负数的情况,至于计算有关大整数负数相乘的问题可以通过其他途径判断

    */

    string stringSubtractstring(string str1,string str2)

    {

    //对传进来的两个数进行修剪,如果前面几位有0则先去掉,便于统一处理

    while ('0' == str1[0]&&str1.size()>1)

    {

    str1=str1.substr(1,str1.size()-1);

    }

    while ('0' == str2[0]&&str2.size()>1)

    {

    str2=str2.substr(1,str2.size()-1);

    }

    //使两个字符串长度相等

    if (str1.size() > str2.size()) 

    {

    str2 = stringBeforeZero(str2,str1.size() - str2.size());

    }

     

    string result;

    for(int i=str1.size()-1;i>=0;i--)

    {

    int c = (str1[i] - '0') - (str2[i] - '0');//利用ASCII码进行各位减法运算

    if (c < 0) //当不够减时向前一位借位,前一位也不够位时再向前一位借位,依次如下

    {

    c +=10;

    int prePos = i-1; 

    char preChar = str1[prePos];

    while ('0' == preChar) 

    {

    str1[prePos]='9';

    prePos -= 1;

    preChar = str1[prePos];

    }

    str1[prePos]-=1;

    }

     

    result.insert(0,num_to_string(c));//在result字符串最前端插入新生成的单个字符

    }

    return result;

    }

     

     

    //在字符串str后跟随s个零

    string stringFollowZero(string str,int s)

    {

    for(int i=0;i<s;i++)

    {

    str.insert(str.size(),"0");

    }

    return str;

    }

     

    //分治法大整数乘法实现函数

    string IntMult(string x,string y)//递归函数

    //对传进来的第一个数进行修剪,如果前面几位有0则先去掉,便于统一处理

    while ('0' == x[0]&&x.size()>1)

    {

    x=x.substr(1,x.size()-1);

    }

    //对传进来的第二个数进行修剪,如果前面几位有0则先去掉,便于统一处理

    while ('0' == y[0]&&y.size()>1)

    {

    y=y.substr(1,y.size()-1);

    }

    /*这里的f变量代表在两个数据字符串长度不想等或者不是2的指数倍的情况下,所要统一的长度,这样做是为了让数据长度为2的n次方

     的情况下便于利用分治法处理

    */

    int f=4;

    /*当两字符串中有任意一个字符串长度大于2时都要通过与上面定义的f值进行比较,使其达到数据长度为2的n次方,实现方式是在前面

     补0,这样可以保证数据值大小不变

    */

    if (x.size()>2 || y.size()>2) 

    {

    if (x.size() >= y.size()) //第一个数长度大于等于第二个数长度的情况

    {

    while (x.size()>f) //判断f值

    {

    f*=2;

    }

    if (x.size() != f) 

    {

    x = stringBeforeZero(x,f-x.size());

    y = stringBeforeZero(y,f-y.size());

    }

    }else//第二个数长度大于第一个数长度的情况

    {

    while (y.size()>f) //判断f值

    {

    f*=2;

    }

    if (y.size() != f) 

    {

    x = stringBeforeZero(x,f-x.size());

    y = stringBeforeZero(y,f-y.size());

    }

    }

    }

     

    if (1 == x.size()) //数据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据是因为前面对数据修剪过)

    {

    x=stringBeforeZero(x,1);

    }

    if (1 == y.size()) //数据长度为1时,在前面补一个0(这里之所以会出现长度为1的数据是因为前面对数据修剪过)

    {

    y=stringBeforeZero(y,1);

    }

     

    if (x.size() > y.size()) //最后一次对数据校正,确保两个数据长度统一

    {

    y = stringBeforeZero(y,x.size()-y.size());

    }

    if (x.size() < y.size()) //最后一次对数据校正,确保两个数据长度统一

    {

    x = stringBeforeZero(x,y.size()-x.size());

    }

     

        int s = x.size(); 

        string a1,a0,b1,b0; 

     

        if( s > 1) 

        { 

            a1 = x.substr(0,s/2); 

     

            a0 = x.substr(s/2,s-1); 

     

            b1 = y.substr(0,s/2); 

     

            b0 = y.substr(s/2,s-1); 

        } 

     

    string result;

     

        if( s == 2) //长度为2时代表着递归的结束条件

        { 

            int na = string_to_num(a1); 

            int nb = string_to_num(a0);  

            int nc = string_to_num(b1); 

            int nd = string_to_num(b0);

            result = num_to_string((na*10+nb) * (nc*10+nd)); 

        } 

        else{ //长度不为2时利用分治法进行递归运算

    /***************************************************

    小提示:

    c = a*b = c2*(10^n) + c1*(10^(n/2)) + c0;

    a = a1a0 = a1*(10^(n/2)) + a0;

    b = b1b0 = b1*(10^(n/2)) + b0;

    c2 = a1*b1;  c0 = a0*b0;

    c1 = (a1 + a0)*(b1 + b0)-(c2 + c0);

    ****************************************************/

    string c2 = IntMult(a1,b1);// (a1 * b1)

     

    string c0 = IntMult(a0,b0);// (a0 * b0)

     

    string c1_1 = stringAddstring(a1,a0);// (a1 + a0)

     

    string c1_2 = stringAddstring(b1,b0);// (b1 + b0)

     

    string c1_3 = IntMult(c1_1,c1_2);// (a1 + a0)*(b1 + b0)

     

    string c1_4 = stringAddstring(c2,c0);// (c2 + c0)

     

    string c1=stringSubtractstring(c1_3,c1_4);// (a1 + a0)*(b1 + b0)-(c2 + c0)

    string s1=stringFollowZero(c1,s/2);// c1*(10^(n/2))

     

    string s2=stringFollowZero(c2,s);// c2*(10^n)

     

    result = stringAddstring(stringAddstring(s2,s1),c0);// c2*(10^n) + c1*(10^(n/2)) + c0

        } 

     

        return result; 

     

     

    void main() 

    int f=1;

    while (1 == f)

    {

    string A,B,C,D; 

    string num1,num2; 

    string r;

    cout<<"大整数乘法运算(分治法实现)"<<endl;

    cout<<"请输入第一个大整数(任意长度):";

    cin>>num1;

    int i=0;

    //判断第一个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入

    for(i=0 ;i < num1.size();i++)

    {

    if (num1[i]<'0' || num1[i]>'9') 

    {

    cout<<"您输入的数据不合法,请输入有效的整数!"<<endl;

    cin>>num1;

    i=-1;

    }

    }

     

    cout<<"请输入第二个大整数(任意长度):";

    cin>>num2;

    //判断第二个输入的数据是否合法,当字符串中包含非数字字符时提示用户重新输入

    for(i=0 ;i < num2.size();i++)

    {

    if (num2[i]<'0' || num2[i]>'9') 

    {

    cout<<"您输入的数据不合法,请输入有效的整数!"<<endl;

    cin>>num2;

    i=-1;

    }

    }

     

    r=IntMult(num1,num2); 

     

    //对求得的结果进行修剪,去掉最前面的几个0

    while ('0' == r[0]&&r.size()>1)

    {

    r=r.substr(1,r.size()-1);

    }

    cout<<"两数相乘结果为:"<<endl;

    cout<<num1<<" "<<"*"<<" "<<num2<<" "<<"="<<" "<<r<<endl<<endl;     

    }

     

    }

    //本程序转载请说明出处,谢谢,非常感谢大家提出宝贵的建议!










     

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

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

    2018-10-01 11:38:29
    大整数乘法C语言实现 希望能帮到你们 #include &lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;algorithm&gt; #include &lt;cstring&gt; #define MAX 210 using ...
  • Java实现大整数乘法

    千次阅读 2018-11-17 11:12:13
    请设计一个有效的算法,可以进行两个n位大整数乘法运算 1 最暴力的方法:O(n^2) 2 我们采用分而治之的思想 将X和Y按如下方法分成两部分 那么 X = A*10^(n/2) + B Y = C*10^(n/2) + D X*Y = ...
  • 采用数组实现的200位大整数乘法,代码十分简洁,不到100行。对c语言学习很有帮助~
  • 大整数乘法 C++ ACM

    2013-10-23 17:36:23
    大整数乘法 C++ ACM 在一些应用中,特别是现在的密码学中,常常需要用超过100位的整数来做乘法,以此来对数据加密。 现在有两个小于等于100位的大整数a和b(位数相同),请写程序计算出这两个大整数乘积的结果。 ...
  • Python 实现大整数乘法算法

    万次阅读 多人点赞 2019-09-16 01:09:27
    我们平时接触的长乘法,按位相乘,是一种时间复杂度为 O(n ^ 2) 的算法。今天,我们来介绍一种时间复杂度为 O (n ^ log 3) 的大整数乘法(log 表示以 ...
  • 大整数乘法实现思路

    千次阅读 2018-07-03 12:02:33
    1、大整数乘法的实现思路(一):模拟手工列竖式计算两个大整数的乘积 模拟手工计算两个整数相乘的过程:逐位相乘,错位累加,最后进位。以1235789×64523511235789×64523511235789\times6452351为例: 相乘的...
  • 大整数乘法的Karatsuba算法实现

    千次阅读 2013-10-14 17:03:34
    Karatsuba's multiplication algorithm 大整数的快速乘法实现,使用递归。附上原代码。  理论上应该计算速度很快,但是在测试中,内存消耗巨大,速度也较慢,还希望大家帮帮忙,优化一下。和FFT_MULT相比,相差近...
  • c++解决大整数乘法

    千次阅读 2018-02-13 17:29:26
    c++解决大整数乘法问题描述:求两个不超过200位的非负整数的积输入数据:输入有两行,每行是一个不超过200位的非负整数,没有多余的前导0。输出要求:输出只一行,即相乘后的结果。结果里不能有多余的前导0,即如果...
  • 利用快速傅里叶变换FFT实现了大整数乘法。时间复杂度从O(n2)降低到了O(nlgn) 利用快速傅里叶变换FFT实现了大整数乘法。时间复杂度从O(n2)降低到了O(nlgn) 利用快速傅里叶变换FFT实现了大整数乘法。时间复杂度从O...
  • int main(){ int texttimes = TEXT_TIMES; m = 50; while(texttimes--){ int size,choice; cout cin>>size; cout cin>>choice; double random(double,double); srand(unsigned(time(0)));...double sumtime
  • 大整数乘法算法

    万次阅读 2012-07-11 23:38:34
    一 转换为二进制求,推导出的公式适合十进制计算 设X和Y都是n位的二进制整数,现在要计算它们的乘积XY。...下面我们用分治法来设计一个更有效的大整数乘积算法。   图6-3 大整数X和Y的分段
  • C++实现大整数乘法

    千次阅读 2011-05-08 19:11:00
    //大整数乘法 #include #include using namespace std; void MUL_max(string a,int la,string b,int lb,int **c);//相乘函数 void ADD_max(int * d,int **c,int la,int lb);//相加函数 char * ZhuanH(string...

空空如也

1 2 3 4 5 ... 20
收藏数 69,679
精华内容 27,871
关键字:

ultragrid 整数验证