Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/181: Рейтинг темы: голосов - 181, средняя оценка - 4.76
1487 / 951 / 811
Регистрация: 30.04.2016
Сообщений: 3,315
1

Длинная арифметика. Сложение длинных чисел

09.08.2017, 19:52. Показов 37461. Ответов 10
Метки нет (Все метки)

Здравствуйте! Впервые за все время изучения C++ решил реализовать длинную арифметику, используя строки. К сожалению, программа прошла только 2 из 6 тестов, хотя код работает. Не ругайтесь особо, это моя первая программа и я обязательно переработаю ее в будущем. Сейчас, прошу оценить данный код и внести какие-либо замечания (если таковые имеются).

Условие:

Даны два "длинных" целых неотрицательных числа. Требуется найти результат их сложения. В качестве типа данных для хранения чисел используйте строки.

Входные данные:

На вход программе подаются два числа, каждое состоит из не более чем 250 цифр и находится в отдельной строке.

Выходные данные:

Выведите результат их сложения.

Примеры:

Входные данные:
10
1

Выходные данные:
11

Мое решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <string>
#include <algorithm>
#include <windows.h> //Шрифт консоли - Lucida Console
 
using namespace std;
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    string numOne, numTwo;
    string a, b, str, str_n, rem;
    int A[1000], B[1000], mem, tmp;
    cout << "Введите первое число: ";
    cin >> numOne;
    cout << "Введите второе число: ";
    cin >> numTwo;
    if (numOne.size() >= numTwo.size())
    {
        a = numOne;
        b = numTwo;
    }
    else
    {
        a = numTwo;
        b = numOne;
    }
    mem = 0;
    if (a.size() == b.size())
    {
        tmp = (a[0] - '0') + (b[0] - '0');
        if (tmp > 9)
        {
            a[0] = '0';
            b[0] = (tmp % 10) + '0';
        }
    }
    for (int i = 0; i < b.size(); i++)
    {
        A[i] = a[a.size() - (i + 1)] - '0' + b[b.size() - (i + 1)] - '0';
        A[i] += mem;
        if (A[i] >= 10)
            mem = A[i] / 10;
        else
            mem = 0;
        str += A[i] % 10 + '0';
    }
    reverse(str.begin(), str.end());
    if (mem == 0)
    {
        rem = a.substr(0, a.size() - b.size());
        rem += str;
        if (tmp > 9)
            cout << "1" + rem << endl;
        else
            cout << rem << endl;
    }
    else if (mem == 1)
    {
        rem = a.substr(0, a.size() - b.size());
        for (int i = 0; i < rem.size() - 1; i++)
        {
            B[i] = rem[rem.size() - (i + 1)] - '0' + mem;
            if (B[i] >= 10)
                mem = B[i] / 10;
            else
                mem = 0;
            str_n += B[i] % 10 + '0';
        }
        reverse(str_n.begin(), str_n.end());
        if (rem[0] != '9' && mem == 1)
        {
            rem[0]++;
            str_n = rem[0] + str_n;
        }
        else if (rem[0] == '9' && mem == 1)
        {
            str_n = "10" + str_n;
        }
        else if (mem != 1)
        {
            str_n = rem[0] + str_n;
        }
        rem = str_n + str;
        cout << rem << endl;
    }
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.08.2017, 19:52
Ответы с готовыми решениями:

Длинная арифметика. Сложение длинных чисел
Добрый день, Киберфорум! Изучаю длинную арифметику и нашел вот такой простейший пример сложения...

Длинная арифметика(вычитание длинных целых чисел)
Добрый вечер! Очень нужна помощь. Мне нужно написать программы для сложения больших целых...

Длинная арифметика. Умножение двух длинных чисел.
Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в...

Длинная арифметика: умножение двух длинных чисел
Всем привет! Снова к Вам за помощью. Алгоритм умножения двух длинных чисел: void...

10
190 / 164 / 82
Регистрация: 01.07.2016
Сообщений: 923
09.08.2017, 20:28 2
Не могу понять смысл вашего алгоритма. Наверное мой код будет понятнее
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
const int maxsize = 250;
 
void cinlong(int *mas) // Зеркально сохраняем цифры в массив
{
    string s;
    cin >> s;
    for(int i=0;i<maxsize;++i)
        mas[i] = 0;
 
    int len;
    len=s.length();
    for(int i=0;i<len;i++)
        mas[len - i] = int(s[i]) - 48;
}
 
void coutlong(int *mas) // выводим задом на перёд
{
    int i = maxsize;
    while(mas[i] == 0 && i > 1) i--;
 
    for(int j=i;j>=1;j--)
        cout << mas[j];
}
 
int main()
{
    int a[maxsize], b[maxsize];
 
    cinlong(a);
    cinlong(b);
 
//========================================================
    int c = 0;
    for(int i=1;i<maxsize;++i) // Сложение (с - остаток который может получиться при сложении поэтому делим его нацело)
        c = c + a[i] + b[i],
        a[i] = c % 10,
        c /= 10;
//========================================================
 
    coutlong(a);
}
0.50
1487 / 951 / 811
Регистрация: 30.04.2016
Сообщений: 3,315
09.08.2017, 20:31  [ТС] 3
no swear, здравствуйте! Спасибо за ваше замечание. Весь смысл - это сложение в столбик по существующим правилам. Правда, сложновато получилось, я торопился. Но, думаю, что переделаю вскоре и будет намного понятней. Еще раз спасибо за ваш ответ.
0
190 / 164 / 82
Регистрация: 01.07.2016
Сообщений: 923
09.08.2017, 20:40 4
Лучший ответ Сообщение было отмечено Fixer_84 как решение

Решение

Fixer_84, Здравствуйте. Нужно реализовать сложение в столбик максимально приближенно к тому виду которым мы пользуемся при подсчёте ручкой с бумажкой, т. е. я хочу сказать что и для вас это будет удобно и код будет красиво выглядеть и даже если вы, вдруг через 2 - 3 года, снова захотите посмотреть на этот код то вам будет легко всё восстановить(вспомнить) и думать("А что же я здесь написал...") вам не придётся.
Ну здесь я так и сделал, т. е. максимально понятно для себя я реализовал сложение в столбик. 9 + 9 = 18 - > 18 mod 10 в массив, 18 div 10 в остаток (в переменную с).
1
1466 / 1174 / 551
Регистрация: 08.01.2012
Сообщений: 4,524
09.08.2017, 20:46 5
Длинная арифметика(сложение)
1
633 / 476 / 278
Регистрация: 24.02.2017
Сообщений: 1,710
09.08.2017, 22:38 6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>
using namespace std;
 
int main(){
string a="10",b="101",sum="";
int c=0,d=0,t=0,n=0;
 
 if(a.size()>b.size())
 {
  t=a.size()-b.size();
  for(n=0;n<t;n++)
  sum+='0';
  sum+=b;
  b=sum;
  }
 if(a.size()<b.size())
  {
  t=b.size()-a.size();
  for(n=0;n<t;n++)
  sum+='0';
  sum+=a;
  a=sum;
  }
 if(a.size()==b.size())
    sum=a;
 
  for(n=a.size()-1;n>=0;n--)
   {
    t=d+(b[n]-'0')+(a[n]-'0');
    c=t%10;
    d= t/10;
    sum[n]=c+'0';
   }
   cout<<sum;
    system("pause>NULL");
    return 0;
}
1
1487 / 951 / 811
Регистрация: 30.04.2016
Сообщений: 3,315
09.08.2017, 23:11  [ТС] 7
no swear, спасибо за ваше замечание Я немного переделал код и мне удалось сдать задачу Он проще моего первого, но не проще вашего, хотя теперь можно разобраться без особого труда. Я обошелся только строками (без использования массивов).

Еще один рабочий код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int F(char sym)
{
    return sym - '0';
}
 
int main()
{
    string a, b, str, numOne, numTwo;
    int mem = 0, l, sum, end;
    cin >> numOne;
    cin >> numTwo;
    if (numOne.size() >= numTwo.size())
    {
        a = numOne;
        b = numTwo;
    }
    else
    {
        a = numTwo;
        b = numOne;
    }
    l = abs(a.size() - b.size());
    for (int i = 0; i < l; i++)
    {
        b = '0' + b;
    }
    for (int i = a.size() - 1; i >= 0; i--)
    {
        sum = F(a[i]) + F(b[i]) + mem;
        end = sum % 10;
        str += end + '0';
        if (i == 0)
            str += to_string(sum);
        mem = sum / 10;
    }
    reverse(str.begin(), str.end());
    cout << str.erase(0, 1) << endl;
    system("pause");
    return 0;
}
Добавлено через 7 минут
повар1, спасибо, что проявили внимание.

Добавлено через 15 минут
Вот урезанная версия того же самого:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
 
using namespace std;
 
int F(char sym)
{
    return sym - '0';
}
 
int main()
{
    string a, b, str, numOne, numTwo;
    int mem = 0, L, sum;
    cin >> numOne;
    cin >> numTwo;
    if (numOne.size() >= numTwo.size())
    {
        a = numOne;
        b = numTwo;
    }
    else
    {
        a = numTwo;
        b = numOne;
    }
    L = abs(a.size() - b.size());
    b.insert(0, L, '0');
    for (int i = a.size(); i--;)
    {
        sum = F(a[i]) + F(b[i]) + mem;
        str += sum % 10 + '0';
        if (i == 0)
            str += to_string(sum);
        mem = sum / 10;
    }
    reverse(str.begin(), str.end());
    cout << str.erase(0, 1) << endl;
    system("pause");
    return 0;
}
0
0 / 0 / 0
Регистрация: 18.10.2018
Сообщений: 53
03.11.2018, 12:27 8
Почему -48

Добавлено через 44 секунды
no swear почему -48 а не другой цифры

Добавлено через 2 минуты
-48?
0
498 / 477 / 77
Регистрация: 29.05.2015
Сообщений: 3,195
03.11.2018, 12:35 9
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Я обошелся только строками (без использования массивов).
И для этого пришлось переводить данные сперва из строки в цифру (что-бы произвести арифметические операции), а затем обратно из цифры в строку (что-бы сохранить результат). Не думаю, что это хорошее решение с точки зрения быстродействия.
0
44 / 20 / 14
Регистрация: 23.10.2018
Сообщений: 103
03.11.2018, 14:20 10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
string add(const string& n1, const string& n2) {
    if (n1.size() < n2.size()) {
        return add(n2, n1);
    }
 
    string result = "0" + n1;
    auto it1 = result.rbegin();
    auto it2 = n2.rbegin();
    int sum = 0;
    while (it2 != n2.rend()) {
        sum += (*it1 - '0') + (*it2 - '0');
        *it1 = (sum % 10) + '0';
        sum /= 10;
        it1++;
        it2++;
    }
    
    while (sum != 0) {
        sum += *it1 - '0';
        *it1 = (sum % 10) + '0';
        sum /= 10;
        it1++;
    }
    
    return result[0] == '0' ? result.substr(1) : result;
}
0
0 / 0 / 0
Регистрация: 15.08.2019
Сообщений: 5
12.11.2020, 22:27 11
Добрый день. Я понимаю, что эту задачу решали очень давно, просто я только сейчас столкнулся с этой темой и обучаюсь программированию. У меня есть пара вопросов и комментариев к вашему коду. Он очень компактный и хороший. В принципе, он даже работает, но немного не так, как хотелось бы. Я его скопировал, и у меня он уже вывел сначала мусор в массиве, потом нули и только потом ответ. Согласитесь, что это немного не то, чего пользователь ждал бы от программы. +у вас много обращений к несуществующим элементам массива. Например: в 15 строчке вы присваиваете в массив 0 элементов 2 элемент строки, выглядит нормально, но отсчёт строк начинается с 0 и по факту вы присвоили 3 элемент числа, а в двухзначном числе его просто не существует. Или ещё: 21 строчка. Вы вызываете 250 элемент массива, но его не существует. У массивов отсчёт идёт с нуля, поэтому у массива из 250 элементов, крайним будет 249. Получилось длинно, но эти вопросы меня мучают. Надеюсь, что вы прочитаете и ответите
P.s. и ещё у вас получилось магическое число в строке 15. Почему -48? Это понятно только вам, а при чтении другого программиста, он не сразу, а может и вообще не поймёт назначение данного числа

Адресовано no swear

Добавлено через 10 минут
no swear, надеюсь, вы увидите

Добавлено через 1 минуту
Damdador, если мы захотим вывести, предположим, int(string[0]), а string = 1234, в теории он должен вывести 1, но на самом деле программы выведет 49, т.к. 1 - в таблице аски кодов - это 49. Поэтому, чтобы мы получили 1, 2, 3 и тд, нам надо от значения в аски коде отнять 48.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.11.2020, 22:27

Длинная арифметика: реализовать операцию сложения длинных чисел
я пыталась сложить два больших числа но при запуске после ввода всё крошится #include...

Реализовать оператор сравнения в классе длинных чисел (длинная арифметика)
Здравствуйте, дорогие форумчане. Недавно назрел вопрос, как бы сделать сравнение чисел длинной...

Длинная арифметика. Сложение чисел
Есть у меня массив в каждой ячейке записано 1 или 0, т.е число в двоичном коде. Необходимо...

Сложение больших чисел (длинная арифметика)
Есть две строки string с числами, не получается сделать их суммирование с помощь, не могу понять...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru