准备阶段:
准备一个整型数组若无特别说明下文提到的数组都是指该整型数组其维数为str1和str2这两个字符串的长度之和(两数相乘,其乘积的位数必不大于两乘数的位数之和)。因事先无法知道str1和str2的长度,所以使用动态内存分配的方式定义该数组这里记为arr。该数组的作用是用来保存两个大数相乘的结果每个数组元素存放一个整数并且该整数是0~9间的整数。初始状态都设置为0。
运算步骤:
在进行大数相乘时仍然采用传统的计算方式即从数的最低位开始用其每一位依次与被乘数相乘然后将结果依次相加。显然要得到最终结果需要涉及到多次的相乘和相加的运算。
第一次相乘
(本文约定一次相乘意为乘数的某一位和被乘数的所有位依次相乘并把结果进行相应处理后的一次过程)乘数str2的末位bn与被乘数的每一位相乘并把结果按末位在前首位在后的顺序存入数组arr中。若1≤k≤m如果c[k]≥10则需要进位使得c[k+1]=c[k+1]+c[k]/10c[k]=c[k]%10这个过程称之为数组的重构。
当进行第二次相乘时乘数str2的倒数第二位b[n- 1]与被乘数的每一位相乘结果依次和数组arr中的attr[2]~attr[m+1]的元素相加并且修改对应数组元素然后按需要进行数组的重构。以此类推当完成第n次相乘后数组arr中存放的数据便是最终结果不过是反序的即最高位在后个位在前这时只要将结果数组逆转,并移除首位为0的元素。最后依次输出每个数组元素的值即可
下面是用Java具体代码的实现:
import java.util.Arrays; public class BigNumberMultiplication { /** * 计算两数相乘 * 在进行大数相乘时,仍然采用传统的计算方式,即从数的最低位开始,用其每一位依次与被乘数相乘,然后将结果依次相加存放在结果数组中;(结果数组为末位在前首位在后) * 每次相乘之后对数组进行重构,对大于10的产生进位; * 计算完后对结果数组进行逆转,逆转完之后将结果首位为0的的元素移除,此时的结果数组就为最终计算的结果。 * @param str1 被乘数 * @param str2 乘数 * @return 返回两数相乘后的结果数组 */ public int[] calculateMulti(int[] str1,int[] str2){ int[] resultArr = new int[str1.length+str2.length];//两数相乘的最大位数不会超过两数的长度之和 int offset =0;//记录乘数已经进行计算的次数,即进行第几次乘数运算 for(int i=str2.length-1;i>=0;i--){ //用其每一位一次与被乘数相乘,将结果一次相加存放在结果数组对应位置中 for(int j=str1.length-1;j>=0;j--){ resultArr[offset+str2.length-1-j]+=str2[i]*str1[j]; } //重构数组 rebulidResultArr(resultArr,offset,str1.length); offset++; } convertResultArr(resultArr); //将结果首位为0的元素移除 boolean isBegin= false; for(int i=0;i<resultArr.length;i++){ if(!isBegin&&resultArr[i]>0){ isBegin = true; resultArr = Arrays.copyOfRange(resultArr, i, resultArr.length); break; } } return resultArr; } /** * 重构结果数组,判断指定位的数值是否大于10,如果大于10就要进位 * @param resultArr 待重构的数组 * @param offset 重构的起始索引,在这里为第几次重构或者第几次相乘 * @param length 需要重构的长度,在这里为被乘数的长度。 */ private void rebulidResultArr(int[] resultArr, int offset, int length) { int i= offset; while(i<offset+length){ if(resultArr[i]>10){ resultArr[i+1] += resultArr[i]/10; resultArr[i] %= 10; } i++; } } /** * 翻转数组,将指定的数组逆转过来 * @param resultArr 待翻转的数组 */ private void convertResultArr(int[] resultArr){ int i=0,j=resultArr.length-1,temp = 0; while(i<j){ temp = resultArr[i]; resultArr[i]=resultArr[j]; resultArr[j]=temp; i++; j--; } } /** * 打印计算的结果 * @param resultArr 计算的结果数组 */ public void printResultArr(int[] resultArr){ for(int i=0;i<resultArr.length;i++){ System.out.print(resultArr[i]); } } public static void main(String[] args) { BigNumberMultiplication test= new BigNumberMultiplication(); int[] str =new int[20]; for(int i=0;i<str.length;i++){ str[i]=(i+1)%10; System.out.print(str[i]); } System.out.println(); int[] resuleArr = test.calculateMulti(str, str); test.printResultArr(resuleArr); } }
相关推荐
大数相乘算法,java代码,包含独立大数相加算法 其中bigNumberPlus(String s1,String s2)为大数相加方法 bigNumberMultiply(String s1,String s2)为大数相乘方法
用数组进行大数相乘,解决超整形的大数相乘
20位左右的大数相乘算法解析,用一个整型数组表示一个大数,数组的每个元素储存大数的一位数字,则实际的大数d表示为: d=a[k]*10的k-1次幂+a[k-1]*10的k-2次幂+......+a[2]*10+a[1] 其中a[0]保存该大数的位数. ...
本程序可以求出:任意位的两个大数相乘的结果。 已经实验过>2000位的两数相乘,有兴趣的话,你也试一试吧。 support me!thanks!
大数相乘,算法源码分析,以及相关的实现
大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码大数相乘算法源代码...
大数相乘算法,用CSharp实现,经过测试,应该没错了
java实现大数相乘,在不使用BigInteger工具方法的前提下进行大数相乘运算。
用C语言写的两个大数如何相乘及在计算机上显示出结果。
通过汇编语言实现大数相乘,作业,调试成功
分享一下用C/C++实现的大数相加和大数相乘,可以拿来当工具用。
主要为大家详细介绍了C++实现大数相乘算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
两大数相乘,算法,数组,C语言.。。。。。。
实现了两个大数相乘的小程序,数组大小可自行指定,欢迎大家进行验证
主要为大家详细介绍了C++实现大数相乘的算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
大数相乘解决无限位数相乘问题,可以解决工程问题中无限复杂数据相乘难题
C/C++实现两个大数相乘的源代码,同理可以实现两个无限小数的相乘,实现原理都是一样的。看代码就能写出来。
用c实现了大数相乘,详细设计了算法等,可以用于毕业设计
大数相乘的代码及算法解析,希望对需要的人有帮助哦~
大数相乘大数相乘大数相乘大数相乘大数相乘