Умножение двух десятичных целых чисел с divide и conquer java

Question

Я пытаюсь умножить два числа, которые являются положительными целыми числами, и они имеют одинаковое количество цифр, с делением и побегом рекурсивно, я пытаюсь сделать что-то вроде этого : T (n) = 4T (n/2) + O (n) Примечание: я знаю, что он работает в тета (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)  

Answer 1

вот полная программа, и все работает нормально:

import java.io.ObjectInputStream.GetField; 
import java.util.Scanner; 

public class main { 
    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(); 
     check(Num1, Num2); 
    } 
    static int DaQMultiplay(char[] num1,char[] num2){ 
     int res=0; 
     if(num1.length<=1){ 
      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); 
     } 
     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]; 
      } 
     } 

     res+=(DaQMultiplay(ln1,ln2)*(Math.pow(10, len))); 
     res+=(DaQMultiplay(rn1,ln2)*(Math.pow(10, (len/2)))); 
     res+=(DaQMultiplay(ln1,rn2)*(Math.pow(10, (len/2)))); 
     res+=(DaQMultiplay(rn1, rn2)); 

     return res; 
    } 
    static void check(char []Num1,char []Num2){ 
     int res=0; 
     if ((Num1.length%2)==0) { 
      res=DaQMultiplay(Num1, Num2); 
      System.out.println(res); 
     } 
     else{ 
      String num1 = String.valueOf(Num1); 
      num1 = num1+"0"; 
      String num2 = String.valueOf(Num2); 
      num2 = num2+"0"; 
      Num1=num1.toCharArray(); 
      Num2=num2.toCharArray(); 
      res=DaQMultiplay(Num1, Num2); 
      res=(res/100); 
      System.out.println(res); 
     } 
    } 
} 

Answer 2

Обычно код не обрабатывает случай, когда 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(num1.length<2){... только hanldes случай, когда 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 

и проблему, реализации алгоритма все еще существует ...