Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.51/198: Рейтинг темы: голосов - 198, средняя оценка - 4.51
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31

Длинная арифметика. Умножение двух длинных чисел.

29.04.2011, 13:44. Показов 39624. Ответов 55
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора.
Либо простой и понятно описанный алгоритм, по которому можно такое сделать.
Заранее спасибо.
P.S. в гугл отправлять не надо-разбираться со сложными алгоритмами вроде БПФ у меня нет ни времени, ни желания.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
29.04.2011, 13:44
Ответы с готовыми решениями:

Длинная арифметика: умножение двух длинных чисел
Всем привет! Снова к Вам за помощью. Алгоритм умножения двух длинных чисел: void...

Длинная арифметика. Сложение длинных чисел
Здравствуйте! Впервые за все время изучения C++ решил реализовать длинную арифметику, используя строки. К сожалению, программа прошла...

Длинная арифметика. Сложение длинных чисел
Добрый день, Киберфорум! Изучаю длинную арифметику и нашел вот такой простейший пример сложения длинных чисел "в столбик". Не...

55
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 07:43
Студворк — интернет-сервис помощи студентам
Спрошу в этой темке...
Как быстро работает swap?
Не хочу писать
Code
1
 if (a>b) {...} else {почти то же самое}
Хочу написать просто
if (a>b) swap(a,b);
Но боюсь, что времени много пожрет.
0
377 / 228 / 79
Регистрация: 24.11.2009
Сообщений: 695
01.05.2011, 10:50
Цитата Сообщение от diagon Посмотреть сообщение
Спрошу в этой темке...
Как быстро работает swap?
быстро. Оптимизация по скорости без необходимости - зло.
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 15:38
Вычисляет факториал с помощью умножения длинного на длинное, с того же сайта взято. Писал для себя, чтобы в векторах и длинной арифметике попрактиковаться, поэтому извиняюсь за быдло-код.
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
#include <iostream>
#include <vector>
#include <algorithm>
void readlong(std::vector<int> &a); //чтение
void writelong(std::vector<int> a){  //вывод
    for (size_t i=0; i< a.size();i++) std::cout << a[i];}
short compare(std::vector<int> a,std::vector<int> b); //сравнение
void nol(std::vector<int> &a,std::vector<int> &b); //добавление нулей в начало(для суммы)
std::vector<int> sum(std::vector<int> a, std::vector <int> b); //сумма
std::vector<int> smult(std::vector<int> a,int b); //умножение длинного на короткое
void ten(std::vector<int> &a,int b);//добавление b нулей в конец
long long vectoint(std::vector<int> a);//перевод вектора в int
std::vector<int> mult (std::vector<int> a, std::vector<int> b); //умножение длинного на длинное
std::vector<int> factorial(std::vector<int> b); //факториал
int main(){
 
    std::vector<int> a,b,c,rez;
    readlong(a);
    writelong(factorial(a));
    return 0;
}
void readlong(std::vector<int> &a){
    char c;
    for(;;){
        std::cin.get(c);
        if ((c==' ')||(c=='\n'))break;
        a.push_back(c-48);
    }
}
short compare(std::vector<int> a,std::vector<int> b){
    if (a.size()>b.size()) return 1;
    if (a.size()<b.size()) return 2;
    for (size_t i=0; i<a.size();i++){
    if (a[i]>b[i]) return 1;
    if (a[i]<b[i]) return 2;
    }
    return 0;
 
}
void nol(std::vector<int> &a,std::vector<int> &b){
    if (a.size()==b.size()) return;
    if (a.size()>b.size()) std::swap(a,b);
    for (size_t i=0; i< a.size()-b.size(); i++){
        a.insert(a.begin(),0);
    }
}
std::vector<int> sum(std::vector<int> a, std::vector<int> b){
    std::vector<int>c;
    short p=0;
    nol(a,b);
    c.assign(a.size(),0);
    for (short i = a.size()-1; i >= 0; i--) {
        c[i]=a[i]+b[i]+p;
        p=0;
        if (c[i]>9) {c[i]-=10; p=1;}
    }
    if (p) c.insert(c.begin(),1);
    return c;
}
std::vector<int> smult(std::vector<int> a,int b){
    std::vector<int> c;
    if (!b||!a[0]) {c.push_back(0); return c; }
    for (size_t i = 0; i <a.size(); i++) {
        if (i==c.size()) c.push_back(0);
        c[i]=a[i]*b;
    }
    for (size_t i=c.size()-1; i > 0; i--) {
        if (c[i]>9) {
            c[i-1]+=c[i]/10;
            c[i]%=10;
            }
        }
    if (c[0]<10) return c;
    short p=c[0];
    c[0]%=10;
    for(;;){
        if (!(p/10)) break;
        c.insert(c.begin(),p/10);
        p/=10;
    }
    return c;
}
void ten(std::vector<int>& a,int b){
    for (; b; b--)
        a.push_back(0);
}
std::vector<int> factorial(std::vector<int>(b)){
    std::vector<int> a,o,c;
    a.push_back(1);
    o.push_back(1);
    c.push_back(1);
    for(long int i=0;i<vectoint(b)-1;i++){
        c=sum(c,o);
        a=mult(c,a);
    }
    return a;
}
long long vectoint(std::vector<int> a){
    long long c=0,q=1;
    for (short i = a.size()-1; i >=0; i--) {
        c+=a[i]*q;
        q*=10;
    }
    return c;
}
std::vector<int> mult (std::vector<int> a, std::vector<int> b)
{
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    std::vector<int> c(a.size()+b.size());
    for (int i = 0; i < a.size(); ++i)
        for (int j = 0, carry = 0; j < b.size() || carry; ++j)
        {
            long long cur = c[i+j] + a[i] * (j < b.size() ? b[j] : 0) + carry;
            c[i+j] = cur % 10;
            carry = cur / 10;
        }
 
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
        reverse(c.begin(),c.end());
        return c;
}
1
0 / 1 / 0
Регистрация: 29.04.2011
Сообщений: 31
01.05.2011, 15:55  [ТС]
Цитата Сообщение от diagon Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::vector<int> mult (std::vector<int> a, std::vector<int> b)
{
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        std::vector<int> c(a.size()+b.size());
        for (int i = 0; i < a.size(); ++i)
                for (int j = 0, carry = 0; j < b.size() || carry; ++j)
                {
                        long long cur = c[i+j] + a[i] * (j < b.size() ? b[j] : 0) + carry;
                        c[i+j] = cur % 10;
                        carry = cur / 10;
                }
 
        while (c.size() > 1 && c.back() == 0)
                c.pop_back();
                reverse(c.begin(),c.end());
                return c;
}
Так они там в перевернутом виде хранились... Мда. А я-то думал...
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
01.05.2011, 15:57
diagon, я уже выкладывал в эту тему программу вычисления факториала)
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
01.05.2011, 16:01
У вас это не в 130 строк сделано
Да и у меня он вычисляется как обычный, и есть полезная для ТСа готовая функция умножения.
Вообще хотел рекурсивное вычисление факториала сделать, но как это сделать с помощью векторов не додумался.
1
01.05.2011, 16:09

Не по теме:

Ну просто у вас сделано не совсем рационально, много лишних действий.
Да и умножение двух длинных я тоже выкладывал)

1
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
02.05.2011, 10:27
vpupkin, у меня, кстати, тоже в перевёрнутом виде... Совсем забыл предупредить...
0
1552 / 918 / 193
Регистрация: 26.03.2010
Сообщений: 3,105
02.05.2011, 11:27
silent_1991, дак а без перевернутого вида там хрен и реализуешь) разряды добавлять, сдвигать.. надо это))
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
02.05.2011, 11:37
neske, но предупредить всё же следовало, а то сходу ведь и не поймёшь)))
0
15 / 15 / 1
Регистрация: 17.10.2012
Сообщений: 98
Записей в блоге: 1
11.04.2013, 00:00
Цитата Сообщение от silent_1991 Посмотреть сообщение
мать моя... Вы что же, не в состоянии написать умножение столбиком? Алгоритм я, например, помню с начальной школы, а если бы и не помнил - загуглил бы, на первой странице точно был бы алгоритм. А дальше дело техники...
Так Почему бы тебе не написать ему пример от 0 до конца ?*
а? или ты слова на ветер бросаеш ?
Вот Тут читал Факторниал Нужен я вот старый код для факториал выщитует любой факториал но будет оч долго щитать после 1000 но впринципе мне хватало...
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
char *My_Factorial(int f)
{
    char *name;
    char C[4],A[10000],B[10000],D[10000];
    char E[]="123456789";
    int i,j,k,l,m,n,o,p,q,r,s,t;
    for(i=0;i<9999;i++)
    {
        A[i]='0';
        B[i]='0';
        D[i]='0';
    }
    A[9998]='1';
    A[9999]='\0';
    B[9999]='\0';
    D[9999]='\0';
    //f -> scanf
    for(i=1;i<=f;i++)
    {
        itoa(i,C,10);
        k=strlen(C);
        for(j=k;j>0;j--)
        {
            n=(C[j-1]-48);
            s=(abs(j-k));
            for(l=9998;l>=3;l--)
            {
                m=A[l]-48;
                o=B[l-s]-48;
                p=n*m+o;
                r=p%10;
                q=(int)(p-r)/10;
                if(p<10)
                {
                    r=p;
                    q=0;
                }
                B[l-s]=r+48;
                B[l-s-1]=q+48;
            }
            for(l=9999;l>0;l--)
            {
                m=B[l-1]-48;
                o=D[l-1]-48;
                p=m+o;
                r=p%10;
                q=(int)(p-r)/10;
                if(p<10){r=p;q=0;}
                D[l-1]=r+48;
                D[l-2]+=q;
            }
            for(l=0;l<9999;l++)B[l]='0';
        }
        strcpy(A,D);
        for(l=0;l<9999;l++)D[l]='0';
    }
    int xz=strlen(A);
    name=new char[xz];
    name[0]=NULL;
    name=strpbrk(A,E);
    name[0]=NULL;
    return name;
}
удачи
0
245 / 246 / 38
Регистрация: 08.04.2013
Сообщений: 927
11.04.2013, 00:07
Может я, конечно, не сильно в тему буду. Но как написать длинную арифметику для любых действительных чисел с экономией места, то есть в один int помещать не 1 цифру, а 8(кажется 8 или 7 должно влезть)? Как это все правильно и оптимально оформить?
0
11.04.2013, 08:25

Не по теме:

Цитата Сообщение от Програмер_80лвл Посмотреть сообщение
Так Почему бы тебе не написать ему пример от 0 до конца ?*
А мне оно надо?

0
11.04.2013, 09:26

Не по теме:

Програмер_80лвл, Вы обладаете удивительной способностью отвечать на темы(это не единственная тема), в которые никто не заглядывал уже несколько лет.

0
11.04.2013, 09:48

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
Програмер_80лвл, Вы обладаете удивительной способностью отвечать на темы(это не единственная тема), в которые никто не заглядывал уже несколько лет.
Программер прокачался уже до 81лвл, и ему надо 100 сообщений для смены ника.

0
807 / 534 / 158
Регистрация: 27.01.2015
Сообщений: 3,017
Записей в блоге: 1
27.04.2016, 21:14
На всякий случай (умножение длинного числа на длинное), вдруг кому-либо понадобится...
Проверки на корректность ввода нет, работает лишь с натуральными числами.
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
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
 
#include <string>
using std::string;
 
#include <algorithm>
 
#include <windows.h>
 
string& multOneDigit(const string& value1, const char& value2)
{
    static string result;
    result = "";
    unsigned digit(value2 - '0');
    switch (digit)
    {
    case 0:
        return result = "0";
        break;
    case 1:
        return result = value1;
        break;
    }
    unsigned temp(0);
    for (unsigned i(0); value1[i]; ++i)
    {
        temp += (value1[i] - '0') * digit;
        result.push_back(temp % 10 + '0');
        temp /= 10;
    }
    if (temp)
        result.push_back(temp % 10 + '0');
    return result;
}
 
string& multDigitWithZeros(const string& value1, const string& value2)
{
    static string result;
    result = multOneDigit(value1, value2[0]);
    if (value2.length() == 1)
        return result;
    return result = string(value2.begin() + 1, value2.end()) + result;
}
 
string& toAdd(string& value1, string& value2)
{
    static string result;
    result = "";
    unsigned i(value1.length()), j(value2.length());
    if (i < j)
        for (; i < j; ++i)
            value1.push_back('0');
    else if (j < i)
        for (; j < i; ++j)
            value2.push_back('0');
    unsigned temp(0);
    for (i = 0; i < j; ++i)
    {
        temp += value1[i] + value2[i] - 2 * '0';
        result.push_back(temp % 10 + '0');
        temp /= 10;
    }
    if (temp)
        result.push_back(temp % 10 + '0');
    return result;
}
 
const string& toMult(string& value1, string& value2)
{
    static string result;
    result = "0";
    if (value1.length() < value2.length())
        swap(value1, value2);
    reverse(value1.begin(), value1.end()),
        reverse(value2.begin(), value2.end());
    for (unsigned i(0), count(value2.length()); i < count; ++i)
    {
        string temp(&value2[i], 1);
        for (unsigned j(0); j < i; ++j)
            temp.push_back('0');
        result = toAdd(multDigitWithZeros(value1, temp), result);
    }
    reverse(result.begin(), result.end());
    return result;
}
 
int main(void)
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    string value1("470827"), value2("60013");
    cout << toMult(value1, value2) << endl;
    system("pause");
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
27.04.2016, 21:14

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

Длинная арифметика: реализовать операцию сложения длинных чисел
я пыталась сложить два больших числа но при запуске после ввода всё крошится #include &lt;bits/stdc++.h&gt; using...

Реализовать оператор сравнения в классе длинных чисел (длинная арифметика)
Здравствуйте, дорогие форумчане. Недавно назрел вопрос, как бы сделать сравнение чисел длинной арифметики в дальнейшем коде? Сравнение...

Длинная арифметика: сложение и умножение чисел
Нужно реализовать сложение и умножение больших чисел. Есть идея, необходима помощь в реализации на C++. Собственно, идеи такие... ...

Сложение двух чисел (длинная арифметика)
Нужно реализовать длинную арифметику (сложение двух больших чисел), но на экран выводятся не понятные символы. Я подозреваю, что a =...


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

Или воспользуйтесь поиском по форуму:
56
Ответ Создать тему
Новые блоги и статьи
сукцессия 15 неявная схема
anaschu 29.06.2026
Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений
сукцессия 14. Обновленная схема модели
anaschu 28.06.2026
ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного
anaschu 28.06.2026
## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .
сукцессия 12. краткий список проверок модели перед запуском.
anaschu 27.06.2026
Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .
Сукцессия 11. Проверка орудий перед войной: разработка через тестирование
anaschu 27.06.2026
Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .
10 сукцессия. Питон код войны грибов и растений
anaschu 27.06.2026
import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .
сукцессия 9. Математика подлости: как растения предали грибных друзей
anaschu 27.06.2026
Статья 2. Глобальная фосфорная война: эволюционно-экономические механизмы распределения биомов Земли Введение: Экологический рынок как игра с нулевой суммой Традиционная экология долгое время. . .
сукцессия 8. Как я спорил с ИИ, которые - агенты растений и ненавистники грибов!
anaschu 27.06.2026
Статья 1. Хроники грибного восстания: как Сократов диалог разрушил академические догмы ИИ Введение: Синдром «цифрового учебника» Современные большие языковые модели (LLM) обладают колоссальным. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru