[编程题]大整数相乘
import java.util.Scanner;
/**
- Created by linjian on 17/8/5.
*/
public class Main {
public static void main(String[] args) {
}Scanner scanner = new Scanner(System.in); String num1 = scanner.next(); String num2 = scanner.next(); System.out.println(multiply(num1,num2));
public static String multiply(String num1, String num2) {
}num1 = new StringBuilder(num1).reverse().toString(); num2 = new StringBuilder(num2).reverse().toString(); // even 99 * 99 is < 10000, so maximaly 4 digits int[] d = new int[num1.length() + num2.length()]; for (int i = 0; i < num1.length(); i++) { int a = num1.charAt(i) - '0'; for (int j = 0; j < num2.length(); j++) { int b = num2.charAt(j) - '0'; d[i + j] += a * b; } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < d.length; i++) { int digit = d[i] % 10; int carry = d[i] / 10; sb.insert(0, digit); if (i < d.length - 1) d[i + 1] += carry; } //trim starting zeros while (sb.length() > 0 && sb.charAt(0) == '0') { sb.deleteCharAt(0); } return sb.length() == 0 ? "0" : sb.toString();
}
发表于 2017-08-05 19:38:16
回复(10)
import sys s=sys.stdin.readline().strip().split() def karatsuba_mul(num1, num2): #karatsuba算法 if len(str(num1))==1 or len(str(num2))==1: return num1*num2 n=max(len(str(num1)),len(str(num2))) half=n//2 a=num1//10**half b=num1%10**half c=num2//10**half d=num2%10**half ac=karatsuba_mul(a,c) #计算a*c bd=karatsuba_mul(b,d) #计算b*d abcd=karatsuba_mul(a+b,c+d) #计算(a+b)*(c+d) adbc=abcd-ac-bd return ac*10**(2*half)+adbc*10**half+bd print(str(karatsuba_mul(int(s[0]), int(s[1]))))
编辑于 2019-03-18 19:49:42
回复(2)
import java.util.Scanner;
/**
* @author wylu
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
char[] s1 = scanner.next().toCharArray();
char[] s2 = scanner.next().toCharArray();
int len = s1.length + s2.length;
char[] res = new char[len];
for (int i = 0; i < len; i++) res[i] = '0';
for (int i = s1.length - 1; i >= 0; i--) {
int cur = s1.length - i - 1, multiplier = s1[i] - '0', carry = 0;
for (int j = s2.length - 1; j >= 0; j--) {
int product = (res[cur] - '0') + multiplier * (s2[j] - '0') + carry;
res[cur++] = (char) (product % 10 + '0');
carry = product / 10;
}
if (carry != 0) res[cur] = (char) (carry + '0');
}
int i = len - 1;
while (i >= 0 && res[i] == '0') i--; //忽略前导0
if (i < 0) {
System.out.println(0);
}else {
for (; i >= 0; i--) System.out.print(res[i]);
System.out.println();
}
}
}
}
发表于 2019-01-12 00:53:10
回复(0)
#include <iostream>
#include <cstring>
int multi(const char* lhs, const char* rhs, char* result) {
if (lhs == NULL || rhs == NULL || result == NULL)
return 0;
int llen = strlen(lhs), rlen = strlen(rhs);
if (llen == 0 || rlen == 0)
return 0;
// 用rhs每一位去乘lhs,模拟手工算乘法的过程。
int length = llen + rlen - 1;
for (int j = rlen - 1; j >= 0; j--) {
int carry = 0; // 乘法进位
for (int i = llen - 1; i >= 0; i--) {
int temp = (rhs[j] - '0') * (lhs[i] - '0') + carry;
// 根据位偏移将本位的结果加到result中去并处理加法进位。(result为倒序)
int bit = llen - i - 1 + (rlen - j - 1);
if ((result[bit] += temp % 10) >= '0' + 10) {
result[bit + 1] += (result[bit] - '0') / 10;
result[bit] = (result[bit] - '0') % 10 + '0';
}
// 保留进位。
carry = temp / 10;
}
// 最高位有进位
if (carry > 0) {
result[llen + (rlen - j - 1)] += carry;
length++;
}
}
// 去掉多余的0
while (result[length - 1] == '0')
length--;
return length;
}
int main() {
char a[999];
char b[999];
scanf("%s%s", a, b);
char r[999999];
memset(r, '0', sizeof(r));
int length = multi(a, b, r);
while (--length >= 0) {
std::cout << r[length];
}
system("pause");
return 0;
}
发表于 2017-08-06 22:30:16
回复(0)
# coding=utf-8
def fun(l):
num0,num1 = l[0],l[1]
result = 0
# 还原乘法的过程，按位相乘再乘以位数权重
for i in range(len(num0)):
for j in range(len(num1)):
# 注意计算位数权重时，index越大位数越小
result += int(num0[i])*int(num1[j])*pow(10,len(num0)-1-i+len(num1)-1-j)
return (str(result))
if __name__=='__main__':
s = raw_input()
l = s.split(' ')
print(fun(l))
发表于 2019-01-15 16:03:15
回复(1)
模拟手算过程：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static String add(String n1, String n2) {
StringBuilder res = new StringBuilder();
int p1 = n1.length() - 1;
int p2 = n2.length() - 1;
int carry = 0;
while (carry > 0 || p1 >= 0 || p2 >= 0) {
int value = carry + (p1 >= 0 ? n1.charAt(p1) - '0' : 0) + (p2 >= 0 ? n2.charAt(p2) - '0' : 0);
res.append(value % 10);
carry = value / 10;
if (p1 >= 0) p1--;
if (p2 >= 0) p2--;
}
return res.reverse().toString();
}
private static String singleMul(String n1, char n2) {
StringBuilder res = new StringBuilder();
int p = n1.length() - 1;
int carry = 0;
while (carry > 0 || p >= 0) {
int value = carry + (n2 - '0') * (p >= 0 ? n1.charAt(p) - '0' : 0);
res.append(value % 10);
carry = value / 10;
if (p >= 0) p--;
}
return res.reverse().toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String n1 = scanner.next();
String n2 = scanner.next();
if (n1.length() < n2.length()) {
String tmp = n1;
n1 = n2;
n2 = tmp;
}
List<String> sums = new ArrayList<>();
for (int i = n2.length() - 1; i >= 0; i--) {
sums.add(singleMul(n1, n2.charAt(i)) + new String(new char[n2.length() - 1 - i]).replace('\0', '0'));
}
String res = "0";
for (String s : sums) {
res = add(res, s);
}
System.out.println(res);
}
}
运行时间：74ms
占用内存：11272k
发表于 2019-03-13 00:33:42
回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string num1, num2;
string s = "";
cin >> num1 >> num2;
int len1 = num1.size();
int len2 = num2.size();
vector<int> vTemp(len1 + len2 - 1);
int n1, n2;
for (int i = 0; i<len1; i++)
{
n1 = num1[i] - '0';
for (int j = 0; j <len2; j++)
{
n2 = num2[j] - '0';
vTemp[i + j] += n1*n2;
}
}
int carry = 0;
int tmp;
for (int i = vTemp.size()-1; i >= 0; i--)
{
tmp = vTemp[i] + carry;
vTemp[i] = tmp % 10;
s = to_string(vTemp[i])+s;
carry = tmp / 10;
}
if(carry > 0)
s = to_string(carry)+s;
cout << s << endl;
return 0;
}
发表于 2018-08-05 16:31:52
回复(3)
直接模拟乘法的竖式计算过程，不过要注意计算加法的时候数字排列是阶梯状的，需要在数的后面补0。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strNum = br.readLine().trim().split(" ");
System.out.println(multiply(strNum[0].toCharArray(), strNum[1].toCharArray()));
}
// 模拟乘法竖式
private static String multiply(char[] num1, char[] num2) {
if(num1.length < num2.length){
char[] temp = num1;
num1 = num2;
num2 = temp;
}
Stack<String> stack = new Stack<>();
for(int j = num2.length - 1; j >= 0; j--){
StringBuilder sb = new StringBuilder();
// 之后做竖式加法要补0
for(int k = 0; k < num2.length - 1 - j; k++) sb.append(0);
int carry = 0;
for(int i = num1.length - 1; i >= 0; i--){
int num = (num1[i] - '0')*(num2[j] - '0') + carry;
carry = num / 10;
sb.append(num % 10);
}
if(carry > 0) sb.append(carry);
if(stack.isEmpty())
stack.push(sb.reverse().toString());
else{
String temp = stack.pop();
stack.push(add(temp, sb.reverse().toString()));
}
}
return stack.pop();
}
private static String add(String num1, String num2) {
if(num1.length() < num2.length()){
String temp = num1;
num1 = num2;
num2 = temp;
}
int len1 = num1.length();
int len2 = num2.length();
int i = len1 - 1, j = len2 - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while(i >= 0 && j >= 0){
int num = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + carry;
carry = num / 10;
sb.append(num % 10);
i--;
j--;
}
while(i >= 0){
int num = (num1.charAt(i) - '0') + carry;
carry = num / 10;
sb.append(num % 10);
i--;
}
if(carry > 0) sb.append(carry);
return sb.reverse().toString();
}
}
发表于 2021-02-01 14:57:29
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s1, s2;
cin>>s1>>s2;
int n=s1.size(), m=s2.size(), k;
string r(n+m,'0');
for(int i=n-1;i>=0;i--){
int c = 0;
for(int j=m-1;j>=0;j--){
int t = (r[i+j+1]-'0') + (s1[i]-'0')*(s2[j]-'0') + c;
r[i+j+1] = t%10 + '0';
c = t/10;
}
r[i] += c;
}
for(k=0;k<r.size();k++)
if(r[k]!='0')
break;
r = r.substr(k);
cout<<r<<endl;
return 0;
}
发表于 2020-11-10 01:10:00
回复(0)
from functools import reduce def multiply(num1, num2): n1, n2 = len(num1), len(num2) if n1 < n2: num1, num2, n1, n2 = num2, num1, n2, n1 res = [] for j in range(n2 - 1, -1, -1): tmpRes = '' carry = 0 for i in range(n1 - 1, -1, -1): tmp = int(num1[i]) * int(num2[j]) + carry tmpRes = str(tmp % 10) + tmpRes carry = tmp // 10 tmpRes = str(carry) + tmpRes if carry != 0 else tmpRes if int(tmpRes) != 0: tmpRes += (n2 - j - 1) * '0' else: tmpRes = '0' res.append(tmpRes) return reduce(addStrings, res) if len(res) > 1 else res[0] def addStrings(num1, num2): i, j, res = len(num1) - 1, len(num2) - 1, '' carry = 0 while i >= 0&nbs***bsp;j >= 0&nbs***bsp;carry: c1 = int(num1[i]) if i >= 0 else 0 c2 = int(num2[j]) if j >= 0 else 0 tmp = c1 + c2 + carry carry = tmp // 10 res = str(tmp % 10) + res i, j = i - 1, j - 1 return res a, b = input().split() print(multiply(a, b))
发表于 2020-07-15 16:24:50
回复(0)
import java.math.BigDecimal;
import java.util.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin=new Scanner (System.in);
String s1=cin.next();
String s2=cin.next();
BigDecimal b1=new BigDecimal(s1);
BigDecimal b2=new BigDecimal(s2);
BigDecimal b3=b1.multiply(b2);
String s3=String.valueOf(b3);
System.out.print(s3);
}
}
发表于 2020-01-10 12:32:45
回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void output(vector<int> v)
{
for (auto ele : v)
{
cout << ele;
}
putchar(10);
}
vector<int> mul(string x, string y)
{
vector<int> res(x.length() + y.length(), 0);
reverse(x.begin(), x.end());
reverse(y.begin(), y.end());
//先乘，不用考虑进位，int范围21亿，10以内的乘法，可以存2千万次
for (int i = 0; i < x.length(); i++)
{
for (int j = 0; j < y.length(); j++)
{
//和x的第一位数乘，结果从res[0]开始保存，和x的第二位数乘，结果从res[1]开始保存，以此类推
res[i + j] += (x[i] - '0') * (y[j] - '0');
}
}
//最后一次性进位
for (int i = 0; i < res.size() - 1; i++)
{
res[i + 1] += res[i] / 10;
res[i] %= 10;
}
//3 * 3 = 9，但是申请了2个int的vector，最后一个int没有进位，pop掉
while (res.back() == 0)
{
res.pop_back();
}
//逆置就是结果了
reverse(res.begin(), res.end());
return res;
}
int main()
{
string x, y;
while (cin >> x >> y)
{
output(mul(x, y));
}
return 0;
}
发表于 2019-08-19 18:42:16
回复(0)
a, b = map(int, input().split())
print(str(a*b))
print(str(a*b))
发表于 2019-08-06 23:14:30
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
import java.lang.Math;
public class Main{
public static String add(String s1,String s2){
int len1=s1.length();
int len2=s2.length();
int pad=Math.abs(len1-len2);
String padding="";
for(int i=0;i<pad;i++){
padding=padding+"0";
}
if(len1>len2){
s2=padding+s2;
}else{
s1=padding+s1;
}
int len=s1.length();
String ans="";
int c=0;
for(int j=len-1;j>=0;j--){
int a=s1.charAt(j)-'0';
int b=s2.charAt(j)-'0';
int v=(a+b+c)%10;
c=(a+b+c)/10;
ans=v+ans;
}
if(c>0){
ans=c+ans;
}
return ans;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String s1=sc.next();
String s2=sc.next();
int len1=s1.length();
int len2=s2.length();
ArrayList<String> tmp=new ArrayList<>();
for(int i=len2-1;i>=0;i--){
String ans="";
int v=s2.charAt(i)-'0';
for(int j=0;j<v;j++){
ans=add(ans,s1);
}
int pad=len2-1-i;
String padding="";
for(int l=0;l<pad;l++){
padding=padding+"0";
}
ans=ans+padding;
tmp.add(ans);
}
String result="";
for(String s:tmp){
result=add(result,s);
}
System.out.println(result);
}
}
}
发表于 2019-07-26 10:36:37
回复(2)
/*很朴素的代码*/
#include <iostream>
#include<string>
using namespace std;
int main()
{
string str1,str2;
cin>>str1>>str2;
int s1=str1.size();
int s2=str2.size();
int *result=new int[s1+s2];
for(int i=0;i<s1+s2;i++)
{
result[i]=0;
}
for(int i=s1-1;i>=0;i--)
{
int carry=0;
for(int j=s2-1;j>=0;j--)
{
int temp=(str1[i]-'0')*(str2[j]-'0')+result[i+j+1]+carry;
result[i+j+1]=temp%10;
carry=temp/10;
if(j==0)
result[i]+=carry;
}
}
int i = 0;
while (result[i] == 0)
i++;
string s;
for(i;i<s1+s2;i++)
s+=result[i]+'0';
cout<<s<<endl;
return 0;
}
编辑于 2019-06-25 14:29:29
回复(0)
- 仿照手算乘法的思路，逐位相乘，然后错位累加即可。
#include <bits/stdc++.h>
using namespace std;
string sum;
string multi(string str1, int num) {
string tmp;
int forward = 0;
for (int i = str1.size() - 1; i >= 0; i--) {
int s = num * (str1[i] - '0') + forward;
tmp.insert(tmp.begin(), (s % 10) + '0');
forward = s / 10;
}
if (forward)
tmp.insert(tmp.begin(), forward + '0');
return tmp;
}
string add(string s1, string s2) {
int i = s1.size() - 1;
int j = s2.size() - 1;
int forward = 0;
string tmp;
while (i >= 0 && j >= 0) {
int s = (s1[i] - '0') + (s2[j] - '0') + forward;
tmp.insert(tmp.begin(), (s % 10) + '0');
forward = s / 10;
i--; j--;
}
while (i >= 0) {
int s = (s1[i] - '0') + forward;
tmp.insert(tmp.begin(), (s % 10) + '0');
forward = s / 10;
i--;
}
while (j >= 0) {
int s = (s2[j] - '0') + forward;
tmp.insert(tmp.begin(), (s % 10) + '0');
forward = s / 10;
j--;
}
if (forward)
tmp.insert(tmp.begin(), forward + '0');
return tmp;
}
int main(int argc, char const *argv[])
{
string str1, str2;
cin >> str1 >> str2;
sum.clear();
int flag = 1;
//cout << "debug " << add("12", "12") << endl;
for (int i = str2.size() - 1; i >= 0; i--) {
string tmp = multi(str1, str2[i] - '0');
//cout << tmp << endl;
if (sum.empty())
sum = tmp;
else {
//cout << "add is " << add(tmp, sum.substr(0, sum.size() - 1)) << endl;
sum = add(tmp, sum.substr(0, sum.size() - flag)) + sum.substr(sum.size() - flag);
flag++;
//cout << "sum is " << sum << endl;
}
}
cout << sum;
return 0;
}
发表于 2019-06-25 11:00:58
回复(0)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
//参照二楼思路做了修正
//基本思路：首先，两个整数相乘可以分为两步。第一步，不考虑进位，两个整数相乘后，得到很多列
// ,然后每列的和都依次存入数组c中。其次，从右往左看，后一列的和还需要加上前一列的
// 和的十进制位，而前一列需要变成它的和的余数。最后，只需将数组c依次拼接即可得所求。
void bigIntegerMultiplying(string a,string b) {
int len1=a.size();
int len2=b.size();
vector<int> c(len1+len2+1);
int num1,num2;
for(int i=0; i<len1; ++i) {
num1=a[len1-1-i]-'0';
for(int j=0; j<len2; ++j) {
num2=b[len2-1-j]-'0';
c[i+j]+=num1*num2;
}
}
string str="";
char s;
for(int i=0; i<len1+len2; ++i) {
c[i+1]+=c[i]/10;//加进位
c[i]=c[i]%10; //变余数
s=c[i]+'0';
if(i==len1+len2-1&&!c[i])//过滤最高位可能为0的情况
continue;
str=s+str;//反向拼接
}
cout<<str;
}
};
int main() {
string str1,str2;
cin>>str1>>str2;
Solution s;
s.bigIntegerMultiplying(str1,str2);
return 0;
}
发表于 2019-06-21 22:17:47
回复(0)
import java.util.Scanner;
import java.math.BigDecimal;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s1= scanner.next();
String s2 = scanner.next();
BigDecimal b1 = new BigDecimal(s1);
BigDecimal b2 = new BigDecimal(s2);
System.out.println(b1.multiply(b2));
}
import java.math.BigDecimal;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s1= scanner.next();
String s2 = scanner.next();
BigDecimal b1 = new BigDecimal(s1);
BigDecimal b2 = new BigDecimal(s2);
System.out.println(b1.multiply(b2));
}
}
这不算使用系统自带的大整数吗? 也通过了！
发表于 2019-05-24 14:56:01
回复(0)
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String num1=scan.nextBigDecimal().toString();
String num2=scan.nextBigDecimal().toString();
long x=Long.parseLong(num1);
BigInteger h=BigInteger.valueOf(x);
long y=Long.parseLong(num2);
BigInteger g=BigInteger.valueOf(y);
BigInteger k=h.multiply(g);
String ssum=String.valueOf(k);
System.out.println(ssum);
}
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String num1=scan.nextBigDecimal().toString();
String num2=scan.nextBigDecimal().toString();
long x=Long.parseLong(num1);
BigInteger h=BigInteger.valueOf(x);
long y=Long.parseLong(num2);
BigInteger g=BigInteger.valueOf(y);
BigInteger k=h.multiply(g);
String ssum=String.valueOf(k);
System.out.println(ssum);
}
}
为什么我这个在自己电脑上可以 在这就不行呢？？？？ 有没有大神帮我看看
发表于 2019-04-24 19:40:10
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-03 01:08:20
-
2023-02-14 15:45:17 -
2022-09-16 08:48:40
-
2022-09-13 16:30:21 -
2022-09-06 22:33:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
