- 浏览: 33404 次
- 性别:
- 来自: 北京
最新评论
-
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 1847昨天博客上看到一童鞋 ... -
布隆过滤器
2012-04-23 15:39 924package org.jf.alg; import ... -
基本的排序算法
2012-04-21 21:07 711插入排序 选择排序 快速排序 。。。。 后续补充 pack ... -
日期计算
2012-04-19 23:04 830简单日期计算类: 日期大小比较 日期之间天数计算 pack ... -
判断数组中是否存在两个元素之和等于给定数值
2012-04-06 22:58 1947已知int数组a按升序排列,要求用线性时间复杂的算法,判断是否 ... -
求最大子数组之和
2012-04-06 22:51 1274求最大子数组之和的线性解法:本算法受编程珠玑中提示而得 /** ... -
LRUCache
2012-03-15 14:35 1574MyLRUCache 缓存类 package org.jf ... -
求变位词组合
2012-03-13 22:53 823public class CharComp { ... -
计算24点
2012-03-13 21:49 1192计算n个数的全排列 package org.jf.alg. ... -
表达式计算
2012-03-10 23:02 874中缀表达式转后缀 后缀表达式计算 支持整型 分数计算,只支持 ... -
Many2One缓冲
2012-03-06 12:35 902多线程并发操作中,为了尽量减少同步锁的开销,一般都会尽可能减少 ... -
红黑树
2012-03-03 21:47 1174红黑树 规则 * 1.每个 ... -
行文件分组统计
2012-03-02 22:57 802有些情况下,对于一个结构化的以行为记录的文本文件,需要按列分组 ... -
简单LRU缓存实现
2012-02-09 21:12 1051链表保存键值,由于没有权值策略,简单的将当前访问过的节点放到链 ... -
大根堆
2012-02-08 22:23 1387大根堆,可用于优先级队列 package org.jf.a ... -
固定容量二叉堆
2012-02-08 17:26 967固定容量的二叉堆实现,可用于快速求top k 问题。如要求一个 ...
相关推荐
大数乘法是公钥加密中最为核心的计算环节之一,快速实现大数乘法单元也是RSA、ElGamal、全同态等密码体制急需解决的问题之一。目前,基于C 的NTL GMP库函数虽然能在CPU上实现高精度的大数乘法,但其仍不能满足加密对...
大数乘法 用字符串实现大数乘法,大整数乘法,用string类实现
基于字符串的大数乘法 有效解决大数乘法溢出的问题
用C++写的重载的大数模板 大数加法、大数乘法、大数除法、大数减法 带有注释
16进制大数乘法,支持unsigned char 数组数据,任意长度相乘
用VC6.0实现的大数乘法,这是算法设计实验的一个小题目
个人在vc6.0上用C写的大数乘法的程序。
大数乘法
C#编写的大数乘法运算原代码 运行环境VS
Q714586 C语言大数乘法的运算 https://ask.csdn.net/questions/714586
任意两个大数乘法,理论上可算2G长度的两个数的乘法,C++实现,在VS 2008下编译通过
算法设计,利用c语言实现大数乘法,如需更多帮助,请发邮件至1436125018#qq。com(发送时请把地址中的‘#’换成‘@’)
用java写的动态数组实现的大数乘法.两个大数相乘:利用数组实现,数组a存放大数1的每一位,数组b依次存放大数2的每一位。如:一大数1为3463546,则数组 a[]={3,4,6,3,5,4,6},大数2为:89019 则数组b[]={8,9,0,1,9},...
大数相乘,超出整型最大数值时,不能直接进行乘法运算。将该数拆分,进行运算
该段程序使用简短的算法就可完成两个大数相乘的过程
可以高效快速的实现两个大数相乘,可以C运行
算法课实验、大作业
大数在c++编程中常常遇到的问题,尤其是乘法,给出了相应的解法
低效率大数运算类
大数乘法比较简单的数组实现,实现两个大数相乘的结果。给予初学者提供思路