大乘数法 -Java

柔光的暖阳◎ 2024-03-04 07:22 46阅读 0赞

[题目链接：![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/c5733b2258874e278581a1e5211b66ff.png][icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.nowcoder.com_practice_c4c488d4d40d4c4e9824c3650f7d5571_tpId_196_tqId_37177_rp_1_ru_exam_company_qru_exam_company_sourceUrl_2Fexam_2Fcompany_difficulty_undefined_judgeStatus_undefined_tags_title]

**描述**

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。数据范围： 读入的数字大小满足 0≤n≤10的![10^\{1000\}][10_1000]。

**示例1**

> 输入："11","99"
> 
> 返回值："1089"
> 
> 说明：11\*99=1089

**示例2**

> 输入："1","0"
> 
> 返回值："0"

![8e446c7cd72f4dd2b8a8b0c9d0be33f3.png][]

**要创建并使用数组就要知道数组的长度**。

假设输入的两个数都是两位数

![ea19cffc421746e5a07d3d23dba7663e.png][]

假设输入的一个是二位数，一个是三位数

![e8881226e6a54318adf8b9d264672a63.png][]

由此可见，**当输入的一个为n位数，一个为m位数，则结果最小为n+m-1位数，最大为n+m位数，当输入两个整数时，只要知道他们都是几位数，就可定义一个数组，只是结果到底是n+m位还是n+m-1位不确定，就以最大值位数即n+m来决定数组长度**。

由题知输入的数为字符串，就可以使用库函数来求数字的位数 ，进而定义一个数组。

public  String Multiplied(String num1,String num2){
            //存储每次计算的结果
            int[] tmp=new int[num1.length()+num2.length()];
            ......
    }

那么乘积的结果怎么存储在数组中呢？

![64856844c0a34af2b6c85fefd4be112a.png][]

将两个数位的乘积除以10的余数放在本位，将两位数的乘积对10取余放在前一位，本位对应的数组下标为i+j-1，其中i的初始值为num1.length-1，j的初始值为num2.length-1。

代码实现：

public  String Multiplied(String num1,String num2){
            //如果两个字符串任意一个有0，乘积为0
            if(num1.equals("0")||num2.equals("0")){
                return "0";
            }
            //存储计算的结果
            int[] tmp=new int[num1.length()+num2.length()];
            //获取两个数字字符串对应位下标
            int len1=num1.length()-1;
            int len2=num2.length()-1;
            for(int i=len1;i>=0;i--){
                int num1s=num1.charAt(i)-'0';
                for(int j=len2;j>=0;j++){
                    int num2s=num2.charAt(j)-'0';
                    //tmp[i+j+1]表示当前位的数值
                    int sum=tmp[i+j+1]+num1s*num2s;
                    tmp[i+j+1]=sum%10;
                    //tmp[i+j]表示前一位（进位）要存的值
                    tmp[i+j]=sum/10;
                }
            }
            //tmp数组是从最后一个元素开始存数据，首元素可能为0
            int start = 0;
            if(tmp[0]==0)
                start=1;
            //将数据以字符串的形式返回
            StringBuilder stringBuilder=new StringBuilder();
            for(int i=start;i<tmp.length;i++){
                stringBuilder.append(tmp[i]);
            }
            return stringBuilder.toString();
        }
    }

[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_www.nowcoder.com_practice_c4c488d4d40d4c4e9824c3650f7d5571_tpId_196_tqId_37177_rp_1_ru_exam_company_qru_exam_company_sourceUrl_2Fexam_2Fcompany_difficulty_undefined_judgeStatus_undefined_tags_title]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/c5733b2258874e278581a1e5211b66ff.png
[10_1000]: https://latex.csdn.net/eq?10%5E%7B1000%7D
[8e446c7cd72f4dd2b8a8b0c9d0be33f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/1adecd7feac24341a21fa9768fed6a26.png
[ea19cffc421746e5a07d3d23dba7663e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/0e9e6befcb24478c85c810d4796ab2a4.png
[e8881226e6a54318adf8b9d264672a63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/df855e279ae045c2afbd13531929b5ba.png
[64856844c0a34af2b6c85fefd4be112a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/04/5762771685124717af6271506e90d505.png