- 浏览: 34418 次
- 性别:
- 来自: 北京
最新评论
-
cjf068:
LuckYes 写道楼主如果用最小堆的话,最好用调整堆的方式来 ...
求最小的k个数问题 -
LuckYes:
楼主如果用最小堆的话,最好用调整堆的方式来构建堆,这样效率更高 ...
求最小的k个数问题 -
cjf068:
这个算法的基本思路, ...
大数乘法 -
liujunsong:
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算 ...
大数乘法 -
shuidexiongdi:
去年我也写了一个http://shuidexiongdi.it ...
大数乘法
论坛看到的一个面试题,实现任意大整数字符串相乘,返回结果字符串
如何验证?这个还真不知道,字符串检查到时必须
package org.jf.alg; /** * * 大数乘法 * @author junfeng.chen * */ public class BigIntegerMultipl { /** * * @param s1 整型乘数字符串 * @param s2 整型乘数字符串 * @return 整型字符串结果 * * s1=a[1]a[2]a[3]....a[n] * s2=b[1]b[2]b[3]....b[n] * 分别将两个字符串拆分,得到两个字符数组 * char[] charArray1={a[1],a[2]....a[n]} * char[] charArray2={b[1],b[2]....b[n]} * * * 乘法步骤: * 1. a[1]*{b[1],b[2],b[3]...b[n]}-->得到一个字符数组 array1 * 2. a[1]*{b[2],b[3],b[4],...b[n]}-->得到字符数组 array2 * array1 与 array2 错一位按位求和 * array1[0] array1[1] array1[2] ...array1[n] * array2[0] array2[1] ...array2[n-1] array2[n] * --->新的结果数组 array3 */ public static String multiplie(String s1,String s2)// { int prex = 1; if(s1.charAt(0)>'9'||s1.charAt(0)<'0') { if(s1.charAt(0)=='-') prex *= -1; else if(s1.charAt(0)!='+') throw new RuntimeException("Illeagle Argumets"); s1=s1.substring(1); } if(s2.charAt(0)>'9'||s2.charAt(0)<'0') { if(s2.charAt(0)=='-') prex *= -1; else if(s2.charAt(0)!='+') throw new RuntimeException("Illeagle Argumets"); s2=s2.substring(1); } if(!s1.matches("\\d+")||!s2.matches("\\d+")) throw new RuntimeException("Illeagle Argumets"); char [] array1=new char[s1.length()]; char [] array2= new char[s2.length()]; for(int i=0;i<s1.length();i++) { array1[i] = s1.charAt(s1.length()-i-1); } for(int i=0;i<s2.length();i++) { array2[i] = s2.charAt(s2.length()-i-1); } char [] rs1 = null; for(int i=0;i<array2.length;i++) { char result[] = new char[array1.length+1]; int extr = 0;//进位 int m2 = Integer.parseInt(array2[i]+""); int j=0; for(;j<array1.length;j++) { int m1 = Integer.parseInt(array1[j]+""); int r = m1*m2+extr; result[j] = (char)(48+(r%10)); extr = r/10; } result[j] = (char)(48+extr); extr = 0; if(i==0) rs1 = result; else//rs1 与 result 错i位按位求和 { char rs2[] = new char[result.length+i+1]; rs2[result.length+i]='0'; rs2[result.length+i-1]='0'; for(int k=0;k<i;k++) { rs2[k] = rs1[k]; } int m = i; for(int n=0;n<result.length;n++,m++) { int x2 = Integer.parseInt(result[n]+""); int x1 = 0; if(m<rs1.length) { x1 = Integer.parseInt(rs1[m]+""); } int r = x1+x2+extr; extr = r/10; rs2[m] = (char)(48+r%10); } for(int l=m+1;l<rs2.length;l++) { rs2[l] = (char)48; } rs1 = rs2; } } String str = ""; int i = rs1.length-1; while(rs1[i]=='0') { i--; } for(;i>=0;i--) { str = str+rs1[i]; } if(prex==-1) str='-'+str; return str; } public static void main(String args[]) { System.out.println(BigIntegerMultipl.multiplie("c123", "c123")); System.out.println(BigIntegerMultipl.multiplie("12","99")); System.out.println(BigIntegerMultipl.multiplie("-345","987")); System.out.println(BigIntegerMultipl.multiplie("3450","210")); System.out.println(BigIntegerMultipl.multiplie("9999999999","121212121212121212121212129999999991919191929293949595959")); } }
评论
7 楼
cjf068
2012-02-13
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算转换成多次的加法运算。
简单来说,假设第一个数是m位,第二个数是n位,最后计算出来就需要m*n次的乘法,然后再相加。
这个算法是相当粗糙的。
对于这个问题,实际上可以做这样的分解。
就是讲两个大数的乘法,转换成几个相对小数的乘法,然后再相加。但这里的小数是相对的小数,不能直接拆分到一个字符一个字符来计算,这样的算法效率太低了。
举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果,得到一个相当于99乘法表的乘法计算结果。
这时如果要计算两个10位数的乘法,就可以将两个10位数的乘法计算,转换成4个5位数的乘法计算,以及3次相加结果。那么在这种情况下,因为5位数的乘法已经计算出来了,不需要重新计算,查找一下结果就可以了。整个计算的效率才能得到提升。
明白你的意思,谢谢,我之前想过,这里只是简单实现了一下,没考虑性能问题,有时间再优化一下,事实上,存储也可以用链表做
简单来说,假设第一个数是m位,第二个数是n位,最后计算出来就需要m*n次的乘法,然后再相加。
这个算法是相当粗糙的。
对于这个问题,实际上可以做这样的分解。
就是讲两个大数的乘法,转换成几个相对小数的乘法,然后再相加。但这里的小数是相对的小数,不能直接拆分到一个字符一个字符来计算,这样的算法效率太低了。
举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果,得到一个相当于99乘法表的乘法计算结果。
这时如果要计算两个10位数的乘法,就可以将两个10位数的乘法计算,转换成4个5位数的乘法计算,以及3次相加结果。那么在这种情况下,因为5位数的乘法已经计算出来了,不需要重新计算,查找一下结果就可以了。整个计算的效率才能得到提升。
liujunsong 写道
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算转换成多次的加法运算。
简单来说,假设第一个数是m位,第二个数是n位,最后计算出来就需要m*n次的乘法,然后再相加。
这个算法是相当粗糙的。
对于这个问题,实际上可以做这样的分解。
就是讲两个大数的乘法,转换成几个相对小数的乘法,然后再相加。但这里的小数是相对的小数,不能直接拆分到一个字符一个字符来计算,这样的算法效率太低了。
举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果,得到一个相当于99乘法表的乘法计算结果。
这时如果要计算两个10位数的乘法,就可以将两个10位数的乘法计算,转换成4个5位数的乘法计算,以及3次相加结果。那么在这种情况下,因为5位数的乘法已经计算出来了,不需要重新计算,查找一下结果就可以了。整个计算的效率才能得到提升。
简单来说,假设第一个数是m位,第二个数是n位,最后计算出来就需要m*n次的乘法,然后再相加。
这个算法是相当粗糙的。
对于这个问题,实际上可以做这样的分解。
就是讲两个大数的乘法,转换成几个相对小数的乘法,然后再相加。但这里的小数是相对的小数,不能直接拆分到一个字符一个字符来计算,这样的算法效率太低了。
举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果,得到一个相当于99乘法表的乘法计算结果。
这时如果要计算两个10位数的乘法,就可以将两个10位数的乘法计算,转换成4个5位数的乘法计算,以及3次相加结果。那么在这种情况下,因为5位数的乘法已经计算出来了,不需要重新计算,查找一下结果就可以了。整个计算的效率才能得到提升。
明白你的意思,谢谢,我之前想过,这里只是简单实现了一下,没考虑性能问题,有时间再优化一下,事实上,存储也可以用链表做
6 楼
liujunsong
2012-02-12
这个算法的基本思路,是小学3年级的 算法,就是简单的把乘法运算转换成多次的加法运算。
简单来说,假设第一个数是m位,第二个数是n位,最后计算出来就需要m*n次的乘法,然后再相加。
这个算法是相当粗糙的。
对于这个问题,实际上可以做这样的分解。
就是讲两个大数的乘法,转换成几个相对小数的乘法,然后再相加。但这里的小数是相对的小数,不能直接拆分到一个字符一个字符来计算,这样的算法效率太低了。
举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果,得到一个相当于99乘法表的乘法计算结果。
这时如果要计算两个10位数的乘法,就可以将两个10位数的乘法计算,转换成4个5位数的乘法计算,以及3次相加结果。那么在这种情况下,因为5位数的乘法已经计算出来了,不需要重新计算,查找一下结果就可以了。整个计算的效率才能得到提升。
简单来说,假设第一个数是m位,第二个数是n位,最后计算出来就需要m*n次的乘法,然后再相加。
这个算法是相当粗糙的。
对于这个问题,实际上可以做这样的分解。
就是讲两个大数的乘法,转换成几个相对小数的乘法,然后再相加。但这里的小数是相对的小数,不能直接拆分到一个字符一个字符来计算,这样的算法效率太低了。
举个例子来说吧。假设我们已经可以计算出所有5位数的乘法结果,得到一个相当于99乘法表的乘法计算结果。
这时如果要计算两个10位数的乘法,就可以将两个10位数的乘法计算,转换成4个5位数的乘法计算,以及3次相加结果。那么在这种情况下,因为5位数的乘法已经计算出来了,不需要重新计算,查找一下结果就可以了。整个计算的效率才能得到提升。
5 楼
shuidexiongdi
2012-02-08
去年我也写了一个
http://shuidexiongdi.iteye.com/admin/blogs/1144176
http://shuidexiongdi.iteye.com/admin/blogs/1144176
4 楼
cjf068
2012-02-07
wait10000y 写道
要严谨,先判断字符串是否符合要求,结尾还要验证结果是否正确的,最后再分析一下可行性...
如何验证?这个还真不知道,字符串检查到时必须
3 楼
chansman
2012-02-07
大学的时候我也弄过,但是除法没弄出来.
2 楼
wait10000y
2012-02-07
要严谨,先判断字符串是否符合要求,结尾还要验证结果是否正确的,最后再分析一下可行性...
1 楼
chasingdeer
2012-02-07
直接用BigDecimal不就行了
发表评论
-
中文数字到阿拉伯数字转换
2012-04-24 10:18 1875昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 956package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 735插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 862简单日期计算类: 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 2006已知int数组a按升序排列,要求用线性时间复杂的算法,判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1304求最大子数组之和的线性解法:本算法受编程珠玑中提示而得 /** ... -
LRUCache
2012-03-15 14:35 1656MyLRUCache 缓存类 package org.jf ... -
求变位词组合
2012-03-13 22:53 853public class CharComp { ... -
计算24点
2012-03-13 21:49 1260计算n个数的全排列 package org.jf.alg. ... -
表达式计算
2012-03-10 23:02 906中缀表达式转后缀 后缀表达式计算 支持整型 分数计算,只支持 ... -
Many2One缓冲
2012-03-06 12:35 932多线程并发操作中,为了尽量减少同步锁的开销,一般都会尽可能减少 ... -
红黑树
2012-03-03 21:47 1229红黑树 规则 * 1.每个 ... -
行文件分组统计
2012-03-02 22:57 831有些情况下,对于一个结构化的以行为记录的文本文件,需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1071链表保存键值,由于没有权值策略,简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1419大根堆,可用于优先级队列 package org.jf.a ... -
固定容量二叉堆
2012-02-08 17:26 997固定容量的二叉堆实现,可用于快速求top k 问题。如要求一个 ...
相关推荐
在IT领域,大数乘法是一项基础且重要的计算任务,特别是在加密、数字信号处理和算法设计等场景。本文将深入探讨“C语言-大数乘法”,特别是针对16进制大数乘法以及如何使用unsigned char数组来表示和处理任意长度的...
本项目通过VC++6.0环境实现了大数乘法的算法,这在课程设计和实验教学中是一个典型的问题。这里我们将深入探讨大数乘法的原理、实现方式以及在C++中的应用。 首先,我们要理解什么是大数。在常规的整数类型如int或...
大数乘法是公钥加密中最为核心的计算环节之一,快速实现大数乘法单元也是RSA、ElGamal、全同态等密码体制急需解决的问题之一。目前,基于C 的NTL GMP库函数虽然能在CPU上实现高精度的大数乘法,但其仍不能满足加密对...
大数乘法 用字符串实现大数乘法,大整数乘法,用string类实现
在计算机科学中,大数乘法是处理超过标准整型数据范围的数字乘法操作。在C语言中,由于int、long等基本类型有其数值范围限制,处理大数时通常需要自定义数据结构和算法。这篇内容将深入探讨如何在C语言环境下,使用...
5. **库支持**:许多编程语言如Python、Java、C#等都内置了大数支持,提供了简便的大数乘法函数,例如Python的`*`运算符可以直接用于大数乘法,底层通常会用到上述的高效算法。 在描述中提到的“将该数拆分,进行...
在IT领域,大数乘法是一项基础且重要的计算任务,特别是在加密算法、数学软件和分布式计算等场景中。本文将详细解析如何使用C语言高效地实现大数乘法。 大数乘法通常涉及到超出普通整型变量范围的数值运算。在C语言...
在编程领域,大数乘法运算是一项基础但重要的任务,特别是在需要处理超出普通整型或浮点型数据范围的情况。C#作为一种现代化的面向对象的编程语言,提供了丰富的数据类型和算法支持来处理这种问题。本篇文章将深入...
在处理金融计算、加密算法、数学建模等领域时,经常需要进行大数运算,其中包括大数乘法。本节将详细探讨大数乘法的算法以及相关编程实现。 在传统的计算机中,整数通常由固定长度的位(如32位或64位)表示,这限制...
基于字符串的大数乘法 有效解决大数乘法溢出的问题
用C++写的重载的大数模板 大数加法、大数乘法、大数除法、大数减法 带有注释
Q714586 C语言大数乘法的运算 https://ask.csdn.net/questions/714586
### ACM大数乘法知识点详解 #### 一、引言 在计算机科学中,处理大数运算是一项重要的技能,尤其是在算法竞赛(ACM)中。传统整型数据类型(如`int`, `long long`等)无法直接支持非常大的数字进行计算。例如,当...
任意两个大数乘法,理论上可算2G长度的两个数的乘法,C++实现,在VS 2008下编译通过
算法设计,利用c语言实现大数乘法,如需更多帮助,请发邮件至1436125018#qq。com(发送时请把地址中的‘#’换成‘@’)
"数据结构中的大数乘法"这个主题就是关于如何高效地进行大数乘法操作的探讨。 大数乘法在密码学、分布式计算、财务计算、科学计算等领域都有广泛应用。例如,RSA加密算法就依赖于大数的乘法和因数分解。传统的整数...
【大数乘法的GPU加速实现】 大数乘法在密码学中扮演着至关重要的角色,尤其是在公钥加密算法如RSA、ElGamal以及全同态加密等体制中。这些算法通常涉及到大整数的复杂运算,而大数乘法是其中计算量最大的部分之一。...
用java写的动态数组实现的大数乘法.两个大数相乘:利用数组实现,数组a存放大数1的每一位,数组b依次存放大数2的每一位。如:一大数1为3463546,则数组 a[]={3,4,6,3,5,4,6},大数2为:89019 则数组b[]={8,9,0,1,9},...
标题中的“大数乘法”指的是在计算机科学中处理超出普通整型范围的大整数的乘法运算。这种运算在密码学、计算数学、分布式计算等领域广泛应用,例如在RSA加密算法中就需要大数的乘法操作。VC++是微软开发的C++编译器...
### C++大数乘法一般算法详解 #### 算法背景与应用场景 在计算机科学领域,特别是编程竞赛、加密算法、金融计算等场景中,经常需要处理超过标准整型或浮点型变量所能表示的大数。对于这些场景,传统的乘法运算不再...