大整數乘法
分治法
將一個規模為N的問題，分解成K個規模較小的子問題，這些子問題相互獨立且月原問題性質相同，求解出子問題的解，合并得到原問題的解
java中的BigInteger總結
（1）程式有時需要處理大整數，java.math包中的BigInteger類提供任意精度的整數運算，可以使用構造方法：
public BigInteger(String VAL)構造一個十進制的BigInteger物件，該構造方法可以發生NumberFormatException例外，也就是說，字串引數VAL中如果含有非數字字符就會發生NumberFormatException例外，
（2）BigInteger類的常用方法：
public BigInteger add(BigInteger val) 回傳當前大整數物件與引數指定的大整數物件的和
public BigInteger subtract(BigInteger val) 回傳當前大整數物件與引數指定的大整數物件的差
public BigInteger multiply(BigInteger val) 回傳當前大整數物件與引數指定的大整數物件的積
public BigInteger devide(BigInteger val) 回傳當前大整數物件與引數指定的大整數物件的商
public BigInteger remainder(BigInteger val) 回傳當前大整數物件與引數指定的大整數物件的余
public int compareTo(BigInteger val) 回傳當前大整數物件與引數指定的大整數物件的比較結果，回傳值是1、-1、0，分別表示當前大整數物件大于、小于或等于引數指定的大整數，
public BigInteger abs() 回傳當前大整數物件的絕對值
public BigInteger pow(int exponent) 回傳當前大整數物件的exponent次冪，
public String toString() 回傳當前當前大整數物件十進制的字串表示，
public String toString(int p) 回傳當前大整數物件p進制的字串表示，
但是這篇文章不用這個java內置的方法來實作大數乘法
import java.util.*;
import java.math.*;
public class NumMul{
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
BigInteger a, b;
while(cin.hasNext()){
a = cin.nextBigInteger();
b = cin.nextBigInteger();
System.out.println(a.multiply(b));
}
}
}
分治演算法特征分析
分治法能解決的問題一般具有以下幾個特征：
-
該問題的規模縮小到一定程度就可以容易的解決；
-
該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
-
利用該問題分解出子問題的解，可以合并為該問題的解；
-
該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題；
分治演算法大多采用遞回實作，第二條特征就反應了遞回思想的參考，
如果滿足了第一條特征和第二條特征，不滿足第三條特征，可以考慮用貪心法或動態規劃法，
如果不滿足第四條特征，也可以用分治法，但是要做很多不必要的作業，重復的解公共的子問題，所以一般用動態規劃法比較好，
大整數乘法：十進制
解法一（分治法）
將兩個整數分別一分為二：
X = A*10^(n/2) + B
Y = C*10^(n/2) + D
X*Y = (A*10^(n/2) + B)*( C*10^(n/2) + D) = A*C*10^n + A*D*10^(n/2) + B*C*10^(n/2) + B*D
但是這樣做并沒有減少直接相乘的的時間復雜度，所以要繼續減少乘法的次數
X*Y = (A*10^(n/2) + B)*( C*10^(n/2) + D)
= A*C*10^n + A*D*10^(n/2) + B*C*10^(n/2) + B*D
= A*C*10^n + ((A+B)(C+D) – A*C – B*D)*10*(n/2) + B*D
或者：= A*C*10^n + ((A-B)(D-C) + A*C + B*D)*10*(n/2) + B*D
然后利用上面的公式寫遞回就好了
代碼如下：
public class BigDataRide {
public static int sign(long a) {
return a < 0 ? -1 : 1;
}
public static double bigdataride(long x,long y,int n) {
x = Math.abs(x);
y = Math.abs(y);
if (n == 1) {
return x * y;
}
else {
if (n%2==1) {
n = n - 1; //對奇數的操作
}
long a = x / Math.round(Math.pow( 10 , (n / 2)));
long b = x - a * Math.round(Math.pow( 10 , (n / 2)));
long c = y / Math.round(Math.pow( 10 , (n / 2)));
long d = y - c * Math.round(Math.pow( 10 , (n / 2)));
double ac = bigdataride(a,c,n/2);//遞回計算a*c
double bd = bigdataride(b,d,n/2);//計算b*d
long aJb = a + b;
long cJd = c + d;
double abcd = bigdataride(aJb,cJd,n/2);
return (ac*Math.pow(10,n) + (abcd - ac - bd)*Math.pow(10,n/2) +bd);
}
}
public static void main(String[] args) {
// 大整數相乘
long x = 12234L;
long y = 45243L;
String sx = String.valueOf(x);
int n = sx.length();
long sig = sign(x)*sign(y);
double s = bigdataride(x,y,n);
System.out.println("大數相乘的計算結果為："+s*sig);
}
}
解法二
模擬乘法
將兩個數分別存入兩個陣列，然后根據乘法規則兩層for回圈分別讓數字相乘，并存入一個新的陣列，大致為這樣：result[a+b] += num1[a]*num2[b];，現在這個result里存盤的就是一個非個位數的臨時結果，只需要做后將這個臨時結果分別進位便可得到最終結果
代碼如下：
import java.util.Scanner;
//創建類largenumberOperationMultiply
public class largenumberOperationMultiply {
//定義方法multiply的功能
public String multiply(String str1,String str2){
int[] num1 = new int[str1.length()];
int[] num2 = new int[str2.length()];
int[] result = new int[str1.length() + str2.length()];
//將兩個字串轉成整型陣列，順序轉換，陣列下標越小，數字對應的位數越高
for (int i = 0;i < str1.length(); i++){
num1[i] = Integer.parseInt(str1.substring(i,i+1));
}
for (int i = 0;i < str2.length(); i++){
num2[i] = Integer.parseInt(str2.substring(i,i+1));
}
//兩大數相乘
for (int a = 0;a < str1.length(); a++){
for (int b = 0;b < str2.length(); b++){
result[a+b] += num1[a]*num2[b];
}
}
////判斷是否需要進位，滿10進1,因為存盤順序與位數高低相反，所以采用逆序進位
int temp;
for (int k = result.length-1; k > 0; k--){
temp=result[k]/10; //陣列下標大的向陣列下標小的進位
result[k-1] += temp;
result[k] = result[k]%10;
}
//將結果陣列逆序轉化為字串
String resultstr = "";
for (int i = 0; i < result.length-1; i++){
resultstr += "" + result[i];
}
return resultstr;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("請輸入第一個數：");
String str1 = sc.next();
System.out.println("請輸入第二個數：");
String str2 = sc.next();
largenumberOperationMultiply bn = new largenumberOperationMultiply();
//創建類largenumberOperationMultiply的物件bn
String output = bn.multiply(str1,str2);
//bn物件呼叫multiply方法對str1和str2進行操作
System.out.println(str1+"與"+str2+"的積為："+output);
}
}
來個c版本的陣列實作大數乘法
#include<stdio.h>
#include<string.h>
#include<math.h>
#define N 1005
char a[N],b[N];
int s1[N],s2[N],s3[N*N];
int main()
{
int len1,len2,max,i,j;
while(scanf("%s%s",a,b)!=EOF)
{
memset(s1,0,sizeof(s1));
memset(s2,0,sizeof(s2));
memset(s3,0,sizeof(s3));
len1=strlen(a);
len2=strlen(b);
max=0;
max=len1+len2;
for(i=0,j=len1-1;i<len1;i++,j--)
s1[i]=a[j]-'0';
for(i=0,j=len2-1;i<len2;i++,j--)
s2[i]=b[j]-'0';
for(i=0;i<len1;i++)
for(j=0;j<len2;j++)
s3[i+j]+=s1[i]*s2[j];
for(i=0;i<max;i++)
{
if(s3[i]>=10)
{
s3[i+1]+=s3[i]/10;
s3[i]%=10;
}
}
while(s3[max-1]==0)
{
if(s3[max-1]==0)
max--;
}
for(i=max-1;i>=0;i--)
printf("%d",s3[i]);
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143250.html
標籤：其他
上一篇：2-程式與用戶互動