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

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

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

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

25.09.2012, 23:03. Просмотров 2800. Ответов 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. Ограничений нет. Я понимаю что надо ввести массив и читать каждый символ. Оставшиеся елементы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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 минуты
А если вы имели ввиду умножение и сложение множества различных чисел, тогда да, массивы это то что надо)Уточните условие)
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
25.09.2012, 23:25  [ТС] #3
нужно реализовать сложение и умножение целых чисел, которые не помещаются в long, без помощи посторонних библиотек. Например, программа должна уметь умножать 72643598263458726384578876 на 4092738458273409857238457 и выводить результат на экран.
0
Байт
Эксперт C
16062 / 10331 / 1540
Регистрация: 24.12.2010
Сообщений: 19,472
25.09.2012, 23:28 #4
Elfenlide, А если числа содержат по сотне десятичных знаков? Или вы считаете, что таких не бывает в природе? Или ваш код действительно сумеет их сложить? Если ему это и удастся, то оче-е-нь приблизительно. А для исследований в теории чисел такая приблизительность не пройдет.

vlad_light, форум кишит обсуждением работы с большими числами и программами их реализующими. Попробуйте поискать. И Гугл тоже может помочь
А идеи ваши на первый взгляд вполне здравые. Удачи!
1
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
25.09.2012, 23:33 #5
Цитата Сообщение от vlad_light Посмотреть сообщение
нужно реализовать сложение и умножение целых чисел, которые не помещаются в long, без помощи посторонних библиотек. Например, программа должна уметь умножать 72643598263458726384578876 на 4092738458273409857238457 и выводить результат на экран.
а что если схитрить и посчитать это в double а потом вывести как целое число?
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
25.09.2012, 23:41 #6
Цитата Сообщение от Elfenlide Посмотреть сообщение
а что если схитрить и посчитать это в double а потом вывести как целое число?
У double ограниченная точность, чуть меньше 16 десятичных знаков. Так что вы получите 2973112483602210###################################. Где # — неопределённая цифра.
0
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
25.09.2012, 23:43 #7
vlad_light, гляньте на этот топик.
Теория чисел. ОТФ
Там в одном из вложений прячется библиотечка для работы с большими числами. Мб не совсем то что вам нужно, но возможно, что-то для себя выковыряете.
2
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;
...
меня не устраивает
И всё-же, старожилы, подскажите, тут сможет кто-то в моём коде разобраться и довести его до ума или тут таким не занимаются? Спасибо!
0
neske
1495 / 862 / 82
Регистрация: 26.03.2010
Сообщений: 2,951
26.09.2012, 00:34 #9
http://e-maxx.ru/algo/big_integer
2
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
26.09.2012, 01:30 #10
лучше использовать не строку, а обычный числовой массив. например вектор. тогда не придется каждый раз заниматься переводом чаров в инты.
для обратного прохода по контейнерам есть такие итераторы, как rbegin и rend.
счетчики должны "умирать" вместе с циклом, а не жить дальше (только если их значения не нужны в дальнейшем), поэтому и объявлять их стоит в самом цикле.
чтобы не писать длинные типы данных, можно использовать ключевое слово auto
если не собираетесь модифицировать данные с помощью итератора, т.е. доступ идет только на чтение, то делайте его константным. даже тип такой есть - const_iterator
используйте говорящие имена переменных. например, temp мне говорит, что там просто хранится промежуточное значение. но на деле вы ее используете и в условиях, и в вычислениях
это бы дело в класс обернуть
1
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
26.09.2012, 08:05 #11
И забейте на обратный проход. Это чревато проблемами, когда вам придётся добавлять цифр в число. Представляйте числа в little-endian: 12345 как [5, 4, 3, 2, 1] (младшие цифры по младшим адресам). Хорошо паковать по нескольку цифр в один int или что там у вас будет в элементе. В идеале — использовать все биты этого типа. (Последнее спорно.)
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
26.09.2012, 09:40 #12
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
В идеале — использовать все биты этого типа. (Последнее спорно.)
с умножением могут возникнуть проблемы. тогда либо умножать в дугой переменной, имеющей размерность (в байтах), как минимум, в два раза больше, либо использовать не более половины бит.
1
vndtta
90 / 67 / 13
Регистрация: 17.10.2011
Сообщений: 235
Завершенные тесты: 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;
1
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;
}
0
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
И все будет работать
Вы чем, кстати, компилируете?
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 22:54
Привет! Вот еще темы с ответами:

Длинная арифметика. - 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. Нахождение суммы...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.09.2012, 22:54
Ответ Создать тему
Опции темы

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