Длинное сложение - C++

@shPavel25 · Регистрация: 29.03.2011

Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в файл

Длинное сложение
Вход:
В первой строке записано натуральное число A. Во второй строке записано натуральное число B. Числа записаны без ведущих нулей. (A, B < 10100)
Выход:
В единственной строке выведите результат без ведущих нулей.
***решение
Хранить длинные числа будем в виде вектора чисел int, где каждый элемент — это одна цифра числа.

C++

1	typedef vector<int> lnum;

Для повышения эффективности будем работать в системе по основанию миллиард, т.е. каждый элемент вектора
lnum содержит не одну, а сразу 9 цифр:

C++

1	const int base = 100010001000;

Цифры будут храниться в векторе в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы,
десятки, сотни, и т.д.).
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.
е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией
лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль
корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий
единственный элемент — ноль.
Вывод
Самое простое — это вывод длинного числа.
Сначала мы просто выводим самый последний элемент вектора (или 0, если вектор пустой), а затем выводим
все оставшиеся элементы вектора, дополняя их нулями до 9 символов:

C++

1
2
3

printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
printf ("%09d", a[i]);

(здесь небольшой тонкий момент: нужно не забыть записать (int), поскольку в противном случае число
будут беззнаковым, и если a.size()<=1, то при вычитании произойдёт переполнение)
Чтение
Считываем строку в string, и затем преобразовываем её в вектор:

C++

for (int i=(int)s.length(); i>0; i-=9)
if (i < 9)
a.push_back (atoi (s.substr (0, i).c_str()));
elsea.push_back (atoi (s.substr (i-9, 9).c_str()));

Если использовать вместо string массив char'ов, то код получится ещё компактнее:

C++

for (int i=(int)strlen(s); i>0; i-=9) {
s[i] = 0;
a.push_back (atoi (i>=9 ? s+i-9 : s));
}

Сложение
Прибавляет к числу a число b и сохраняет результат в a:

C++

int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) {
if (i == a.size())
a.push_back (0);
a[i] += carry + (i < b.size() ? b[i] : 0);
carry = a[i] >= base;
if (carry) a[i] -= base;
}

Опции темы

С++ для начинающих

Длинное сложение - C++