Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
shPavel25
 Аватар для shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
30.07.2012, 20:57     Длинное сложение #1
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в файл

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

C++
1
typedef vector<int> lnum;
Для повышения эффективности будем работать в системе по основанию миллиард, т.е. каждый элемент вектора
lnum содержит не одну, а сразу 9 цифр:

C++
1
const int base = 1000*1000*1000;
Цифры будут храниться в векторе в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы,
десятки, сотни, и т.д.).
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т.
е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией
лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль
корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий
единственный элемент — ноль.
Вывод
Самое простое — это вывод длинного числа.
Сначала мы просто выводим самый последний элемент вектора (или 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++
1
2
3
4
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++
1
2
3
4
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++
1
2
3
4
5
6
7
8
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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2012, 20:57     Длинное сложение
Посмотрите здесь:

Длинное число C++
самое длинное слово C++
C++ длинное слово
C++ Строки. В заданном тексте найти самое длинное слово и самое длинное предложение.
C++ Длинное произведение
C++ Длинное число

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 01:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru