Тема: Сума двох величезних натуральних чисел. Алготестер задача № 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;
}
}Буду вдячний за допомогу!
Щось лісапеди в цій країні останнім часом стали дуже актуальні, саме тоді, коли в Java вже давно є клас BigInteger. і хоча користуватися ним без милиць складно, я дуже сумніваюсь, що він гірший за лісапеди