В моем java-задании нам была поставлена задача умножить произвольно большое число, хранящееся в виде списка массивов, с помощью обычного алгоритма умножения в начальной школе. Итак, я сделал четыре функции. Одна функция для добавления двух списков массивов за O (n). Во-вторых, для сдвига числа на 0, то есть умножения на степень 10. Третий для умножения одной цифры на список массивов в O (n). Четвертый для умножения ArrayList.
package lecture.files;
import java.util.Arrays;
import java.util.ArrayList;
public class FastMult {
public static ArrayList<Integer> norm_mult(ArrayList<Integer> a_1,int b_1) {
ArrayList<Integer> result = new ArrayList<Integer>();
int carry=0,a = 0;
for(int i = 0;i<=a_1.size();i++) {
if(carry == 0 & i == a_1.size()) {
break;
}
a = 0;
if((a_1.size()-1-i) >= 0)
a = a_1.get(a_1.size()-1-i);
result.add(0,(a*b_1+carry)%10);
carry = (a*b_1 + carry)/10;
}
return result;
}
public static ArrayList<Integer> multiply(ArrayList<Integer> a_1,ArrayList<Integer> b_1){
ArrayList<Integer> result = new ArrayList<Integer>(Arrays.asList(0));
ArrayList<Integer> temp = new ArrayList<Integer>();
int size = b_1.size();
if(a_1.size()>b_1.size())
size = a_1.size();
for(int i = 0;i<size;i++) {
int b = 0;
if((b_1.size()-1-i) >= 0)
b = b_1.get(b_1.size()-1-i);
temp = norm_mult(a_1,b);
temp = left_shift(temp,i);
result = add(result,temp);
}
return result;
}
public static ArrayList<Integer> add(ArrayList<Integer> a_1,ArrayList<Integer> b_1) {
int size = b_1.size();
if(a_1.size()>b_1.size())
size = a_1.size();
int a1=0,b1=0,carry=0;
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i = 0;i<=size;i++) {
a1=0;b1=0;
if(carry == 0 & i == size) {
break;
}
if(i<a_1.size())
a1 = a_1.get(a_1.size()-1-i);
if(i<b_1.size())
b1 = b_1.get(b_1.size()-1-i);
result.add(0,(a1 + b1 +carry)%10);
carry = (a1 + b1 + carry)/10;
}
return result;
}
public static ArrayList<Integer> left_shift(ArrayList<Integer> a,int shift) {
ArrayList<Integer> result = a;
for(int i = 1;i<=shift;i++) {
result.add(0);
}
return result;
}
public static ArrayList<Integer> string_to_array(String no){
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=1;i<=no.length();i++) {
char a = no.charAt(no.length()-i);
int num = Character.getNumericValue(a);
result.add(0, num);
}
return result;
}
public static void main(String args[]) {
ArrayList<Integer> a = string_to_array("886656");
ArrayList<Integer> b = string_to_array("88");
ArrayList<Integer> result = multiply(a,b);
System.out.println(result);
}
}
Результаты верны, но на выходе я получаю заполнение нулями. Я хочу удалить его. Как сделать функцию обрезки нулей?