大数乘法
发布时间:2020-12-14 03:43:18 所属栏目:大数据 来源:网络整理
导读:大数乘法,顾名思义,就是两个很大的数做乘法。有多大?反正出现大数乘法的地方,大都无法使用计算机给定的数据类型进行接收并进行直接计算,需要自己做一些算法。例如:编程计算两个 64 位十进制数相乘。 正好自己面试时候遇到了,记得当初写的答案是:换算
大数乘法,顾名思义,就是两个很大的数做乘法。有多大?反正出现大数乘法的地方,大都无法使用计算机给定的数据类型进行接收并进行直接计算,需要自己做一些算法。例如:编程计算两个64位十进制数相乘。 正好自己面试时候遇到了,记得当初写的答案是:换算成二进制,进行计算,再换算成十进制。后来仔细一想,?纯属扯淡~!后来在网上找各位大神的解决方案,方法有多种,其中最易懂、最集中地解决方案也就是三步: 一、用int数组存放两个乘数,每一位上数字对应数组中一个元素。 二、两个乘数依次每位相乘,结果放入一个新的数组。 三、根据新的数组,进位,进完位的即为要求结果。 解决思路及java代码如下: package com.test; import java.util.ArrayList; import java.util.List; /** * @author lyl * */ public class BigNumber { private String number1; private String number2; List<Integer> calNum1; List<Integer> calNum2; List<Integer> calNumResult; /** * @return the number1 */ public String getNumber1() { return number1; } /** * @param number1 the number1 to set */ public void setNumber1(String number1) { this.number1 = number1; } /** * @return the number2 */ public String getNumber2() { return number2; } /** * @param number2 the number2 to set */ public void setNumber2(String number2) { this.number2 = number2; } /** * @param number1 * @param number2 */ public BigNumber(String number1,String number2) { super(); this.number1 = number1; this.number2 = number2; calNum1 = new ArrayList<Integer>(); calNum2 = new ArrayList<Integer>(); calNumResult = new ArrayList<Integer>(); } //转换成int数组 private void toBigNumberChar(){ char temp[]; temp = number1.toCharArray(); for (int i = 0; i < temp.length; ++i) { calNum1.add(temp[i] - '0'); } temp = number2.toCharArray(); for (int i = 0; i < temp.length; ++i) { calNum2.add(temp[i] - '0'); } } //进行计算 public String multiply(){ String result = new String(); toBigNumberChar(); for(int i = 0; i< calNum1.size()+calNum2.size(); ++i){ calNumResult.add(0); } //1.每项相乘,此处模型来自乘法计算竖式。相乘后,每项乘积在同一个位数(例如百位、千位)的结果累加 for(int i = 0; i< calNum1.size(); ++i){ for (int j = 0; j < calNum2.size(); calNumResult.set(i+j,(calNum1.get(calNum1.size() - i - 1) * calNum2.get(calNum2.size() - j - 1)) + calNumResult.get(i+j)); } } //2.进位 for (int i = 0; i < calNum1.size() + calNum2.size() - 1 ; ++i) { calNumResult.set(i+1,calNumResult.get(i+1) + calNumResult.get(i)/10);//低位向高位进位 calNumResult.set(i,calNumResult.get(i) % 10);//求低位值 } for (int i = 0; i < calNumResult.size(); i++) { result += calNumResult.get(calNumResult.size() - i -1); } return result; } public static void main(String[] args) { String number1 = "1234567812345678123456781234567812345678123456781234567812345678"; String number2 = "1234567812345678123456781234567812345678123456781234567812345678"; BigNumber big = new BigNumber(number1,number2); String result = big.multiply(); System.out.println(result); } }计算完,发现效率还可以,毕竟复杂度才 O(n^2)~ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- 如何使List :: Util’shuffle’在Perl中重现相同的输出
- 18.10.29 POJ 3691 DNA repair(AC自动机+dp)
- Groovy轻松入门——通过与Java的比较,迅速掌握
- R文本挖掘初探之“天下风云出我辈, 一入江湖岁月催”(2)
- delphi – 从Microsoft功能区执行命令?
- java – @Transactional的自定义快捷方式注释无法正常工作
- delphi – TVirtualStringTree搜索结果的重点
- lua使用cocos2d-x中的函数
- POJ 2756 Autumn is a Genius 使用string的大数加减
- 用callbyname调用有多个参数的方法