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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 57, средняя оценка - 4.63
Runa
 Аватар для Runa
130 / 82 / 3
Регистрация: 28.08.2009
Сообщений: 363
04.11.2010, 14:16     Деление больших чисел #1
Здравствуйте, уважаемые форумчане.
Необходимо разделить большое чило на большое число.
Эти числа хранятся в массиве ( каждый элемент - одна цифра числа).
Подскажите пожалуйста алгоритм деления, код не обязателен, просто хотя бы самую суть.
Делить необходимо по простому, не используя различные методы высшей математики.
Буду очень благодарна!
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
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
 Аватар для Runa
130 / 82 / 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
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
07.11.2010, 23:19     Деление больших чисел #4
Цитата Сообщение от Maruna Посмотреть сообщение
Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю
Да это, собственно, алгоритм обычного деления в столбик.
Runa
 Аватар для Runa
130 / 82 / 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
Сообщений: 21
31.10.2016, 03:56     Деление больших чисел #7
Mr.X, зачем нужна эта функция и как она работает
Цитата Сообщение от Mr.X Посмотреть сообщение
subtrahend.erase(subtrahend.size() - 1);
?
Mr.X
Эксперт С++
 Аватар для Mr.X
2799 / 1575 / 246
Регистрация: 03.05.2010
Сообщений: 3,656
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
Сообщений: 21
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++ Деление вещественных чисел
Деление шеснадцатиричных чисел C++
Деление двух чисел C++

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

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

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