1

Тема: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

Я вирішив спробувати зробити цю задачу, бо вона прикладного характеру. Програма працює, але алготестер каже, що перевищено ліміт пам'яті.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String numbers = in.nextLine();
        String number1 = numbers.substring(0, numbers.indexOf(' ')),
                number2 = numbers.substring(numbers.indexOf(' ') + 1);
        numbers = null;
        boolean b1 = false;
        if (number1.length() > number2.length()) b1 = true;

        //створюю масив з запасом на 1 елемент, бо сума може бути більшою за більше з чисел
        byte arr[] = new byte[ (b1)?number1.length()+1:number2.length()+1 ];
        //менший з рядків збільшую до розмірів більшого рядка шляхом дописування на початку нулів
        while (number1.length() != number2.length()){
            if (b1) number2 = "0" + number2;
            else number1 = "0" + number1;
        }
        // кожну з цифр перетворюю в int і додаю (в стовпчик)
        for (int i = arr.length-1; i >0; i--){
             arr[i] +=  Integer.parseInt(number1.substring(i-1, i)) + Integer.parseInt(number2.substring(i-1, i));

            arr[i-1] = (byte)(arr[i]/10);
            arr[i]  %=10;
        }
        // якщо перша цифра не нуль, то виводжу
        if (arr[0] != 0) System.out.print(arr[0]);
        //виводжу всі наступні цифри
        for (int i = 1; i < arr.length; i++){
            System.out.print(arr[i]);
        }

    }
}

Також знаходив програми в Інтернеті, але знову і знову пише, що ліміт пам'яті на 2 прикладі.(Всі наступні програми не мої).

import java.util.*;

public class Main {
    int maxsize=0;
    int top=-1;
    int array []=new int [0];


    public Main (int size)
    {
        maxsize=size;
        array=new int [maxsize];
    }

    public void push (int x)
    {
        top=top+1;
        array[top]=x;
    }

    public int pop ()
    {
        int elt=array[top];
        top--;
        return elt;

    }

    public boolean stackisfull()
    {
        return(top==maxsize-1);
    }

    public boolean stackisempty()
    {
        return(top==-1);
    }

    public int peak ()
    {
        int peak =array[top];
        return peak;
    }

    public static void main (String args[]){
        Scanner in=new Scanner (System.in);

        String number = in.nextLine();

        String number1 = number.substring(0,(number.indexOf(' ')) );
        String number2 = number.substring(number.indexOf(' ')+1);

        String temp="";




        if(number1.length()>number2.length())
        {
            temp=number1;
            number1=number2;
            number2=temp;
        }

        int k=0;


        Main S1 = new Main (number1.length());

        for(int i=0;i<number1.length();i++)
        {
            String str=Character.toString(number1.charAt(i));
            S1.push(Integer.parseInt(str));
        }

        Main S2 = new Main (number2.length());

        for(int i=0;i<number2.length();i++)
        {
            String str=Character.toString(number2.charAt(i));
            S2.push(Integer.parseInt(str));
        }

        Main S3 =new Main (number2.length());

        while(!S1.stackisempty())
        {
            int x=S1.pop();
            int y=S2.pop();

            int times=(x+y+k)/10; int remainder =(x+y+k)%10;
            k=0;

            if(times==0)
            {
                S3.push(remainder);
            }

            else
            {
                S3.push(remainder);
                k=1;
            }
        }
        while(!S2.stackisempty())
        {
            if(k==1)
            {
                S3.push(k+S2.pop());
                k=0;
            }
            else
                S3.push(S2.pop());
        }

        if ( Integer.parseInt(number1.substring(0,1)) + Integer.parseInt(number2.substring(0,1)) >9 ){
            System.out.print( (Integer.parseInt(number1.substring(0,1)) + Integer.parseInt(number2.substring(0,1)))/10 );
        }

        while(!S3.stackisempty())
        {
            System.out.print(S3.pop());
            //if ( Integer.parseInt(number1.substring(0,1)) + Integer.parseInt(number2.substring(0,1)) >9 ){
            //
            //}
        }

    }
}
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String number = in.nextLine();

        String number1 = number.substring(0,(number.indexOf(' ')) );
        String number2 = number.substring(number.indexOf(' ')+1);
        BigInteger a = new BigInteger(number1);
        BigInteger b = new BigInteger(number2);
        System.out.println( a.add(b) );

    }


}
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String number = in.nextLine();

        String number1 = number.substring(0,(number.indexOf(' ')) );
        String number2 = number.substring(number.indexOf(' ')+1);
        System.out.println(findSum(number1,number2));

    }

    static String findSum(String str1, String str2)
    {
        // Before proceeding further, make sure length
        // of str2 is larger.
        if (str1.length() > str2.length()){
            String t = str1;
            str1 = str2;
            str2 = t;
        }

        // Take an empty String for storing result
        String str = "";

        // Calculate length of both String
        int n1 = str1.length(), n2 = str2.length();
        int diff = n2 - n1;

        // Initially take carry zero
        int carry = 0;

        // Traverse from end of both Strings
        for (int i = n1 - 1; i>=0; i--)
        {
            // Do school mathematics, compute sum of
            // current digits and carry
            int sum = ((int)(str1.charAt(i)-'0') +
                    (int)(str2.charAt(i+diff)-'0') + carry);
            str += (char)(sum % 10 + '0');
            carry = sum / 10;
        }

        // Add remaining digits of str2[]
        for (int i = n2 - n1 - 1; i >= 0; i--)
        {
            int sum = ((int)(str2.charAt(i) - '0') + carry);
            str += (char)(sum % 10 + '0');
            carry = sum / 10;
        }

        // Add remaining carry
        if (carry > 0)
            str += (char)(carry + '0');

        // reverse resultant String
        return new StringBuilder(str).reverse().toString();
    }

}
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String number = in.nextLine();

        String number1 = number.substring(0,(number.indexOf(' ')) );
        String number2 = number.substring(number.indexOf(' ')+1);
        System.out.println(findSum(number1,number2));

    }

    static String findSum(String str1, String str2)
    {
        // Before proceeding further, make sure length
        // of str2 is larger.
        if (str1.length() > str2.length()){
            String t = str1;
            str1 = str2;
            str2 = t;
        }

        // Take an empty String for storing result
        String str = "";

        // Calculate length of both String
        int n1 = str1.length(), n2 = str2.length();

        // Reverse both of Strings
        str1=new StringBuilder(str1).reverse().toString();
        str2=new StringBuilder(str2).reverse().toString();

        int carry = 0;
        for (int i = 0; i < n1; i++)
        {
            // Do school mathematics, compute sum of
            // current digits and carry
            int sum = ((int)(str1.charAt(i) - '0') +
                    (int)(str2.charAt(i) - '0') + carry);
            str += (char)(sum % 10 + '0');

            // Calculate carry for next step
            carry = sum / 10;
        }

        // Add remaining digits of larger number
        for (int i = n1; i < n2; i++)
        {
            int sum = ((int)(str2.charAt(i) - '0') + carry);
            str += (char)(sum % 10 + '0');
            carry = sum / 10;
        }

        // Add remaining carry
        if (carry > 0)
            str += (char)(carry + '0');

        // reverse resultant String
        str = new StringBuilder(str).reverse().toString();

        return str;
    }

}

Буду вдячний за допомогу!

2

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

https://algotester.com/uk/ArchiveProble … File/40149

3

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

Гадаю, проблема в тому, що Java не звільняє пам'ять без потреби. В результаті ось такі фокуси

        while (number1.length() != number2.length()){
            if (b1) number2 = "0" + number2;
            else number1 = "0" + number1;
        }

призводять до купи шматочків, які чекають на звільнення, але поки що займають місце.
Можете пододавати

System.gc();

в усі місця, де може переповнитися пам'ять.
Якщо не допоможе - виділяйте масиви фіксованого максимального розміру (111111 для вхідних і 111112 для результату) і читайте вхід по одному символу.

Подякували: zxzpogoncuk1

4

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

koala написав:

Якщо не допоможе - виділяйте масиви фіксованого максимального розміру (111111 для вхідних і 111112 для результату) і читайте вхід по одному символу.

InputStreamReader scanner = new InputStreamReader(System.in);
        char a = (char) scanner.read();

Але довжина вхідного рядка завжди різна і я не знаю , як зробити так, щоб коли рядок закінчився scanner перестав чекати нових символів.

5 Востаннє редагувалося koala (05.07.2020 23:09:09)

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

А вам тут не сканер потрібен. System.in.read() цілком впорається. Просто запам'ятовуйте, скільки цифр ви прочитали в яке число, і потім додавайте з відповідного місця.

Я тут накидав код, що проходить тести, але він усе одно 30МБ зжирає.

ще з універу не люблю жабу

Загалом це можна розгорнути в одну функцію, але тоді доведеться повторювати все введення/обмін по два рази. А так ніби зручніше читається.

class LongInteger {
    public LongInteger() {
        digits = new byte[111112];
        digits[0]=0;//це можна пропустити, але так явно показуємо, що перша цифра в 111112-значному числі - 0, а вводимо з другої
        length = 0; //теж можна пропустити, але теж показуємо явно
        try
        {
            while(true)
            {
                int inp = System.in.read()-'0'; //брудний хак - цифри в кодуванні ідуть поспіль, починаючи з 0
                if(inp<0||9<inp) //якщо це не цифра або не прочиталося - в кінці файлу буде -1
                    break;
                digits[++length] = (byte) inp;//заповнюємо з digits[1].
            }
        }
        catch(java.io.IOException e){ //інакше треба на метод ставити throws
        }
    }
    public int get_length() { return length; }
    public void add_shorter(LongInteger other) {
        for(int i_other=other.length,i_this=length;i_this>=0;i_other--,i_this--) { //ідемо по двох числах одночасно
            if(i_other>=0){ //якщо коротше не скінчилося
                digits[i_this] += other.digits[i_other];
            } else if(digits[i_this]<10) { //якщо скінчилося і немає переповнення
                break;
            }
            if(digits[i_this]>=10){ //переповнення
                digits[i_this] -= 10;
                digits[i_this-1] += 1;
            }
        }
    }
    public void print()
    {
        if(digits[0]!=0) //пропускаємо перший 0
            System.out.print(digits[0]);
        for(int i=1;i<=length;i++)
            System.out.print(digits[i]);
    }
    
    private byte[] digits;
    private int length;
}

public class Main {
    public static void main(String[] args) {
        LongInteger number1 = new LongInteger();
        LongInteger number2 = new LongInteger();
        if(number1.get_length()<number2.get_length()) { //якщо друге довше - міняємо їх місцями
            LongInteger temp = number1;
            number1 = number2;
            number2 = temp;
        }
        number1.add_shorter(number2); //додаємо коротше до довшого, щоб не зсувати цифри
        number1.print();
    }
}
Подякували: zxzpogoncuk1

6

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

:| Щось лісапеди в цій країні останнім часом стали дуже актуальні, саме тоді, коли в Java вже давно є клас BigInteger. і хоча користуватися ним без милиць складно, я дуже сумніваюсь, що він гірший за лісапеди

Подякували: zxzpogoncuk1

7 Востаннє редагувалося koala (06.07.2020 07:45:23)

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

ur_naz написав:

:| Щось лісапеди в цій країні останнім часом стали дуже актуальні, саме тоді, коли в Java вже давно є клас BigInteger. і хоча користуватися ним без милиць складно, я дуже сумніваюсь, що він гірший за лісапеди

Вам ніхто не заважає скористатися класом BigInteger, як це зробив я, і переконатися, що розв'язок не проходить через обмеження. Чи вам аби лише ляпнути?

Подякували: leofun01, ExPy, zxzpogoncuk3

8

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

Зверніть увагу на обмеження вхідних даних і памяті. Там треба користувати стрічки, але перед цим почитайте скільки байт може зберігати String в Java.

підказка

2^16

9

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

З чого б це раптом?
https://stackoverflow.com/questions/117 … tring-have

І я ще раз наголошую: проблема тут не в типах даних, а в неадекватно налаштованому GC.

Подякували: leofun01, zxzpogoncuk2

10

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

koala написав:

З чого б це раптом?

Копайте глибше

11

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

Вибачте, але це не внутрішнє представлення String. Це DataInput так кодує. Там поруч є експерименти з довшими за 0xFFFF стрічками - і там воно зупиняється в районі 0x7FFFFFFD. DataInput таке не з'їсть, але ж з цього ніяк не випливає, що внутрішнє представлення String таке.

Подякували: leofun01, zxzpogoncuk2

12

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

koala написав:
class LongInteger {
    public LongInteger() {
        digits = new byte[111112];
        digits[0]=0;//це можна пропустити, але так явно показуємо, що перша цифра в 111112-значному числі - 0, а вводимо з другої
        length = 0; //теж можна пропустити, але теж показуємо явно
        try
        {
            while(true)
            {
                int inp = System.in.read()-'0'; //брудний хак - цифри в кодуванні ідуть поспіль, починаючи з 0
                if(inp<0||9<inp) //якщо це не цифра або не прочиталося - в кінці файлу буде -1
                    break;
                digits[++length] = (byte) inp;//заповнюємо з digits[1].
            }
        }
        catch(java.io.IOException e){ //інакше треба на метод ставити throws
        }
    }
    public int get_length() { return length; }
    public void add_shorter(LongInteger other) {
        for(int i_other=other.length,i_this=length;i_this>=0;i_other--,i_this--) { //ідемо по двох числах одночасно
            if(i_other>=0){ //якщо коротше не скінчилося
                digits[i_this] += other.digits[i_other];
            } else if(digits[i_this]<10) { //якщо скінчилося і немає переповнення
                break;
            }
            if(digits[i_this]>=10){ //переповнення
                digits[i_this] -= 10;
                digits[i_this-1] += 1;
            }
        }
    }
    public void print()
    {
        if(digits[0]!=0) //пропускаємо перший 0
            System.out.print(digits[0]);
        for(int i=1;i<=length;i++)
            System.out.print(digits[i]);
    }
    
    private byte[] digits;
    private int length;
}

public class Main {
    public static void main(String[] args) {
        LongInteger number1 = new LongInteger();
        LongInteger number2 = new LongInteger();
        if(number1.get_length()<number2.get_length()) { //якщо друге довше - міняємо їх місцями
            LongInteger temp = number1;
            number1 = number2;
            number2 = temp;
        }
        number1.add_shorter(number2); //додаємо коротше до довшого, щоб не зсувати цифри
        number1.print();
    }
}

Пане koala, дякую за допомогу! Ваша програма супер, але найкрутіше те, що я зрозумів кожен її рядок.

13 Востаннє редагувалося koala (07.07.2020 23:29:13)

Re: Сума двох величезних натуральних чисел. Алготестер задача № 0346.

До речі, на repl.it спокійно все обходиться 2,5МБ. Причому найбільше, як я зрозумів, виїдає println на буфери.

Подякували: zxzpogoncuk1