我正在尝试将两个数字相乘,它们是正整数并且它们具有相同的位数,递归地进行分而治之,我正在尝试这样做:T(n)=4T(n/2)+O(n) 注意:我知道它在 theta(n^2) 中运行,这太糟糕了!这对我来说只是一个练习。 谢谢你,抱歉我的英语不好。 :) 我的问题是:我的错误在哪里? algorithm based on this doc 这是代码:
import java.util.Scanner;
public class main {
static int res=0;
static int stage =0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] Num1;
char[] Num2;
String num1 = in.nextLine();
String num2 = in.nextLine();
in.close();
Num1 = num1.toCharArray();
Num2 = num2.toCharArray();
DaQMultiplay(Num1, Num2);
System.out.println(res);
}
static int DaQMultiplay(char[] num1,char[] num2){
if(num1.length<2){
stage++;
int num1sd =Integer.parseInt(new String(num1));
int num2sd =Integer.parseInt(new String(num2));
return (num1sd*num2sd);
}
stage++;
double len = num1.length;
int lenl = (int) Math.ceil(len/2);
char []ln1 = new char[lenl];
char []rn1 = new char[(int) (len-lenl)];
char []ln2 = new char[lenl];
char []rn2 = new char[(int) (len-lenl)];
for (int i = 0; i < ln1.length; i++) {
ln1[i]=num1[i];
}
for (int i = 0; i < rn1.length; i++) {
rn1[i]=num1[i+lenl];
}
for (int i = 0; i < ln2.length; i++) {
ln2[i]=num2[i];
}
for (int i = 0; i < rn2.length; i++) {
rn2[i]=num2[i+lenl];
}
System.out.print("Left Side of num1:"+stage+" ");
System.out.println(ln1);
System.out.print("Right Side of num1:"+stage+" ");
System.out.println(rn1);
System.out.print("Left Side of num2:"+stage+" ");
System.out.println(ln2);
System.out.print("Right Side of num2:"+stage+" ");
System.out.println(rn2);
res+=DaQMultiplay(ln1,ln2)*(10^((int)len));
System.out.println("res: "+res);
res+=DaQMultiplay(ln1,rn2)*10^((int) (len-lenl));
System.out.println("res: "+res);
res+=DaQMultiplay(rn1,ln2)*10^((int) (len-lenl));
System.out.println("res: "+res);
res+=DaQMultiplay(rn1, rn2);
System.out.println("res: "+res);
return 0;
}
}
输出:num1=20011,num2=91281
20011
91281
Left Side of num1:1 200
Right Side of num1:1 11
Left Side of num2:1 912
Right Side of num2:1 81
Left Side of num1:2 20
Right Side of num1:2 0
Left Side of num2:2 91
Right Side of num2:2 2
Left Side of num1:3 2
Right Side of num1:3 0
Left Side of num2:3 9
Right Side of num2:3 1
res: 144
res: 164
res: 164
res: 0
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
at main.DaQMultiplay(main.java:46)
at main.DaQMultiplay(main.java:63)
at main.DaQMultiplay(main.java:61)
at main.main(main.java:19)
最佳答案
通常,您的代码不会处理 num2 在 num1 之前解析为单个数字的情况。这会导致 DaQ 方法产生一个空字符串,最终引发异常。您需要首先添加对 num2 解析处理的检查。此检查解决了第一个异常(第 46 行左右):
for (int i = 0; i < rn2.length; i++) {
if(num2.length>i+lenl){
rn2[i]=num2[i+lenl];
}
}
然后你需要在乘法阶段添加一个检查: int num1sd = 1; int num2sd = 1;
if(num1!=null && !num1.equals("") && new String(num2).trim().length()>0){
num1sd =Integer.parseInt(new String(num1));
}
if(num2!=null && !num2.equals("") && new String(num2).trim().length()>0){
num2sd=Integer.parseInt(new String(num2));
}
我不确定第二个检查是否适合您编写的算法,但总体思路是这个 if 语句 if(num1.length<2){...
仅处理 num1 首先解析的情况,但情况并非总是如此。
更正了代码,但仍然传递了错误的答案:
import java.util.Scanner;
public class main {
static int res=0;
static int pow;
static int stage =0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] Num1;
char[] Num2;
String num1 = in.nextLine();
String num2 = in.nextLine();
in.close();
Num1 = num1.toCharArray();
Num2 = num2.toCharArray();
pow = Num1.length;
DaQMultiplay(Num1, Num2);
System.out.println(res);
}
static int DaQMultiplay(char[] num1,char[] num2){
if(num1.length<2){
stage++;
int num1sd = 0;
int num2sd = 0;
if(num1!=null && !num1.equals("") && new String(num2).trim().length()>0){
num1sd =Integer.parseInt(new String(num1));
}
if(num2!=null && !num2.equals("") && new String(num2).trim().length()>0){
num2sd=Integer.parseInt(new String(num2));
}
return (num1sd*num2sd);
}
stage++;
double len = num1.length;
int lenl = (int) Math.ceil(len/2);
char []ln1 = new char[lenl];
char []rn1 = new char[(int) (len-lenl)];
char []ln2 = new char[lenl];
char []rn2 = new char[(int) (len-lenl)];
for (int i = 0; i < ln1.length; i++) {
ln1[i]=num1[i];
}
for (int i = 0; i < rn1.length; i++) {
rn1[i]=num1[i+lenl];
}
for (int i = 0; i < ln2.length; i++) {
ln2[i]=num2[i];
}
for (int i = 0; i < rn2.length; i++) {
if(num2.length>i+lenl){
rn2[i]=num2[i+lenl];
}
}
System.out.print("Left Side of num1:"+stage+" ");
System.out.println(ln1);
System.out.print("Right Side of num1:"+stage+" ");
System.out.println(rn1);
System.out.print("Left Side of num2:"+stage+" ");
System.out.println(ln2);
System.out.print("Right Side of num2:"+stage+" ");
System.out.println(rn2);
res+=(DaQMultiplay(ln1,ln2)*(Math.pow(10, len)));
System.out.println(res);
res+=(DaQMultiplay(rn1,ln2)*(Math.pow(10, (len/2))));
System.out.println(res);
res+=(DaQMultiplay(ln1,rn2)*(Math.pow(10, (len/2))));
System.out.println(res);
res+=(DaQMultiplay(rn1, rn2));
System.out.println(res);
return 0;
}
}
新输出:num1=,num2=
20011
91281
Left Side of num1:1 200
Right Side of num1:1 11
Left Side of num2:1 912
Right Side of num2:1 81
Left Side of num1:2 20
Right Side of num1:2 0
Left Side of num2:2 91
Right Side of num2:2 2
Left Side of num1:3 2
Right Side of num1:3 0
Left Side of num2:3 9
Right Side of num2:3 1
1800
1800
1820
1820
0
0
Left Side of num1:9 2
Right Side of num1:9 0
Left Side of num2:9 2
Right Side of num2:9
而且算法的实现问题依然存在......
关于java - 用分治法java将两个十进制整数相乘,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26787733/