首页 > 试题广场 >

大数乘法

[编程题]大数乘法
  • 热度指数:4067 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
实现大数乘法,输入是两个字符串如
n1 = '340282366920938463463374607431768211456'
n2 = '340282366920938463463374607431768211456'
输出
'115792089237316195423570985008687907853269984665640564039457584007913129639936'
要求:不能使用对大数相乘有内建支持的语言;需要包含对输入字符串的合法性校验

输入描述:
一行,两个非负整数n1,n2,保证|n1|+|n2|<10000,其中|n|是n作为字符串的长度


输出描述:
输出n1*n2的结果
示例1

输入

340282366920938463463374607431768211456 340282366920938463463374607431768211456

输出

115792089237316195423570985008687907853269984665640564039457584007913129639936

备注:
给出的数据均是合法的,但仍建议您对输入的字符串进行合法性校验
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        char[] large = null;
        char[] small = null;
        if(a.length() >= b.length()){
            large = a.toCharArray();
            small = b.toCharArray();
        }else{
            large = b.toCharArray();
            small = a.toCharArray();
        }
        
        int[] mult = new int[a.length()+b.length()];
        for(int j = small.length-1;j>=0;j--){
            for(int i = large.length-1;i>=0;i--){
                int num1 = small[j]-'0';
                int num2 = large[i]-'0';
                mult[large.length-1-i+small.length-1-j] += num1*num2;
            }
        }
        for(int i=0;i<mult.length-1;i++){
            if(mult[i]>9){
                mult[i+1]+=mult[i]/10;
                mult[i]%=10;
            }
        }
        
       StringBuilder builder = new StringBuilder();
        for(int i = mult.length-1;i>=0;i--){
            builder.append(mult[i]);
        }
        String res = builder.toString();
        for(int i = 0;i<res.length();i++){
            if(res.charAt(i)!='0'){
                res = res.substring(i);
                break;
            }
            if(i==res.length()-1 && res.charAt(i) == '0'){
                res = "0";
            }
        }
        System.out.println(res);
    }
}
发表于 2021-03-17 11:53:42 回复(0)

Java 版本,参考了几位大佬的回答。

//package cn.practice.niuke;
import java.util.Scanner;
/**
 * 大数相乘。
 * 给出的数据均是合法的,但仍建议您对输入的字符串进行合法性校验
 * 远远超出 longest.
 */
public class Main {
      public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.next();
        String s2 = scanner.next();
        // 先不做校验。
          int sumLen = s1.length() + s2.length();
          int[] res = new int[sumLen];
          for(int i = 0; i< s1.length(); i++) {
               int num1 = s1.charAt(s1.length() -1 - i ) - '0';
              for(int j  = 0; j< s2.length(); j++) {
                  int num2 = s2.charAt(s2.length() -1 - j) - '0';
                  res[i +j ] += num1 * num2;                          
              }
          }
          for(int i = 0; i< res.length - 1; i++) {
              if(res[i] >= 10) {
                  res[i+1] += res[i] / 10;
                  res[i] %= 10;
              }
          }
          int i = res.length -1;
          for(; i> 0 && res[i] == 0; i--) {} // 去除结果前面的 0
          StringBuilder sb = new StringBuilder();
          for(; i>=0; i--) {
              sb.append(res[i]);
          }
          System.out.println(sb.toString());

    }
}
发表于 2019-08-22 16:53:02 回复(2)