Как добавить два очень больших числа независимо от их размера в Java без использования типа данных BigInteger? - PullRequest
Новая
       11

Как добавить два очень больших числа независимо от их размера в Java без использования типа данных BigInteger?

0 голосов
/ 13 ноября 2018

Мне нужно добавить два очень больших числа без использования BigInteger.Я беру два строковых параметра, но приведенный ниже код работает только со строками одинаковой длины, в противном случае он выдает IndexOutOfBoundsException.Как я могу это исправить, добавив большие числа независимо от их длины? 

public static String add(String a, String b) {
    int carry = 0;
    String result = "";

    for (int i = a.length() - 1; i >= 0; i--) {
      int digitA = a.charAt(i) - 48;
      int digitB = b.charAt(i) - 48;

      int resultingNumber = digitA + digitB + carry;
      if (resultingNumber >= 10) {
        result = (resultingNumber % 10) + result;
        carry = 1;
      } else {
        result = resultingNumber + result;
        carry = 0;
      }
    }
    if (carry > 0) {
      result = carry + result;
    }
    return result;
}

Ответы [ 3 ]

0 голосов
/ 13 ноября 2018

Вы можете оставить панель с нулями в строках следующим образом: 

    int longestString = Math.max(a.length(), b.length());
    a = String.format("%1$" + longestString + "s", a).replace(' ', '0');
    b = String.format("%1$" + longestString + "s", b).replace(' ', '0');

Это добавит пробелы, чтобы заполнить «пробел», а затем заменит их нулями.

Класс: 

public class Mission09 {
    public static void main(String[] args) {
        System.out.println(add("1", "1333"));
    }

    public static String add(String a, String b) {
        int carry = 0;
        String result = "";

        int longestString = Math.max(a.length(), b.length());

        a = String.format("%1$" + longestString + "s", a).replace(' ', '0');
        b = String.format("%1$" + longestString + "s", b).replace(' ', '0');


        for (int i = a.length() - 1; i >= 0; i--) {
            int digitA = a.charAt(i) - 48;
            int digitB = b.charAt(i) - 48;

            int resultingNumber = digitA + digitB + carry;
            if (resultingNumber >= 10) {
                result = (resultingNumber % 10) + result;
                carry = 1;
            } else {
                result = resultingNumber + result;
                carry = 0;
            }
        }
        if (carry > 0) {
            result = carry + result;
        }
        return result;
    }

}

I / O: 

System.out.println(add("1", "1333"));
1334
System.out.println(add("12222", "1333"));
13555
0 голосов
/ 13 ноября 2018

Нет необходимости дополнять любые параметры нулями.Кроме того, для повышения производительности не используйте String + String.

. Создайте char[] для результата.Поскольку результат может быть на 1 длиннее самого длинного ввода, создайте его с таким размером.

Затем выполните итерацию с конца входных строк, установив каждый символ в результате.

Затем исключите все начальные нули, возникающие из-за того, что входы не переполняются, или из-за входов с начальными нулями.

Наконец, создайте String из char[], используя конструктор String(char[] value, int offset, int count).

Вот так: 

public static String add(String a, String b) {
    int i = a.length();
    int j = b.length();
    int k = Math.max(i, j) + 1; // room for carryover
    char[] c = new char[k];
    for (int digit = 0; k > 0; digit /= 10) {
        if (i > 0)
            digit += a.charAt(--i) - '0';
        if (j > 0)
            digit += b.charAt(--j) - '0';
        c[--k] = (char) ('0' + digit % 10);
    }
    for (k = 0; k < c.length - 1 && c[k] == '0'; k++) {/*Skip leading zeroes*/}
    return new String(c, k, c.length - k);
}

Тест 

public static void main(String[] args) {
    test("1234", "2345");   // test equal-sized inputs, no carry-over
    test("12345", "12345"); // test equal-sized inputs, with carry-over
    test("54321", "54321"); // test equal-sized inputs, longer result
    test("99999", "99999"); // test max result
    test("5", "1234");      // test odd-sized inputs, no carry-over
    test("5", "12345");     // test odd-sized inputs, with carry-over
    test("1", "99999");     // test with a carry-over to longer result
    test("001", "00002");   // test leading zeroes in input are eliminated
    test("000", "00000");   // test leading zero removal leaves 1 zero
}
public static void test(String a, String b) {
    // Test add is commutative, i.e. a+b = b+a
    System.out.printf("%s + %s = %s = %s%n", a, b, add(a, b), add(b, a));
}

Выход 

1234 + 2345 = 3579 = 3579
12345 + 12345 = 24690 = 24690
54321 + 54321 = 108642 = 108642
99999 + 99999 = 199998 = 199998
5 + 1234 = 1239 = 1239
5 + 12345 = 12350 = 12350
1 + 99999 = 100000 = 100000
001 + 00002 = 3 = 3
000 + 00000 = 0 = 0
0 голосов
/ 13 ноября 2018

Вы можете добавить к короткой строке нули, чтобы она соответствовала длине другого числа: 

private static String leftPad(String s, int length) {
    if (s.length() >= length)
        return s;

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < length - s.length(); i++)
        sb.append("0");

    return sb.toString() + s;
}

public static String add(String originalA, String originalB) {

    int maxLength = Math.max(originalA.length(), originalB.length());
    String a = leftPad(originalA, maxLength);
    String b = leftPad(originalB, maxLength);

    ... rest of your method
...