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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
25.09.2012, 23:03     Длинная арифметика #1
Нужно реализовать сложение и умножение больших чисел.
Есть идея, необходима помощь в реализации на 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.09.2012, 23:03     Длинная арифметика
Посмотрите здесь:

Длинная арифметика C++
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
C++ Длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
25.09.2012, 23:20     Длинная арифметика #2
Цитата Сообщение от vlad_light Посмотреть сообщение
Нужно реализовать сложение и умножение больших чисел.
Есть идея, необходима помощь в реализации на C++.
Собственно, идеи такие...
Сумма: берём 2 массива, записываем их в строки, затем добавляем к меньшему числу нули так, чтоб их длина стала одинаковой. Затем, начиная с последнего элемента каждого массива, поэлементно суммируем элементы и остаток деления этой суммы на 10 записываем в начало новой строки. Если результат целочисленного деления суммы на 10 больше 0, то к следующему остатку предварительно прибавляем этот результат. И так до начала массива.
Произведение: берём последний элемент меньшего массива и умножаем поэлементно на больший массив, с делением на 10 (как в предыдущем пункте) и получаем новый массив. Далее с предпоследним элементом делаем тоже самое, затем в конце приписываем к нему '0' и производим сумму последних. Повторяем до тех пор, пока не достигнем начало меньшего массива.
Вот, что я пока написал. Понимаю, что бред, но может его можно исправить. Помогите, пожалуйста, очень срочно нужно:
Я конечно извеняюсь но зачем для сложения и умножения больших чисел использовать массивы?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
int main(){
setlocale(0,"");
double a, b;
cout << " Введите число a: " << endl;
cin >> a;
cout << " Введите число b: " << endl;
cin >> b;
cout << "a*b = " << (a*b) <<endl;
cout << "a+b = " << (a+b) <<endl;
system("pause");
return 0;
}
Добавлено через 2 минуты
А если вы имели ввиду умножение и сложение множества различных чисел, тогда да, массивы это то что надо)Уточните условие)
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
25.09.2012, 23:25  [ТС]     Длинная арифметика #3
нужно реализовать сложение и умножение целых чисел, которые не помещаются в long, без помощи посторонних библиотек. Например, программа должна уметь умножать 72643598263458726384578876 на 4092738458273409857238457 и выводить результат на экран.
Байт
 Аватар для Байт
13988 / 8819 / 1230
Регистрация: 24.12.2010
Сообщений: 15,975
25.09.2012, 23:28     Длинная арифметика #4
Elfenlide, А если числа содержат по сотне десятичных знаков? Или вы считаете, что таких не бывает в природе? Или ваш код действительно сумеет их сложить? Если ему это и удастся, то оче-е-нь приблизительно. А для исследований в теории чисел такая приблизительность не пройдет.

vlad_light, форум кишит обсуждением работы с большими числами и программами их реализующими. Попробуйте поискать. И Гугл тоже может помочь
А идеи ваши на первый взгляд вполне здравые. Удачи!
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
25.09.2012, 23:33     Длинная арифметика #5
Цитата Сообщение от vlad_light Посмотреть сообщение
нужно реализовать сложение и умножение целых чисел, которые не помещаются в long, без помощи посторонних библиотек. Например, программа должна уметь умножать 72643598263458726384578876 на 4092738458273409857238457 и выводить результат на экран.
а что если схитрить и посчитать это в double а потом вывести как целое число?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
25.09.2012, 23:41     Длинная арифметика #6
Цитата Сообщение от Elfenlide Посмотреть сообщение
а что если схитрить и посчитать это в double а потом вывести как целое число?
У double ограниченная точность, чуть меньше 16 десятичных знаков. Так что вы получите 2973112483602210###################################. Где # — неопределённая цифра.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
25.09.2012, 23:43     Длинная арифметика #7
vlad_light, гляньте на этот топик.
Теория чисел. ОТФ
Там в одном из вложений прячется библиотечка для работы с большими числами. Мб не совсем то что вам нужно, но возможно, что-то для себя выковыряете.
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
26.09.2012, 00:30  [ТС]     Длинная арифметика #8
Там в одном из вложений прячется библиотечка для работы с большими числами
Дело в том, что сами числа мне не особо нужны... Мне нужно научиться писать такие библиотеки.
форум кишит обсуждением работы с большими числами и программами их реализующими
В основном все говорят об использовании соответствующих библиотек. Поэтому решение в стиле:
C++
1
2
3
4
5
#include <Lib>
...
LibType a,b; 
std::cout << a+b;
...
меня не устраивает
И всё-же, старожилы, подскажите, тут сможет кто-то в моём коде разобраться и довести его до ума или тут таким не занимаются? Спасибо!
neske
1419 / 786 / 55
Регистрация: 26.03.2010
Сообщений: 2,694
26.09.2012, 00:34     Длинная арифметика #9
http://e-maxx.ru/algo/big_integer
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 01:30     Длинная арифметика #10
лучше использовать не строку, а обычный числовой массив. например вектор. тогда не придется каждый раз заниматься переводом чаров в инты.
для обратного прохода по контейнерам есть такие итераторы, как rbegin и rend.
счетчики должны "умирать" вместе с циклом, а не жить дальше (только если их значения не нужны в дальнейшем), поэтому и объявлять их стоит в самом цикле.
чтобы не писать длинные типы данных, можно использовать ключевое слово auto
если не собираетесь модифицировать данные с помощью итератора, т.е. доступ идет только на чтение, то делайте его константным. даже тип такой есть - const_iterator
используйте говорящие имена переменных. например, temp мне говорит, что там просто хранится промежуточное значение. но на деле вы ее используете и в условиях, и в вычислениях
это бы дело в класс обернуть
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.09.2012, 08:05     Длинная арифметика #11
И забейте на обратный проход. Это чревато проблемами, когда вам придётся добавлять цифр в число. Представляйте числа в little-endian: 12345 как [5, 4, 3, 2, 1] (младшие цифры по младшим адресам). Хорошо паковать по нескольку цифр в один int или что там у вас будет в элементе. В идеале — использовать все биты этого типа. (Последнее спорно.)
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.09.2012, 09:40     Длинная арифметика #12
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
В идеале — использовать все биты этого типа. (Последнее спорно.)
с умножением могут возникнуть проблемы. тогда либо умножать в дугой переменной, имеющей размерность (в байтах), как минимум, в два раза больше, либо использовать не более половины бит.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
26.09.2012, 12:32     Длинная арифметика #13
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
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
const int BaseSize = 4;
const int Base = 10000;
 
 
class BigLong
{
public :
    BigLong(){}
    BigLong(string s)
    {
        // 2^32 > 2*10^9
        do
        {
            int newsize = s.length()-BaseSize;
            newsize = (newsize>0)?newsize:0;
 
            string tmp=s.substr(newsize,BaseSize);
            s.resize(newsize);
 
            long val=0;
            for(int i=0;i<tmp.length();i++)
            {
                val*=10;
                val+=tmp[i]-'0';
            }
            Value.push_back(val);
        }while(s.length()>0);
    }
    ~BigLong()
    {
        Value.~vector();
    }
private:
    vector<long> Value;
 
    friend static BigLong operator+(BigLong &A, BigLong &B)
    {
        long buf=0;
        BigLong &min=(A.Value.size()>B.Value.size())?B:A;
        BigLong &max=(A.Value.size()>B.Value.size())?A:B;
        BigLong res;
        for(int i=0;i<min.Value.size();i++)
        {
            int val=min.Value[i]+max.Value[i]+buf;
            buf=val/Base;
            val%=Base;
            res.Value.push_back(val);
        }
        for(int i=min.Value.size();i<max.Value.size();i++)
        {
            int val=max.Value[i]+buf;
            buf=val/Base;
            val%=Base;
            res.Value.push_back(val);
        }
        if (buf) res.Value.push_back(buf);
        return res;
    }
 
    //ABCDE*fgh=
    //          ABCDE*h
    //      +  ABCDE*g
    //      + ABCDE*f
    //        _______
 
    void Add(BigLong &param, int level=0)
    {
        long buf=0;
        if (param.Value.size()+level < this->Value.size())
        {
        //mojet ponadobitsa, na vsyakiy slu4ay napisal, no pri obi4nih obstoyatelstavah suda ne popdaem
            for(int i=level;i<param.Value.size();i++)
            {
                this->Value[i]+=param.Value[i-level]+buf;
                buf=this->Value[i]/Base;
                this->Value[i]%=Base;
            }
            for(int i=param.Value.size();i<this->Value.size() && buf>0;i++)
            {
                this->Value[i]+=buf;
                buf=this->Value[i]/Base;
                this->Value[i]%=Base;
            }
            if (buf) this->Value.push_back(buf);
            return;
        }
 
        //esli lvl bolwe dobavlyaemogo 4isla, toje vryadli takoe slu4itsa, no na vsyakiy slu4ay dopisal
        for(int i=this->Value.size();i<level;i++)
            this->Value.push_back(0);
        //osnovnoe slojenie,  dva cikla
        for(int i=level;i<this->Value.size();i++)
        {
            this->Value[i]+=param.Value[i-level]+buf;
            buf=this->Value[i]/Base;
            this->Value[i]%=Base;
        }
        for(int i=this->Value.size();i<param.Value.size()+level;i++)
        {
            int val=param.Value[i-level]+buf;
            buf=val/Base;
            val%=Base;
            this->Value.push_back(val);
        }
        if (buf) this->Value.push_back(buf);
    }
    BigLong Mul(long mul)
    {
        BigLong res;
        long buf=0;
        for(int i=0;i<this->Value.size();i++)
        {
            int val=this->Value[i]*mul+buf;
            buf=val/Base;
            val%=Base;
            res.Value.push_back(val);
        }
        if (buf>0) res.Value.push_back(buf);
        return res;
    }
    friend static BigLong operator*(BigLong &A, BigLong &B)
    {
        BigLong &min=(A.Value.size()>B.Value.size())?B:A;
        BigLong &max=(A.Value.size()>B.Value.size())?A:B;
        BigLong res;
        for(int level=0;level<min.Value.size();level++)
        {
            res.Add(max.Mul(min.Value[level]),level);
        }
        return res;
    }
 
    friend ostream& operator<<(ostream &out, BigLong number)
    {
        for(int i=number.Value.size()-1;i>=0;i--)
        {
            out<<number.Value[i];
            if (i>0)
            {
                out.width(BaseSize);
                out.fill('0');
            }
        }
        return out;
    }
};
 
int main()
{
 
    cout<<(BigLong("999999999999999")+BigLong("1000000001"))<<endl;
    cout<<(BigLong("99999999")*BigLong("99999999"))<<endl;
 
    string s;
    cin>>s;
 
    return 0;
вот накатал, у меня скомпилилось,
самая длинная функция Add, но там первая половина не нужна

Добавлено через 21 минуту
Цитата Сообщение от vndtta Посмотреть сообщение
[CPP]
вот накатал, у меня скомпилилось,
самая длинная функция Add, но там первая половина не нужна
тут еще надо базу привязать к размеру long
если sizeof(long) = 4, то Base=10000 и BaseSize=4, чтобы при умножении не было переполнения, при перемножении максимальный размер числа - 8 разрядов умещается в 2^32 - это около 4*10^9, а если увеличить базу до пяти разрядов, то при перемножении будет 10 разрядов максимум
если sizeof(long) = 8, (2^64 - 1.8*10^19) -Base=10^9 BaseSize=9;
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
26.09.2012, 22:03  [ТС]     Длинная арифметика #14
вот накатал, у меня скомпилилось,
Спасибо, но я пока не могу осилить сразу весь код: я программировать начал буквально пару дней назад... А под фразой "Помогите, пожалуйста, очень срочно нужно" я имел ввиду не получить готовый код, а как можно быстрее написать его самому
I.M. прошёлся по Вашим комментариям:
лучше использовать не строку, а обычный числовой массив
я пока не знаю, как сделать непрерывный ввод в массив, поэтому пока использую строку.
счетчики должны "умирать" вместе с циклом
Вот в коде, который в этом сообщении, я ведь не могу строки 44, 45 занести в цикл, поскольку они всегда будут возвращать итератор на начало массива. Как тут поступить?
можно использовать ключевое слово auto
я пока такое слово не встречал... Как его изучу -- сразу начну использовать.
если не собираетесь модифицировать данные с помощью итератора, то делайте его константным
сделал
это бы дело в класс обернуть
я пока не знаю, что такое класс
Вот, что я написал, но оно не компилируется. Помогите найти ошибку, пожалуйста.
код
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
#include <iostream>
#include <vector>
#include <string>
 
void Output (std::string str)
{
    if (! str.empty())
        for (std::string::const_iterator str_iter = str.begin(); str_iter != str.end(); ++str_iter)
            std::cout << *str_iter;
    else
        std::cerr << "Error! The vector is empty!";
}
 
std::vector<int> StrToInt (std::string str)
{
    std::vector<int> vec;
    for (std::string::const_iterator str_iter = str.begin(); str_iter != str.end(); ++str_iter)
        vec.push_back(int(*str_iter));
    return vec;
}
 
std::string IntToStr (std::vector<int> vec)
{
    std::string str;
    for (std::vector<int>::const_iterator vec_iter = vec.begin(); vec_iter != vec.end(); ++vec_iter)
        str.push_back(char(*vec_iter));
    return str;
}
 
std::string Inverse (std::string str)
{
    std::string inv_str;
    std::string::const_iterator inv_str_iter = inv_str.begin();
    for (std::string::const_iterator str_iter = str.begin(); str_iter != str.end(); ++str_iter)
        inv_str.insert (inv_str_iter, *str_iter);
    return inv_str;
}
 
std::string Add (std::string str1, std::string str2)
{
    std::vector<int> vec1, vec2, vec_sum;
    vec1 = StrToInt (Inverse (str1));
    vec2 = StrToInt (Inverse (str2));
    std::vector<int>::const_iterator vec1_iter = vec1.begin();
    std::vector<int>::const_iterator vec2_iter = vec2.begin();
    int digit = 0;
    while (vec1_iter != vec1.end())
    {
        if (vec2_iter == vec2.end())
            vec2.push_back(0);
        if (digit != 0)
        {
            vec_sum.push_back ((*vec1_iter + *vec2_iter)%10 + digit);
            digit = 0;
        }
        else
            vec_sum.push_back ((*vec1_iter + *vec2_iter)%10);
        digit = (*vec1_iter + *vec2_iter)/10;
        ++vec1_iter;
        ++vec2_iter;
    }
    if (digit != 0) 
        vec_sum.push_back(1);
    return Inverse(IntToStr(vec_sum));
}
 
int main()
{
    std::string str1, str2;
    std::getline (std::cin, str1);
    std::getline (std::cin, str2);
    Output (Add (str1, str2));
    std::cin.get();
    return 0;
}
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 22:54     Длинная арифметика #15
Цитата Сообщение от vlad_light Посмотреть сообщение
Вот, что я написал, но оно не компилируется.
Все компилируется. Если он выдает неверный результат, то это уже другой разговор. Вы забыли про конвертирование char в int и обратно.
C++
1
2
3
vec.push_back(int(*str_iter - '0'));//строка 18
//...
str.push_back(char(*vec_iter + '0'));//строка 26
И все будет работать
Вы чем, кстати, компилируете?
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
//...
I.M.
 Аватар для I.M.
564 / 547 / 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 почитайте. Когда и где его нужно использовать. Его тоже нужно добавить в код.
Насчет добавления нулей в меньший массив - честно говоря, не очень согласен. Ибо пустая трата памяти. Ну да ладно. Изучайте пока язык.
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. И эта константа будет отвечать, если я не ошибаюсь, за систему исчисления наших чисел.
Насчет добавления нулей в меньший массив - честно говоря, не очень согласен. Ибо пустая трата памяти.
Спасибо за исправления!
Результат, по-моему правильный получается. Теперь нужно с умножением сделать. Сейчас начну писать, но нужна будет Ваша помощь Закончу скорее всего уже завтра...
Ещё раз огромное спасибо!!!
I.M.
 Аватар для I.M.
564 / 547 / 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){/*...*/}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2012, 03:36     Длинная арифметика
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
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;
}
Yandex
Объявления
27.09.2012, 03:36     Длинная арифметика
Ответ Создать тему
Опции темы

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