Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/48: Рейтинг темы: голосов - 48, средняя оценка - 4.75
Runa
133 / 85 / 22
Регистрация: 28.08.2009
Сообщений: 363
#1

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

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

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

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

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

Деление больших чисел (нужно ускорить)
Ребятки, помогите ускорить. Уж очень медленно. Класс совсем простой(вектор...

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

Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел больших 20
Вводится последовательность из N вещественных чисел. Определить наименьшее...

10
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 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;    
    }
}
3
Runa
133 / 85 / 22
Регистрация: 28.08.2009
Сообщений: 363
07.11.2010, 15:14  [ТС] #3
Спасибо большое за вашу реализацию.
Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю
C++
1
2
3
4
 while(subtrahend.size() < minuend.size())
    {
        subtrahend += '0';    
    }
Заранее спасибо
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
07.11.2010, 23:19 #4
Цитата Сообщение от Maruna Посмотреть сообщение
Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю
Да это, собственно, алгоритм обычного деления в столбик.
0
Runa
133 / 85 / 22
Регистрация: 28.08.2009
Сообщений: 363
08.11.2010, 10:20  [ТС] #5
Огромное спасибо, все ясно. Превосходное решение задачи
0
anrayt
0 / 0 / 0
Регистрация: 10.06.2014
Сообщений: 1
11.06.2014, 15:20 #6
Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению

Добавлено через 18 часов 14 минут
Mr.X, Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению
0
masterdov
0 / 0 / 1
Регистрация: 23.10.2016
Сообщений: 46
31.10.2016, 03:56 #7
Mr.X, зачем нужна эта функция и как она работает
Цитата Сообщение от Mr.X Посмотреть сообщение
subtrahend.erase(subtrahend.size() - 1);
?
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 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.
В процитированной строчке кода как раз и производится это отбрасывание нуля у вычитаемого.
1
masterdov
0 / 0 / 1
Регистрация: 23.10.2016
Сообщений: 46
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?
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.11.2016, 15:14 #10
Цитата Сообщение от masterdov Посмотреть сообщение
что будет делать функция?
Функция erase в std::string удаляет весь конец строки, начиная с указанной позиции.
Нам нужно удалить последний символ, поэтому передаем в функцию последнюю позицию.
С момента написания программы стандарты стали удобнее, теперь последний символ строки можно удалить функцией pop_back.
2
makroys
0 / 0 / 0
Регистрация: 12.09.2017
Сообщений: 6
12.09.2017, 01:06 #11
Mr.X, здравствуйте, как вашу программу можно применить к моей задаче: вводится большое число, равное факториалу определенного числа, например !n при n=20, где нужно методом деления больших чисел найти n?

Алгоритм следующий. В вашей программе в строку а вводится определенное число.
А вместо строки b сделать счетчик, на который будет делиться строка a до тех пор, пока a не будет равен единице.

Программированием занимаюсь недавно, поэтому 80% кода мне не понятны.
0
12.09.2017, 01:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2017, 01:06

Вводится последовательность из N вещественных чисел. Определить наименьшее число, среди чисел больших 20.
Вводится последовательность из N вещественных чисел. Определить наименьшее...

Посчитать количество чисел, больших 0 и меньших N, сумма чисел которых и их реверс являются палиндромом
объясните пож не совсем понимаю задание

Деление двух чисел
составить программу делится ли одно число на другое без остатка. Я составил,...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

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