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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 57, средняя оценка - 4.63
Runa
131 / 83 / 3
Регистрация: 28.08.2009
Сообщений: 363
#1

Деление больших чисел - C++

04.11.2010, 14:16. Просмотров 7562. Ответов 9
Метки нет (Все метки)

Здравствуйте, уважаемые форумчане.
Необходимо разделить большое чило на большое число.
Эти числа хранятся в массиве ( каждый элемент - одна цифра числа).
Подскажите пожалуйста алгоритм деления, код не обязателен, просто хотя бы самую суть.
Делить необходимо по простому, не используя различные методы высшей математики.
Буду очень благодарна!
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.11.2010, 14:16     Деление больших чисел
Посмотрите здесь:

Деление больших чисел - C++
Доброго времени суток. Спасите пожалуйста, как здесь быть:) Даны два числа. Ваша задача найти частное и остаток от деления. Input...

Ускорить деление больших чисел - C++
Всё бы ничего, да уж очень медленно. :( По форуму смотрел, в Инете искал. Ничего аппетитного нетути. Деление длинного на длинное. ...

Деление больших чисел (нужно ускорить) - C++
Ребятки, помогите ускорить. Уж очень медленно. Класс совсем простой(вектор со знаком): static const unsigned long long BASE =...

Класс больших чисел. Деление по Кнуту. - C++
Кнут т2 стр. 300 алгоритм D. Кто реализовал для b=2^32 или 2^16 - поделитесь, плз, если не жалко ! (А то у меня много неясных моментов....

Деление шеснадцатиричных чисел - C++
#include <stdio.h> int main () { char y= 0X2e; printf ("y= %x\n", y); printf ("= %x\n", y/0Xf); printf ("= %x\n", y%0Xf);...

Деление двоичных чисел - C++
Пожалуйста помогите!! Даны два двоичных числа, они записанны в строки, и это важное условие(без перевода числа в целое)... Необходимо...

Деление комплексных чисел - C++
Запуталась с делением комплексных чисел. Помогите пожалуйста. struct complex { double a; double b; }A,B,C; void...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
05.11.2010, 18:19     Деление больших чисел #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
//////////////////////////////////////////////////////////////////////////////////////
//Необходимо разделить большое чило на большое число.
//Эти числа хранятся в массиве (каждый элемент - одна цифра числа).
//////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_num_s;
//////////////////////////////////////////////////////////////////////////////////////
void  del_leading_zero(T_num_s&  a)
{
    while(a.size() > 1
          && a[0] == '0')
    {
        a.erase(0, 1);
    }
}
//////////////////////////////////////////////////////////////////////////////////////
bool less_for_big_int(T_num_s  a, T_num_s  b)
{
    del_leading_zero(a);
    del_leading_zero(b);
 
    return  a.size() == b.size() ? a < b : a.size() < b.size();
}
//////////////////////////////////////////////////////////////////////////////////////
void  reduce_big_int(T_num_s&  minuend, const T_num_s&  subtrahend)
{    
    for(T_num_s::size_type  cur_pos = 0; cur_pos < subtrahend.size(); ++cur_pos)
    {
        T_num_s::size_type  minuend_cur_pos     = minuend.size()     - 1 - cur_pos;
        T_num_s::size_type  subtrahend_cur_pos  = subtrahend.size()  - 1 - cur_pos;
 
        char&        cur_minuend_dig_ref     = minuend     [minuend_cur_pos];
        const char&  cur_subtrahend_dig_ref  = subtrahend  [subtrahend_cur_pos];
 
        if(cur_minuend_dig_ref >= cur_subtrahend_dig_ref)
        {
            cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0';
        }
        else
        {
            (cur_minuend_dig_ref -= cur_subtrahend_dig_ref - '0') += 10;
            for(int i = 1; ; ++i)
            {
                if(minuend[minuend_cur_pos - i] == '0')
                {
                    minuend[minuend_cur_pos - i] = '9';
                }
                else
                {
                    --minuend[minuend_cur_pos - i];
                    break;
                }
            }
        }
        del_leading_zero(minuend);
    }
    del_leading_zero(minuend);
}
//////////////////////////////////////////////////////////////////////////////////////
void  inc_big_int(T_num_s&  a)
{    
    for(T_num_s::size_type  cur_pos = a.size() - 1;; --cur_pos)
    {
        if(a[cur_pos] < '9')
        {
            ++a[cur_pos];
            return;
        }
        else
        {
            a[cur_pos] = '0';
            if(cur_pos == 0)
            {              
                a.insert(0, "1");
                return;
            }
        }    
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_num_s  div_big_int(const T_num_s&  a, const T_num_s&  b)
{
    if(b == "0")
    {
        return  "division into zero";
    }    
 
    T_num_s  res = "0";
    T_num_s  minuend     = a;
    T_num_s  subtrahend  = b;
    
    while(subtrahend.size() < minuend.size())
    {
        subtrahend += '0';    
    }
 
    for(;;)
    {
        while(!less_for_big_int(minuend, subtrahend))
        {
            reduce_big_int(minuend, subtrahend);
            inc_big_int(res);
        }
        if(subtrahend.size() <= b.size())
        {
            break;
        }
        
        subtrahend.erase(subtrahend.size() - 1);   
        res += '0';              
        del_leading_zero(res);
    }          
    
    return  res;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    for(;;)
    {
        std::cout << "a = ";
        T_num_s  a;
        std::cin >> a;
        del_leading_zero(a);
 
        std::cout << "b = ";
        T_num_s  b;
        std::cin >> b;
        del_leading_zero(b);
 
        std::cout << "a / b = "
                  << div_big_int(a, b)
                  << std::endl
                  << std::endl
                  << std::endl;    
    }
}
Runa
131 / 83 / 3
Регистрация: 28.08.2009
Сообщений: 363
07.11.2010, 15:14  [ТС]     Деление больших чисел #3
Спасибо большое за вашу реализацию.
Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю
C++
1
2
3
4
 while(subtrahend.size() < minuend.size())
    {
        subtrahend += '0';    
    }
Заранее спасибо
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.11.2010, 23:19     Деление больших чисел #4
Цитата Сообщение от Maruna Посмотреть сообщение
Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю
Да это, собственно, алгоритм обычного деления в столбик.
Runa
131 / 83 / 3
Регистрация: 28.08.2009
Сообщений: 363
08.11.2010, 10:20  [ТС]     Деление больших чисел #5
Огромное спасибо, все ясно. Превосходное решение задачи
anrayt
0 / 0 / 0
Регистрация: 10.06.2014
Сообщений: 1
11.06.2014, 15:20     Деление больших чисел #6
Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению

Добавлено через 18 часов 14 минут
Mr.X, Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению
masterdov
0 / 0 / 0
Регистрация: 23.10.2016
Сообщений: 35
31.10.2016, 03:56     Деление больших чисел #7
Mr.X, зачем нужна эта функция и как она работает
Цитата Сообщение от Mr.X Посмотреть сообщение
subtrahend.erase(subtrahend.size() - 1);
?
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
31.10.2016, 09:24     Деление больших чисел #8
Цитата Сообщение от masterdov Посмотреть сообщение
Mr.X, зачем нужна эта функция и как она работает

Цитата Сообщение от Mr.X
C++
1
subtrahend.erase(subtrahend.size() - 1);
?
Ну, здесь реализован обычный алгоритм деления в столбик.
Если мы делим, например, 500 на 15, то мы сначала добавляем ноль к 15 и вычитаем 150 из 500, пока остаток не станет меньше 150. Получаем остаток 50. Теперь что мы делаем? Отбрасываем ноль у 150, получая 15, и уже 15 вычитаем из 50.
В процитированной строчке кода как раз и производится это отбрасывание нуля у вычитаемого.
masterdov
0 / 0 / 0
Регистрация: 23.10.2016
Сообщений: 35
05.11.2016, 12:52     Деление больших чисел #9
Mr.X,А если
Цитата Сообщение от Mr.X Посмотреть сообщение
(subtrahend.size() - 1)
представить в виде числа , например
C++
1
2
int AAA;
AAA=subtrahend.size() - 1
что будет делать функция? или, если вместо -1, ничего не напишем или -2,+2?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2016, 15:14     Деление больших чисел
Еще ссылки по теме:

Деление комплексных чисел - C++
Вот код #include &lt;iostream&gt; #include &lt;math&gt; using namespace std; typedef struct { float re, im; } cmplx; cmplx cmplx_div(...

Деление вещественных чисел - C++
Есть float a,b,rez; Делю 4 на 2 = 2 все нормально. 2 на 4 ответ 0 Как правильно делить вещественные числа в с++?

Деление длинных чисел - C++
Код который делит очень длинное число на обычное число. Если вводить 121 и 2 выводит неправильный ответ. Какие условия надо поставить...

Деление двух чисел - C++
составить программу делится ли одно число на другое без остатка. Я составил, программа к рассмотрению: #include &quot;windows.h&quot; #include...

Деление длинных чисел столбиком - C++
Привет. У меня возникла проблема при написании курсовой. Необходимо реализовать деление двух больших чисел(записанных &quot;зеркально&quot;). Хотя я...


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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
05.11.2016, 15:14     Деление больших чисел #10
Цитата Сообщение от masterdov Посмотреть сообщение
что будет делать функция?
Функция erase в std::string удаляет весь конец строки, начиная с указанной позиции.
Нам нужно удалить последний символ, поэтому передаем в функцию последнюю позицию.
С момента написания программы стандарты стали удобнее, теперь последний символ строки можно удалить функцией pop_back.
Yandex
Объявления
05.11.2016, 15:14     Деление больших чисел
Ответ Создать тему
Опции темы

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