大数相乘 傷城~ 2022-09-30 13:55 208阅读 0赞 ## 一、背景 ## 最近在看算法的时候发现了一个问题,我们都知道方法的形参是要指定类型的,假如有以下方法 public int example(int a,int b){ int c = a+b; return c; } 其中的形参a和形参b的类型是int,我们都知道int类型的数据的取值会限制在一定范围之内,如果我要传入的参数是大于int的取值范围怎么办,有人可能会想到用long,再不够就用long long,但是当传入的参数是大数时,long long类型可能远远不够。 通过冥思苦想和查阅相关资料,终于找到了解决方法,以下是我对大数相乘的学习总结,希望能与大家分享,如有错误,希望大家能够指正,谢谢! 以上提到的取值范围的问题,我们可以通过用字符串来表示参数,这样子我们传入的参数可以在一个非常之大的取值范围之内。因此便有了对大数进行运算的需要,其中包括大数相乘、大数相加、大数相减等等。此篇博文先总结下大数相乘的算法。 ## 二、数字相乘的规律 ## 说到大数相乘,这里先明确几个规律: 1.当两个数相乘时,结果的位数一定是小于或者等于两个数的位数相加,如a(位数为2)和b(位数为3)相乘,结果c的位数一定小于或者等于5(2+3)。 2.假设有a和b相乘,结果为c,则有a的第i位乘以b的第j位,等于c的第i+j位,如下图所示 ![Center][] 假如a=128,b=629,红色的数字表示为第几位(注意是倒过来的)。 如c的第0位为8\*9=72,第1位为2\*9=18,如有重复则旧值和新值相加。 ## 三、具体算法 ## public String BigNumMultip(String bigNum1,String bigNum2){ if(bigNum1==null||bigNum2==null){ return "输入有误"; } if(bigNum1=="0"||bigNum2=="0"){ return "0"; } //将传进来的字符串参数转为字符数组并反转数组 char[] num1 =new StringBuffer(bigNum1).reverse().toString().toCharArray(); char[] num2 =new StringBuffer(bigNum2).reverse().toString().toCharArray(); for(int i=0;i<num1.length;i++){ //以下两个循环使得形参只接受含有“0~9”字符的字符串 if(num1[i]<'0'||num1[i]>'9'){ return "输入的数字不能含有非法字符"; } } for(int i=0;i<num2.length;i++){ if(num2[i]<'0'||num2[i]>'9'){ return "输入的数字不能含有非法字符"; } } int resultLen = num1.length+num2.length; //结果的长度 int[] result = new int[resultLen]; for(int j=0;j<num1.length;j++){ for(int i=0;i<num2.length;i++){ result[i+j] += (int)(num1[j]-'0')*(int)(num2[i]-'0'); } } for(int i=0;i<resultLen-1;i++){ //处理进位 result[i+1] += result[i]/10; result[i] = result[i]%10; } StringBuffer resultStr = new StringBuffer(); for(int i=resultLen-1;i>=0;i--){ resultStr.append(result[i]); } return resultStr.toString(); } 注:以上算法暂不支持负数相乘 [Center]: /images/20220705/3b4abe2436544e36ba0bc56204107728.png
相关 大数相乘 void mul(string a, string b) { int max = 0; int c[1000] = {0}; in r囧r小猫/ 2022年12月04日 08:47/ 0 赞/ 21 阅读
相关 大数相乘 一、背景 最近在看算法的时候发现了一个问题,我们都知道方法的形参是要指定类型的,假如有以下方法 public int example(int a,int b){ 傷城~/ 2022年09月30日 13:55/ 0 赞/ 209 阅读
相关 大数相乘 参考地址:[http://www.cnblogs.com/heyonggang/p/3599857.html][http_www.cnblogs.com_heyonggang_ 悠悠/ 2022年08月20日 06:29/ 0 赞/ 189 阅读
相关 大数相乘 [用分治法实现大数乘法,加法,减法(java实现)][java] 大数乘法即多项式乘法问题,求A(x)与B(x)的乘积C(x),朴素解法的复杂度O 小咪咪/ 2022年08月19日 15:12/ 0 赞/ 184 阅读
相关 大数相乘 无意中看到一个华为面试题,使用代码计算[1234567891011121314151617181920\2019181716151413121110987654321][123 系统管理员/ 2022年08月11日 20:29/ 0 赞/ 194 阅读
相关 大数相乘 题目:请使用代码计算1234567891011121314151617181920\2019181716151413121110987654321。 答: ![复制代码][ Bertha 。/ 2022年08月05日 08:54/ 0 赞/ 205 阅读
相关 大数相乘 在这之前我们先来了解一下Java 中每种基本数据类型所占存储空间的大小。其中 1Byte = 8bit。 <table> <tbody> <tr> <th> 朱雀/ 2022年06月02日 02:36/ 0 赞/ 251 阅读
相关 大数相乘 设X和Y是n位的二进制整数,现在要计算X\Y的结果 将a和b分为两段,每段长均为总长的1/2, ![20180329214901958][] 拼搏现实的明天。/ 2022年05月28日 05:06/ 0 赞/ 215 阅读
相关 大数相乘 题目 编写两个任意位数的大数相乘的程序,给出计算结果。比如: > 题目描述: 输出两个不超过100位的大整数的乘积。 > 输入: 输入两个大整数,如1234567 今天药忘吃喽~/ 2022年05月23日 11:23/ 0 赞/ 336 阅读
相关 大数相乘 def fun(num1,num2): num1 type str num2 type str a = map(int, 落日映苍穹つ/ 2021年10月24日 01:48/ 0 赞/ 329 阅读
还没有评论,来说两句吧...