大数乘法

喜欢ヅ旅行 2022-03-15 15:46 277阅读 0赞

给定两个长度不限的数字字符串,求乘积.

思路:如果是让你手算,你一定会列竖式,然后数字a的每一位去乘数字b的每一位,而且还都是从最低位开始.  
那么代码也可以模仿这一过程.  
比如:输入 “123” “20”  
那么计算竖式应该是这样:

1     2         3
                        2        0
                 1*0    2*0     3*0
       2*1       2*2     2*3

注意结果的对齐  
比较复杂的实现方式,使用链表,先将输入转为由低位到高位的单链表  
然后遍历两个链表做乘法,进位等等

# 1 链表实现: #

class Node{ 
            int val;
            Node next;
            public Node(int val){ 
                this.val=val;
            }
            public String toString(){ 
                Node current=this;
                StringBuffer sb=new StringBuffer();
                while(current!=null){ 
                    sb.append(current.val+" ");
                    current=current.next;
                }
                return sb.toString();
            }
        }
        public class Main { 
    
            public static void main(String[] args) { 
                String num1 = "123";
                String num2 = "20";
                Main obj = new Main();
                Node n1 = obj.convert(num1.toCharArray());
                Node n2 = obj.convert(num2.toCharArray());
                System.out.println("num1:" + n1);
                System.out.println("num2:" + n2);
                System.out.println(obj.multi(n1, n2));
            }
    
            // 将字符串转为 个位,百位,依次排列的链表
            public Node convert(char[] array) { 
                Node head = new Node(0);
                Node preNode = head;
                Node newNode = head;
                for (int i = array.length - 1; i >= 0; i--) { 
                    preNode = newNode;
                    newNode = new Node(array[i] - '0');
                    preNode.next = newNode;
                }
                return head.next;
            }
    
            // 将两个 链表相加后得到的链表返回
            public Node addList(Node node1, Node node2) { 
                Node curr1 = node1;
                Node curr2 = node2;
                Node resultHead = new Node(0);
                Node newNode = resultHead;
                Node preNode = null;
                int res = 0;// 进位
    
                while (curr1 != null && curr2 != null) { 
                    preNode = newNode;
                    int sum = 0;
                    sum = curr1.val + curr2.val + res;
                    res += sum / 10;
                    sum = sum % 10;
                    newNode=new Node(sum);
                    preNode.next = newNode;
                    curr1 = curr1.next;
                    curr2 = curr2.next;
                }
                //curr1 比较长
                while (curr1 != null) { 
                    preNode = newNode;
                    int sum = res + curr1.val;
                    res = sum / 10;
                    sum = sum % 10;
                    newNode = new Node(sum);
                    preNode.next = newNode;
                    curr1 = curr1.next;
                }
                //curr2 比较长
                while (curr2 != null) { 
                    preNode = newNode;
                    int sum = res + curr2.val;
                    res = sum / 10;
                    sum = sum % 10;
                    newNode = new Node(sum);
                    preNode.next = newNode;
                    curr2 = curr2.next;
                }
                // 考虑最终进位导致最高位进位
                if (res != 0) { 
                    preNode = newNode;
                    newNode = new Node(res);
                    preNode.next = newNode;
                }
                return resultHead.next;
            }
    
            // 将乘法转为多个链表相加,返回一个链表
            public Node multi(Node node1, Node node2) { 
                Node tempNode = new Node(0);
                Node resultNode = new Node(0);
                Node n1 = node1;
                Node n2 = node2;
                int zeroCount = 0;// 标记结果有多少个0(用以生成最低位的0的节点个数)
                // 双层循环,从一个数的个位开始
                while (n1 != null) { 
                    n2 = node2;
                    Node preNode = tempNode;
                    Node newNode = tempNode;
                    int zeroCount2 = zeroCount;
                    //补充0
                    while (zeroCount2-- > 0) { 
                        preNode = newNode;
                        newNode = new Node(0);
                        preNode.next = newNode;
                    }
                    int res = 0;// 记录进位
                    while (n2 != null) { 
                        preNode = newNode;
                        int mul = n1.val * n2.val + res;
                        res = mul / 10;
                        mul = mul % 10;
                        newNode = new Node(mul);
                        preNode.next = newNode;
                        n2 = n2.next;
                    }
                    if (res != 0) { 
                        newNode.next = new Node(res);
                    }
                    // 计算当前结果
                    resultNode = addList(resultNode, tempNode.next);
                    zeroCount++;
                    n1 = n1.next;
                }
    
    
    
                return resultNode;
            }
        }

测试输出:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]最终结果反转一即得到正确结果.

# 2 非链表实现 #

另一种思路,不借助链表的反转,而是Stringbuffer或者StringBilder的reverse 方法将 输入先反转,思路一致,只是数据结构不一样而已

public class Main { 
    
            public static void main(String[] args) { 
                String num1 = "123";
                String num2 = "20";
                Main obj = new Main();
               // Node n1 = obj.convert(num1.toCharArray());
               // Node n2 = obj.convert(num2.toCharArray());
               // System.out.println("num1:" + n1);
               // System.out.println("num2:" + n2);
               // System.out.println(obj.multi(n1, n2));
                System.out.println(obj.multi(new StringBuffer(num1).reverse(),new StringBuffer(num2).reverse()));
            }
            // 字符串反转版乘法
            private String multi(StringBuffer reverse1, StringBuffer reverse2) { 
                 int []result=new int[reverse1.length()+reverse2.length()];
                 int zeroCount=0;// 0个数,可以用来表示当前是在计算哪一位,为0表示个位,1表示十位
                int res=0;//进位
                for(int i=0;i< reverse1.length();i++){ 
    
                  int multi=0;
                  int  resultStart=zeroCount;// 此次循环 乘积结果最低位应放在result 中的位置
                    res=0;// 进位
                    for(int j=0;j<reverse2.length();j++){ 
                         multi=res+ (reverse1.charAt(i)-'0')*(reverse2.charAt(j)-'0');
                         res=multi/10;
                         multi%=10;
                         result[resultStart++]+=multi;
                         if(resultStart>=1){ 
                             result[resultStart]+=result[resultStart-1]/10;
                             result[resultStart-1]%=10;
                         }
    
                    }
                    zeroCount++;
                }
                StringBuffer resultStr=new  StringBuffer();
                for(int i=0;i<result.length-1;i++){ 
                    resultStr.append(result[i]);
                }
                //表示最高位有进位
                if(res!=0){ 
                    resultStr.append(res);
                }
    
    
             return  resultStr.reverse().toString();
            }

测试输出:  
输入:String num1 = “100000000”;  
String num2 = “20”;  
输出:  
![在这里插入图片描述][20190303210905212.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]: /images/20220315/112eab1a6da147ae8887712778405400.png
[20190303210905212.png]: /images/20220315/0494bc50b2574049898292dfb435c0db.png