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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

Длинная арифметика - C++

25.09.2012, 23:03. Просмотров 2879. Ответов 38
Метки нет (Все метки)

Нужно реализовать сложение и умножение больших чисел.
Есть идея, необходима помощь в реализации на C++.
Собственно, идеи такие...
Сумма: берём 2 массива, записываем их в строки, затем добавляем к меньшему числу нули так, чтоб их длина стала одинаковой. Затем, начиная с последнего элемента каждого массива, поэлементно суммируем элементы и остаток деления этой суммы на 10 записываем в начало новой строки. Если результат целочисленного деления суммы на 10 больше 0, то к следующему остатку предварительно прибавляем этот результат. И так до начала массива.
Произведение: берём последний элемент меньшего массива и умножаем поэлементно на больший массив, с делением на 10 (как в предыдущем пункте) и получаем новый массив. Далее с предпоследним элементом делаем тоже самое, затем в конце приписываем к нему '0' и производим сумму последних. Повторяем до тех пор, пока не достигнем начало меньшего массива.
Вот, что я пока написал. Понимаю, что бред, но может его можно исправить. Помогите, пожалуйста, очень срочно нужно
код
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
#include <iostream>
#include <vector>
#include <string>
 
int CtI(char x) // char в int
{
    return int(x)-48;
}
 
char ItC(int x) // int в char
{
    return char(x+48);
}
 
std::string adapt(std::string x, std::string y) // дописываем нули
{
    std::string::iterator iter = y.begin();
        y.insert(iter, x.size() - y.size(), '0');
    return y;
}
 
std::string sum_func(std::string x, std::string y)
{
    
    std::string::iterator x_iter = x.begin();
    std::string::iterator y_iter = y.begin();
    x.insert(x_iter, '0');
    y.insert(y_iter, '0');
    if (x.size() > y.size())
        y = adapt(x,y);
    if (x.size() < y.size())
        x = adapt(y,x);
    std::string sum;
    std::string::iterator sum_iter = sum.begin();
    int temp = 0;
    for (x_iter = --x.end(), y_iter = --y.end(); x_iter != x.begin(); --x_iter, --y_iter) // для того, чтоб цикл выполнился до
    {                                                                                     // конца мы заранее добавили по нолику
        if (temp != 0)
        {
            sum.insert(sum_iter, ItC((CtI(*x_iter)+CtI(*y_iter))%10+temp));
            temp = 0;
        }
        else
            sum.insert(sum_iter, ItC((CtI(*x_iter)+CtI(*y_iter))%10));
        temp = (CtI(*x_iter)+CtI(*y_iter))/10;
    }
    if (temp != 0)
        sum.insert(sum_iter, ItC(temp));
    else
        sum.erase(sum_iter);
    return sum;
}
 
int main()
{
    std::string x, y;
    std::cin >> x >> y;
    std::cout << sum_func(x,y);
    std::cin.get(); std::cin.get(); 
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.09.2012, 23:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Длинная арифметика (C++):

Длинная арифметика - C++
Ребята,объясните как решить задачу , напишите хоть часть кода. Пусть даны числа a , b . Найти a+b, если a и b не больше чем 10 в...

Длинная арифметика - C++
:senor: Здраствуйте, пишу модуль длинной математики. В принципе, работоспособность у него положительная. Но в силу моей неопытности меня...

Длинная арифметика - C++
Вот условие задачи: Во время исследований, посвященных появлению жизни на планете Олимпия, учеными было сделано несколько сенсационных...

Длинная арифметика - C++
Здравствуйте помогите пожалуйста с задачкой на с++ борландс :wall: 1. &quot;Вычислить точное значение (n!)! &quot; 2. &quot;Для заданной...

Длинная арифметика - C++
Всем доброго вечера. Нужна помощь в решении задачи. Составить программу для вычисления числа: 2^64-1. В результате сохранить все...

Длинная арифметика N+1 - C++
Помогите плиз. Вводится n. Вывести N+1. Ограничений нет. Я понимаю что надо ввести массив и читать каждый символ. Оставшиеся елементы...

38
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
26.09.2012, 23:15  [ТС] #16
Вы чем, кстати, компилируете?
я компилирую программой MS VS Express 2010
Вы забыли про конвертирование char в int и обратно.
что-то я не понял... в строке 18 у меня *str_iter имеет тип string; с помощью int(*str_iter) я преобразовываю его в int и вставляю в vector<int>.
При вводе чисел у меня выдаёт ошибку:
Debug assertion failed!
Program:...dio
path\my_project.exe
File: path\vc\include\vector
Line: 70
Expression: vector iterator not derefencable
//...
0
I.M.
565 / 548 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 23:24 #17
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
std::vector<int> StrToInt (std::string str)
{
    std::vector<int> vec(str.cbegin(), str.cend());
    
    for (auto it = vec.begin(); it!= vec.end(); ++it)
    {
        *it -= '0';
    }
    return vec;
}
 
std::string IntToStr (std::vector<int> vec)
{
    std::string str(vec.cbegin(), vec.cend());
 
    for (auto it = str.begin(); it!= str.end(); ++it)
    {
        *it += '0';
    }
    return str;
}
 
std::string Inverse (std::string str)
{
    std::string inv_str(str);
    std::reverse(inv_str.begin(), inv_str.end());
    return inv_str;
}
 
std::string Add (std::string str1, std::string str2)
{
    std::vector<int> vec1 = StrToInt (Inverse (str1));
    std::vector<int> vec2 = StrToInt (Inverse (str2));
 
    int max_size = std::max(vec1.size(), vec2.size());
    vec1.resize(max_size);
    vec2.resize(max_size);
 
    std::vector<int> vec_sum;
    vec_sum.reserve(max_size);
    
    int digit = 0;
    for (auto vec1_iter = vec1.cbegin(), vec2_iter = vec2.cbegin(); vec1_iter != vec1.end(); ++vec1_iter, ++vec2_iter)
    {
        vec_sum.push_back((*vec1_iter + *vec2_iter)%10 + digit);
        digit = (*vec1_iter + *vec2_iter)/10;
    }
    if (digit != 0) 
        vec_sum.push_back(1);
 
    return Inverse(IntToStr(vec_sum));
}
Слегка отредактировал программу.
Почитайте про то, что такое указатели и ссылки. В чем разница между передачей объекта в функцию напрямую и, например, по ссылке. Тогда увидите, что еще надо исправить в программе.
Еще про ключевое слово const почитайте. Когда и где его нужно использовать. Его тоже нужно добавить в код.
Насчет добавления нулей в меньший массив - честно говоря, не очень согласен. Ибо пустая трата памяти. Ну да ладно. Изучайте пока язык.
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
26.09.2012, 23:56  [ТС] #18
Спасибо, Вам, огромное!!! Единственное --строка 7:
code
C++
1
*it = *it - '0';
что делает эта операция?
В чем разница между передачей объекта в функцию напрямую и, например, по ссылке.
Ну, если мы передаём объект напрямую, то сам объект не меняется, а если передаём через ссылку, то происходит изменение аргумента, например:
code
C++
1
2
3
4
5
6
7
8
void inc1 (int& x){x +=1;}
void inc2 (int x) {x +=1;}
int main()
{
    int x = 0;  //x == 0
    inc1(x);    //x == 1
    inc2(x);    //x == 1
}

Тогда увидите, что еще надо исправить в программе.
Намекните, пожалуйста.
Еще про ключевое слово const почитайте. Когда и где его нужно использовать. Его тоже нужно добавить в код.
Кое-что читал. Я так понял, что его можно поставить вместо цифры 10. И эта константа будет отвечать, если я не ошибаюсь, за систему исчисления наших чисел.
Насчет добавления нулей в меньший массив - честно говоря, не очень согласен. Ибо пустая трата памяти.
Спасибо за исправления!
Результат, по-моему правильный получается. Теперь нужно с умножением сделать. Сейчас начну писать, но нужна будет Ваша помощь Закончу скорее всего уже завтра...
Ещё раз огромное спасибо!!!
0
I.M.
565 / 548 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
27.09.2012, 00:28 #19
Цитата Сообщение от vlad_light Посмотреть сообщение
что делает эта операция?
Берется очередной элемент массива вектор. Затем его значение меняется - оттуда вычитается ascii код нуля.

Цитата Сообщение от vlad_light Посмотреть сообщение
Ну, если мы передаём объект напрямую, то сам объект не меняется, а если передаём через ссылку, то происходит изменение аргумента
Если мы передаем объект напрямую, то происходит его полное копирование. А если по ссылке, то передается только ссылка (аналогично с указателем). А теперь представьте, что объект очень большой. Его гораздо выгоднее передавать по ссылке (естественно, если надо передавать именно копию, то передавайте объект по значению). Но если вы боитесь, что можете его случайно изменить, то тут на помощь приходит const.
итого получаем:
C++
1
void some_function(const std::vector<std::string>& some_vector){/*...*/}
Кстати, такая штука с копированиями справедлива и для возвращаемых значений. Поэтому можно делать так:
C++
1
void some_function(const std::vector<std::string>& input_vector, std::vector<int>& output_vector){/*...*/}
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
27.09.2012, 03:36  [ТС] #20
Всё, написал. Выкладываю полный код программы. Хотелось бы кол-во функций уменьшить, а то их много как-то... Да и критики ещё выслушать по поводу программы И по поводу класса: я вообще-то про них ничего не знаю, но слышал, что можно скрыть неиспользуемые функции, т.е. оставить в public только Input и Result, а все остальные кинуть в private. Я правильно говорю? Помогите, пожалуйста, обернуть это в класс, если это несложно, конечно
код
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
#include <string>
#include <vector>
const int BASE = 10;
 
void Input (std::string& str1, std::string& str2, char& oper)
{
    std::cout << "Please, input the 1st number: ";
    std::getline(std::cin, str1);
    std::cout << std::endl << "Please, input the 2nd number: ";
    std::getline(std::cin, str2);
    std::cout << std::endl << "Please, input the operation ('+','-' or '*'): ";
    std::cin.get(oper).get();
}
 
void Output (const std::string& str)
{
    for (std::string::const_iterator str_iter = str.begin(); str_iter != str.end(); ++str_iter)
            std::cout << *str_iter;
}
 
std::vector<int> StrToInt (const std::string& str)
{
    std::vector<int> vec(str.cbegin(), str.cend());
    
    for (auto iter = vec.begin(); iter!= vec.end(); ++iter)
    {
        *iter -= '0';
    }
    return vec;
}
 
std::string IntToStr (const std::vector<int>& vec)
{
    std::string str(vec.cbegin(), vec.cend());
 
    for (auto iter = str.begin(); iter!= str.end(); ++iter)
    {
        *iter += '0';
    }
    return str;
}
 
std::string Inverse (const std::string& str)
{
    std::string inv_str(str);
    std::reverse(inv_str.begin(), inv_str.end());
    return inv_str;
}
 
std::string Max (const std::string& str1, const std::string& str2)
{
    if (str1.size() > str2.size()) 
        return str1;
    if (str1.size() < str2.size()) 
        return str2;
 
    std::vector<int> vec1 = StrToInt (str1);
    std::vector<int> vec2 = StrToInt (str2);
 
    for (auto vec1_iter = vec1.cbegin(), vec2_iter = vec2.cbegin(); vec1_iter != vec1.end(); ++vec1_iter, ++vec2_iter)
    {
        if (*vec1_iter > *vec2_iter)
            return str1;
        if (*vec1_iter < *vec2_iter)
            return str2;
    }
 
    return str1;
}
 
std::string Add (const std::string& str1, const std::string& str2)
{
    std::vector<int> vec1 = StrToInt (Inverse (str1));
    std::vector<int> vec2 = StrToInt (Inverse (str2));
 
    int max_size = std::max(vec1.size(), vec2.size());
    vec1.resize(max_size);
    vec2.resize(max_size);
 
    std::vector<int> vec_sum;
    vec_sum.reserve(max_size);
    
    int digit = 0;
    for (auto vec1_iter = vec1.cbegin(), vec2_iter = vec2.cbegin(); vec1_iter != vec1.end(); ++vec1_iter, ++vec2_iter)
    {
        vec_sum.push_back((*vec1_iter + *vec2_iter + digit) % BASE);
        digit = (*vec1_iter + *vec2_iter) / BASE;
    }
    if (digit != 0) 
        vec_sum.push_back(digit);
 
    return Inverse(IntToStr(vec_sum));
}
 
std::string Multiple (const std::string& str1, const std::string& str2)
{
    std::vector<int> vec1 = StrToInt (Inverse (str1));
    std::vector<int> vec2 = StrToInt (Inverse (str2));
 
    int max_size = std::max(vec1.size(), vec2.size());
    vec1.resize(max_size);
    vec2.resize(max_size);
 
    std::string str_prod_sum;
    int n = 0;
    
    for (auto vec2_iter = vec2.begin(); vec2_iter != vec2.end(); ++vec2_iter)
    {
        std::vector<int> vec_prod(0);
        int digit = 0;
 
        for (int i = 0; i < n; ++i)
                vec_prod.push_back(0);
        ++n;
        
        for (auto vec1_iter = vec1.begin(); vec1_iter != vec1.end(); ++vec1_iter)
        {
            vec_prod.push_back((*vec1_iter * *vec2_iter + digit) % BASE);
            digit = (*vec1_iter * *vec2_iter + digit) / BASE;
        }
        if (digit != 0)
            vec_prod.push_back(digit);
 
        str_prod_sum = Add (Inverse(IntToStr(vec_prod)), str_prod_sum);
    }
 
    return str_prod_sum;
}
 
std::string Subtract (const std::string& str1, const std::string& str2)
{
    std::vector<int> vec1 = StrToInt (Inverse (str1));
    std::vector<int> vec2 = StrToInt (Inverse (str2));
 
    int max_size = std::max(vec1.size(), vec2.size());
    vec1.resize(max_size);
    vec2.resize(max_size);
    
    std::vector<int> vec_sub;
    vec_sub.reserve(max_size);
 
    int digit = 0;
    for (auto vec1_iter = vec1.cbegin(), vec2_iter = vec2.cbegin(); vec1_iter != vec1.end(); ++vec1_iter, ++vec2_iter)
    {
        if ((*vec1_iter - digit) >= *vec2_iter)
        {
            vec_sub.push_back (*vec1_iter - digit - *vec2_iter);
            digit = 0;
        }
        else
        {
            vec_sub.push_back (*vec1_iter + BASE - digit - *vec2_iter);
            digit = 1;
        }
    }
 
    while (vec_sub.back() == 0)
        vec_sub.pop_back();
 
    return Inverse(IntToStr(vec_sub));
}
 
void Result (const std::string& str1, const std::string& str2, const char& oper)
{
    std::cout << std::endl << "Result is: ";
    switch (oper)
    {
        case '+':
            Output (Add (str1, str2));
            break;
        case '*':
                Output (Multiple (str1, str2));
            break;
        case '-':
            if (str1 != Max(str1, str2))
            {
                std::cout << '-';
                Output (Subtract (str2, str1));
            }
            else
                Output (Subtract (str1, str2));
            break;
        default:
            std::cerr << "Error! Try again";
    }
}
 
int main()
{
    std::string str1, str2;
    char oper;
    Input (str1, str2, oper);
    Result (str1, str2, oper);
    std::cin.get();
    return 0;
}
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 09:35 #21
Зачем мучаться с десятичной системой? Возьмите основание, равное количеству чисел, представимых байтом, а тип элемента байт. Складывать можно так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TLongNamber TLongNamber:: operator + (TLongNamber &Right)
{
 TLongNamber Result;
 byte *p1, *p2, *p3;
 word buffer;
 word f;
 word o=UCHAR_MAX+1;
 for (p1=Litle, p2=Right->Litle, p3=Result->Litle, f=0; p1>=Big; --p1, --p2, --p3)
 {
  buffer=(word)(*p1)+(word)(*p2)+f;
  f=buffer/o;
  *p3=buffer%o;
 }
 return Result;
}
Добавлено через 1 час 3 минуты
Можно даже не делить, а сдвигать, а остаток выделять макросом.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
TLongNamber TLongNamber:: operator + (TLongNamber &Right)
{
 TLongNamber Result;
 byte *p1, *p2, *p3;
 word buffer;
 word f;
 for (p1=Litle, p2=Right->Litle, p3=Result->Litle, f=0; p1>=Big; --p1, --p2, --p3)
 {
  buffer=(word)(*p1)+(word)(*p2)+f;
  f=buffer>>sizeof(byte);
  *p3=LOWBYYE(buffer);
 }
 return Result;
}
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
27.09.2012, 10:18 #22
Цитата Сообщение от taras atavin Посмотреть сообщение
Зачем мучаться с десятичной системой? Возьмите основание, равное количеству чисел, представимых байтом, а тип элемента байт.
тут будет проблема перевести в удобный для пользователя формат(десятичный) и обратно
основание нужно брать равным степени десятки
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 10:25 #23
Для этих целей приняты переводы при вводе/выводе.
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
27.09.2012, 10:41 #24
Цитата Сообщение от taras atavin Посмотреть сообщение
Для этих целей приняты переводы при вводе/выводе.
я про это и говорил, при вводе выводе придется реализовывать длинную арифметику на десятичной базе
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 10:47 #25
С какого перепугу? Арифметика делается во внутреннем представлении и не зависит ни от второго основания, ни от направления перевода.
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
27.09.2012, 10:52 #26
Цитата Сообщение от taras atavin Посмотреть сообщение
С какого перепугу? Арифметика делается во внутреннем представлении и не зависит ни от второго основания, ни от направления перевода.
ну ладно, давай так - ты напишешь функцию перевода десятичного числа из строки в число с основанием 256, потом обратно
даже при обратном преобразовании нужно реализовывать сложение, напиши хотя бы алгоритм а?
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 11:01 #27
Откуда всплыла константа?
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
27.09.2012, 11:07 #28
Цитата Сообщение от taras atavin Посмотреть сообщение
Откуда всплыла константа?
Цитата Сообщение от taras atavin Посмотреть сообщение
Зачем мучаться с десятичной системой? Возьмите основание, равное количеству чисел, представимых байтом, а тип элемента байт.
byte --> 2^8 вроде бы
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
27.09.2012, 11:10 #29
Цитата Сообщение от vndtta Посмотреть сообщение
byte --> 2^8 вроде бы
Байт - единица адресной организации памяти, а не информации и в принципе может быть любым, хоть 9 тритов (19 683 представимых значений). То, что большинство современных машин имеет 8-ми битные байты сути не меняет и в исходнике не упомянуто.
0
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 1
27.09.2012, 11:17 #30
Цитата Сообщение от taras atavin Посмотреть сообщение
Байт - единица адресной организации памяти, а не информации и в принципе может быть любым, хоть 9 тритов (19 683 представимых значений). То, что большинство современных машин имеет 8-ми битные байты сути не меняет и в исходнике не упомянуто.
ладно, и ты считаешь, что тс сейчас сидит в каком-нибудь НИИ и бороздит интернет с какого-нить мэйнфрейма с 36-битной архитектрой? в общем сказки
алгоритм перевода плз в студию
запихни любой байт, какой удобно, на алгоритм не повлияет ведь?
0
27.09.2012, 11:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2012, 11:17
Привет! Вот еще темы с ответами:

Длинная арифметика. - C++
Даны два длинных числа a и b. Найти частное и остаток при делении числа a на b. Не могу реализовать деление отрицательных чисел. Помогите...

Длинная арифметика - C++
Поодскажите какую-нибудь библиотеку, где реализована работа со знаковыми целыми числами произвольной длины.

Длинная арифметика - C++
Помогите реализовать длинную арифметику #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; int main(){ int a; string...

Длинная арифметика - C++
Срочно нужны исходники (функции): 1. Перевод обычного числа в длинное (массив, строка , вектор кто с чем работает) 2. Нахождение суммы...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru