写在前面

周五腾讯模仿笔试（2016.03.25），出了个题，关于大数相乘的题目。这样的题早年也有，网上也有许多实当代码（笔者写完算法后搜刮了一下，确有许多，并未细看，并不知道是否有和笔者沟通的办理方案）。笔者将算法用java实现，写出来给列位参考一下，不敷之处，请列位多多指正。

题目

题目描写

输入两个整数，要求输出两个整数的乘积，该乘积也许超出整型范畴。

题目说明

起首，依题意，必定是不能用两个整数直接相乘，获得功效。故要思量解析题目，即怎样将两个大数的乘法，换成一系列小一点的数的运算。由此，笔者按照小学竖式，想到了不进位乘法，认为可以用不进位乘法来办理大数相乘的题目。至此，算法已经确定，接下来就是如那里理赏罚两个整数和其乘积了。笔者自觉得可以用ArrayList来存储。

算法描写

根基头脑：回收不进位乘法计较，然后再将功效举办转换
如计较12345*123 （num1*num2）

1  2  3  4  5       list1    5 4 3 2 1
         *        1  2  3       list2    3 2 1
          ————————————————
            3  6  9 12 15
         2  4  6  8 10
      1  2  3  4  5
      ——————————————————————
      1  4  9 16 22 22 15   listres 15 22 22 16  9  4  1
 转换为：
      1  5  1  8  5  3  5    
 留意：list中，数据存储的次序是从最低位开始，依次到最高位

算法实现

详细实当代码如下：

import java.util.ArrayList;
/** * @Title: 大数相乘list实现（本例中指针对大整数） * @Description: 给定两个大数，其相乘功效也许超出整数的范畴， * 溢出。通过本算法实现大数相乘，并打印功效。 * @author: JerryZhou * @date:2016年3月27日 * @version:V1.0 */
public class bigNumMultiple {
    /* * 根基头脑：回收不进位乘法计较，然后再将功效举办转换 * 如计较12345*123 （num1*num2） * 1 2 3 4 5 list1 5 4 3 2 1 * * 1 2 3 list2 3 2 1 * ———————————————— * 3 6 9 12 15 * 2 4 6 8 10 * 1 2 3 4 5 * —————————————————————— * 1 4 9 16 22 22 15 listres 15 22 22 16 9 4 1 * 转换为： * 1 5 1 8 5 3 5 * 留意：list中，数据存储的次序是从最低位开始，依次到最高位 */
    public static void main(String[] args) {
        int a =12345;
        int b = 123;
        Multiple(a,b);
    }
    /** * @Title Multiple * @Description 大数相乘，打印功效 * @param num1 * @param num2 */
    public static void Multiple(int num1,int num2){
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        ArrayList<Integer> listres = new ArrayList<Integer>();
        if(num1<num2){   //将较大的数放在前面
            int tmp = 0;
            tmp = num1;
            num1 = num2;
            num2 = tmp;
        }
        while(num1/10!=0){ //将num1，从个位开始，依次存入list1中
            list1.add(num1 % 10);
            num1 = num1 / 10;
        }
        list1.add(num1);
        while(num2/10!=0){ //将num2，从个位开始，依次存入list2中
            list2.add(num2 % 10);
            num2 = num2 / 10;
        }
        list2.add(num2);
        int firstlen = list1.size(); //num1的位数
        int secondlen = list2.size(); //num2的位数
        for(int i = 0;i < secondlen; i++){ //不进位乘法运算
            for(int j = 0;j< firstlen;j++){
                if(listres.size()<j+i+1){
                    listres.add(0);
                    listres.set(j+i,listres.get(j+i)+list1.get(j)*list2.get(i));
                }else{
                    listres.set(j+i,listres.get(j+i)+list1.get(j)*list2.get(i));
                }   
            }
        }
        int len = listres.size(); 
        for(int i =0;i<len;i++){ //功效转换
            if(listres.get(i)>9){
                int temp = listres.get(i)/10;
                listres.set(i,listres.get(i)%10);
                if(listres.size()<i+2){ //思量到最高为的进位题目，也许导致list必要开发新空间
                    listres.add(0);
                }
                listres.set(i+1,listres.get(i+1)+temp);
            }else{
                continue;
            }
        }
        while(len>0){  //打印大数相乘的最后功效
            System.out.print(listres.get(len-1));
            len-=1;
        }
    }
}

以上措施经笔者测试，确实是乐成办理了大数相乘的题目，但笔者以为尚有很大的优化空间。但愿列位读者多多指正。

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!