Сложение столбиков двух массивов чисел

@PlayaRC · Регистрация: 10.03.2012

Author24 — интернет-сервис помощи студентам

Например есть два массива

C++

1 2	int a[13]={2,8,3,9,4,7,5,8,6,7,3,8,2}; int b[8]={4,7,3,8,5,7,3,8};

Как мне их сложить в столбик (длинная арифметика)?

Беру остаток от деления на 10 суммы двух элементов массива и одинаковыми индексами, а как сделать перенос 1цы в следующий разряд не пойму.

C++

void sum()
{
    for(int i=0; i<max_len; i++)
    {
        s=0;
        if(a[i]+b[i]>9)
            s=1;
        c[i]=(a[i]+b[i])%10;
    }
}

Заранее спасибо за ответы!

@UnsKneD · 21.03.2013, 03:03

Сложение столбиком

@PlayaRC · 21.03.2013, 13:50 **[ТС]**

Сообщение от UnsKneD

Сложение столбиком

не особо понимаю, как сказанное в этой теме реализовать на моем примере, не могли бы вы показать?

Добавлено через 25 минут
Все, разобрался.

Может кому понадобится код всей программы.

"Сложение больших чисел столбиком"

C++

#include <stdlib.h>
#include <iostream>
using namespace std;
 
class bigint
{
    int a[256], b[256], c[256];
    int s, len_a, len_b, max_len;
 
public:
    bigint(int [], int [], int, int);
    void show();
    void sum();
};
 
bigint::bigint(int a[], int b[], int len_a, int len_b)
{
    s=0;
 
    bigint::len_a = len_a;
    bigint::len_b = len_b;
 
    int k;
 
    for(int i=0; i<len_a; i++)
    {
        bigint::a[i]=a[i];
    }
    for(int i=0; i<len_a/2; i++)
    {
        k=bigint::a[i];
        bigint::a[i]=bigint::a[len_a-i-1];
        bigint::a[len_a-i-1]=k;
    }
 
    for(int i=0; i<len_b; i++)
    {
        bigint::b[i]=b[i];
    }
    for(int i=0; i<len_b/2; i++)
    {
        k=bigint::b[i];
        bigint::b[i]=bigint::b[len_b-i-1];
        bigint::b[len_b-i-1]=k;
    }
 
    if(len_a<len_b)
    {
        max_len = len_b;
        for(int i=0; i<len_b-len_a; i++)
        {
            bigint::a[len_a+i]=0;
        }
    }
    if(len_b<len_a)
    {
        max_len = len_a;
        for(int i=0; i<len_a-len_b; i++)
        {
            bigint::b[len_b+i]=0;
        }
    }
}
 
void bigint::show()
{
    cout<<"Первое число = ";
    for(int i=0; i<max_len; i++)
        cout<<a[i];
    cout<<", размером в "<<len_a<<" символов"<<endl;
 
    cout<<"Второе число = ";
    for(int i=0; i<max_len; i++)
        cout<<b[i];
    cout<<", размером в "<<len_b<<" символов"<<endl;
    cout<<"Сумма = ";
    for(int i=max_len-1; i>=0; i--)
        cout<<c[i];
}
 
void bigint::sum()
{
    int i, k;
    for(k=0; k<max_len; k++)
        c[k]=0;
    for(i=max_len-1; i>=0; i--)
    {
        s=0;
        if(a[i]+b[i]>9)
        {
            s=1;
            c[i+1]+=s;
        }
        c[i]=(a[i]+b[i])%10;
    }
}
 
int main()
{
    setlocale(0, "rus");
 
    int a[13]={2,8,3,9,4,7,5,8,6,7,3,8,2};
    int b[8]={4,7,3,8,5,7,3,8};
 
    bigint str(a, b, 13, 8);
    str.sum();
    str.show();
 
    return 0;
}

Добавлено через 16 минут
Теперь не могу сделать вычитание, прошу рассказать хотя бы алгоритм, заранее спасибо!

@vua72 · 21.03.2013, 15:05

Вычитаете начиная с младшего разряда, если уменьшаемое меньше вычитаемого прибавляем 10 к уменьшаемому, производим вычитание, затем вычитаем единицу из вычитаемого следующего разряда и т.д.. Если заем из разряда старше вашего старшего - получили отрицательное число

Добавлено через 8 минут
И еще, вы фактически для хранения одного разряда используете 4 байта, хотя по логике вашей задачи - достаточно 1 байта (даже его половины). Почему не сделать массив unsigned char?

@PlayaRC · 21.03.2013, 20:36 **[ТС]**

Сообщение от vua72

Вычитаете начиная с младшего разряда, если уменьшаемое меньше вычитаемого прибавляем 10 к уменьшаемому, производим вычитание, затем вычитаем единицу из вычитаемого следующего разряда и т.д.. Если заем из разряда старше вашего старшего - получили отрицательное число

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

...затем вычитаем единицу из вычитаемого следующего разряда и т.д..

нужно вычитать единицу из уменьшаемого следующего разряда.

Добавлено через 8 минут
И еще, вы фактически для хранения одного разряда используете 4 байта, хотя по логике вашей задачи - достаточно 1 байта (даже его половины). Почему не сделать массив unsigned char?

а по поводу этого даже не задумывался, сейчас исправлю, спасибо еще раз!

Добавлено через 1 минуту
И вдруг кому понадобиться, выкладываю код функции вычитания:

C++

void minus()
{
    int i, k;
    for(k=0; k<max_len; k++)
        f[k]=0;
    for(i=0; i<max_len; i++)
    {
        s=0;
        if(a[i]<b[i])
        {
            a[i]+=10;
            s=1;
        }
        f[i]=a[i]-b[i];
        a[i+1]-=s;
    }
}

@PlayaRC · 21.03.2013, 21:25 **[ТС]**

еще вопрос: Почему например при вычитании\сложении числа, например: a[]={123456789844346} + b[]={53262354312} все считает нормально, а если ввожу a[]={999999999999999} + b[]={99999999999}

@UnsKneD · 21.03.2013, 21:52

PlayaRC, для int максимальное значение 2 147 483 647

Добавлено через 2 минуты
если нужно складывать такие большие числа, используй long long int
http://ru.wikipedia.org/wiki/Limits.h

Добавлено через 1 минуту

C++

1 2	int a = 999999999999999; std::cout<<a<<std::endl;

Попробуй так сделать, выдаст полную ерунду.

@PlayaRC · 21.03.2013, 21:59 **[ТС]**

Сообщение от UnsKneD

PlayaRC, для int максимальное значение 2 147 483 647

Добавлено через 2 минуты
если нужно складывать такие большие числа, используй long long int
http://ru.wikipedia.org/wiki/Limits.h

так я ведь вношу числа в массив! то есть в одной ячейке максимальное число = 9

@UnsKneD · 21.03.2013, 22:18

PlayaRC, ой, точно же)
а ты функции правильные размеры массивов передаёшь?

@PlayaRC · 21.03.2013, 22:25 **[ТС]**

Сообщение от UnsKneD

PlayaRC, ой, точно же)
а ты функции правильные размеры массивов передаёшь?

вот весь код, вроде правильные

C++

#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
 
class bigint
{
    int a[256], b[256], c[256], f[256], back_a[256];
    int s, len_a, len_b, max_len;
 
public:
    bigint(int [], int [], int, int);
    void show();
    void sum();
    void minus();
};
 
bigint::bigint(int a[], int b[], int len_a, int len_b)
{
    s=0;
 
    bigint::len_a = len_a;
    bigint::len_b = len_b;
 
    int k;
 
    for(int i=0; i<len_a; i++)
    {
        bigint::a[i]=a[i];
    }
    for(int i=0; i<len_a/2; i++)
    {
        k=bigint::a[i];
        bigint::a[i]=bigint::a[len_a-i-1];
        bigint::a[len_a-i-1]=k;
    }
 
    for(int i=0; i<len_b; i++)
    {
        bigint::b[i]=b[i];
    }
    for(int i=0; i<len_b/2; i++)
    {
        k=bigint::b[i];
        bigint::b[i]=bigint::b[len_b-i-1];
        bigint::b[len_b-i-1]=k;
    }
 
    if(len_a<len_b)
    {
        max_len = len_b;
        for(int i=0; i<len_b-len_a; i++)
        {
            bigint::a[len_a+i]=0;
        }
    }
    if(len_b<len_a)
    {
        max_len = len_a;
        for(int i=0; i<len_a-len_b; i++)
        {
            bigint::b[len_b+i]=0;
        }
    }
}
 
void bigint::show()
{
    cout<<"Первое число = ";
    for(int i=max_len-1; i>=0; i--)
        cout<<a[i];
    cout<<", размером в "<<len_a<<" символов"<<endl;
 
    cout<<"Второе число = ";
    for(int i=max_len-1; i>=0; i--)
        cout<<b[i];
    cout<<", размером в "<<len_b<<" символов"<<endl;
    cout<<"Сумма = ";
    for(int i=max_len-1; i>=0; i--)
        cout<<c[i];
    cout<<endl<<"Разница = ";
    for(int i=max_len-1; i>=0; i--)
        cout<<f[i];
}
 
void bigint::sum()
{
    for(int i=0; i<max_len; i++)
    {
        back_a[i]=a[i];
    }
    int i, k;
    for(k=0; k<max_len; k++)
        c[k]=0;
    for(i=0; i<max_len; i++)
    {
        s=0;
        if(a[i]+b[i]>=10)
            s=1;
        c[i]=(a[i]+b[i])%10;
        a[i+1]+=s;
    }
}
 
void bigint::minus()
{
    int i, k;
    for(k=0; k<max_len; k++)
        f[k]=0;
    for(i=0; i<max_len; i++)
    {
        s=0;
        if(back_a[i]<b[i])
        {
            back_a[i]+=10;
            s=1;
        }
        f[i]=back_a[i]-b[i];
        back_a[i+1]-=s;
    }
 
}
 
int main()
{
    setlocale(0, "rus");
 
    int n=256;
    int *a = new int[n];
    int *b = new int[n];
    char *buff=new char[n];
 
    //int a[8]={4,7,3,8,5,7,3,8};
    //int b[5]={6,5,2,7,4};
    cout<<"Введите первое число: ";
    cin.sync();
    cin.getline(buff,n);
    int a_len=strlen(buff);
    for(int i=0;i<a_len;i++)
    {
        a[i]=buff[i]-48;
        buff[i]=0;
    }
 
    cout<<"Введите второе число: ";
    cin.sync();
    cin.getline(buff,n);
    int b_len=strlen(buff);
    for(int i=0;i<b_len;i++)
    {
        b[i]=buff[i]-48;
        buff[i]=0;
    }
 
    bigint str(a, b, a_len, b_len);
    str.sum();
    str.minus();
    str.show();
 
    return 0;
}

@UnsKneD · 21.03.2013, 22:53

C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
void bigint::sum() { for(int i=0; i<max_len; i++) { back_a[i]=a[i]; } int i, k; for(k=0; k<max_len; k++) c[k]=0; for(i=0; i<max_len; i++) { s=0; if(a[i]+b[i]>=10) s=1; c[i]=(a[i]+b[i])%10; //a[i+1]+=s; } }
Если закоментить последнюю строчку, то всё нормально.

@PlayaRC · 21.03.2013, 22:57 **[ТС]**

Если закоментить последнюю строчку, то всё нормально.

не, без нее не как, это же перенос единицы в следующий разряд при a[i]+b[i]>=10.

Без нее будет не правильно считать

@UnsKneD · 21.03.2013, 23:04

PlayaRC, да я понял уже, но ошибка где то там выходит.

@PlayaRC · 21.03.2013, 23:12 **[ТС]**

если ошибку в результате еще можно предположить, а вот почему оно даже выводиться с ошибками?

@UnsKneD · 21.03.2013, 23:21

C++

void bigint::sum() {
    int i, k; 
        for(int i=0; i<max_len; i++)
    {
        back_a[i]=a[i];
    }
    for(k=0; k<max_len; k++) 
        c[k]=0; 
    for(i=max_len-1; i>=0; i--) {
        s=0; 
        if(back_a[i]+b[i]>9) 
        { s=1; c[i+1]+=s; }
        c[i]=(back_a[i]+b[i])%10; 
    } 
}

Вот так будет правильно. Изначальный вариант функции.

Добавлено через 1 минуту
Выводится не с ошибками, выводится то что вы изменяете массив a[] в функции sum, воизбежании подобного нужно выгрузить из а во временный массив.

@PlayaRC · 21.03.2013, 23:25 **[ТС]**

Сообщение от UnsKneD

Добавлено через 1 минуту
Выводится не с ошибками, выводится то что вы изменяете массив a[] в функции sum, воизбежании подобного нужно выгрузить из а во временный массив.

блин, и как я сам не увидел) спасибо огромное, все работает)

@UnsKneD · 21.03.2013, 23:28

PlayaRC, пока ковырялся, заметил что если вводить первое меньше второго то результат разности не корректен.

@PlayaRC · 21.03.2013, 23:31 **[ТС]**

Сообщение от UnsKneD

PlayaRC, пока ковырялся, заметил что если вводить первое меньше второго то результат разности не корректен.

это знаю, я это еще не обработал, разность работает только для a>b

@UnsKneD · 21.03.2013, 23:32

с числами одинаковой длины, вообще ничего не выводится.

Добавлено через 1 минуту

Сообщение от PlayaRC

это знаю, я это еще не обработал, разность работает только для a>b

Всё ясно)

@UnsKneD алкокодер 157 / 153 / 41 Регистрация: 27.12.2012 Сообщений: 550
	21.03.2013, 23:32	19
	с числами одинаковой длины, вообще ничего не выводится. Добавлено через 1 минуту Сообщение от PlayaRC это знаю, я это еще не обработал, разность работает только для a>b Всё ясно) 1

@UnsKneD алкокодер 157 / 153 / 41 Регистрация: 27.12.2012 Сообщений: 550
	21.03.2013, 03:03	2
	Сложение столбиком 1

@vua72 419 / 418 / 167 Регистрация: 28.11.2010 Сообщений: 1,183
	21.03.2013, 15:05	4
	Вычитаете начиная с младшего разряда, если уменьшаемое меньше вычитаемого прибавляем 10 к уменьшаемому, производим вычитание, затем вычитаем единицу из вычитаемого следующего разряда и т.д.. Если заем из разряда старше вашего старшего - получили отрицательное число Добавлено через 8 минут И еще, вы фактически для хранения одного разряда используете 4 байта, хотя по логике вашей задачи - достаточно 1 байта (даже его половины). Почему не сделать массив unsigned char? 1

@PlayaRC 5 / 5 / 1 Регистрация: 10.03.2012 Сообщений: 121
	21.03.2013, 21:25 [ТС]	6
	еще вопрос: Почему например при вычитании\сложении числа, например: a[]={123456789844346} + b[]={53262354312} все считает нормально, а если ввожу a[]={999999999999999} + b[]={99999999999} 0

@PlayaRC 5 / 5 / 1 Регистрация: 10.03.2012 Сообщений: 121
	21.03.2013, 21:59 [ТС]	8
	Сообщение от UnsKneD PlayaRC, для int максимальное значение 2 147 483 647 Добавлено через 2 минуты если нужно складывать такие большие числа, используй long long int http://ru.wikipedia.org/wiki/Limits.h так я ведь вношу числа в массив! то есть в одной ячейке максимальное число = 9 0

@UnsKneD алкокодер 157 / 153 / 41 Регистрация: 27.12.2012 Сообщений: 550
	21.03.2013, 22:18	9
	PlayaRC, ой, точно же) а ты функции правильные размеры массивов передаёшь? Миниатюры 1

@PlayaRC 5 / 5 / 1 Регистрация: 10.03.2012 Сообщений: 121
	21.03.2013, 22:57 [ТС]	12
	Если закоментить последнюю строчку, то всё нормально. не, без нее не как, это же перенос единицы в следующий разряд при a[i]+b[i]>=10. Без нее будет не правильно считать 0

@UnsKneD алкокодер 157 / 153 / 41 Регистрация: 27.12.2012 Сообщений: 550
	21.03.2013, 23:04	13
	PlayaRC, да я понял уже, но ошибка где то там выходит. 1

@PlayaRC 5 / 5 / 1 Регистрация: 10.03.2012 Сообщений: 121
	21.03.2013, 23:12 [ТС]	14
	если ошибку в результате еще можно предположить, а вот почему оно даже выводиться с ошибками? 0

@PlayaRC 5 / 5 / 1 Регистрация: 10.03.2012 Сообщений: 121
	21.03.2013, 23:25 [ТС]	16
	Сообщение от UnsKneD Добавлено через 1 минуту Выводится не с ошибками, выводится то что вы изменяете массив a[] в функции sum, воизбежании подобного нужно выгрузить из а во временный массив. блин, и как я сам не увидел) спасибо огромное, все работает) 0

@UnsKneD алкокодер 157 / 153 / 41 Регистрация: 27.12.2012 Сообщений: 550
	21.03.2013, 23:28	17
	PlayaRC, пока ковырялся, заметил что если вводить первое меньше второго то результат разности не корректен. 1

@PlayaRC 5 / 5 / 1 Регистрация: 10.03.2012 Сообщений: 121
	21.03.2013, 23:31 [ТС]	18
	Сообщение от UnsKneD PlayaRC, пока ковырялся, заметил что если вводить первое меньше второго то результат разности не корректен. это знаю, я это еще не обработал, разность работает только для a>b 0