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

@Runa · Регистрация: 28.08.2009

Студворк — интернет-сервис помощи студентам

Здравствуйте, уважаемые форумчане.
Необходимо разделить большое чило на большое число.
Эти числа хранятся в массиве ( каждый элемент - одна цифра числа).
Подскажите пожалуйста алгоритм деления, код не обязателен, просто хотя бы самую суть.
Делить необходимо по простому, не используя различные методы высшей математики.
Буду очень благодарна!

@Mr.X · 05.11.2010, 18:19

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 · 07.11.2010, 15:14 **[ТС]**

Спасибо большое за вашу реализацию.
Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю

C++
1
2
3
4
 while(subtrahend.size() < minuend.size())
    {
        subtrahend += '0';    
    }

Заранее спасибо

@Mr.X · 07.11.2010, 23:19

Сообщение от Maruna

Очень прошу, опишите алгоритм.
Особенно непонятно для чего добавляются нули к делителю

Да это, собственно, алгоритм обычного деления в столбик.

@Runa · 08.11.2010, 10:20 **[ТС]**

Огромное спасибо, все ясно. Превосходное решение задачи

@anrayt · 11.06.2014, 15:20

Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению

Добавлено через 18 часов 14 минут
Mr.X, Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению

@masterdov · 31.10.2016, 03:56

Mr.X, зачем нужна эта функция и как она работает

Сообщение от Mr.X

subtrahend.erase(subtrahend.size() - 1);

?

@Mr.X · 31.10.2016, 09:24

Сообщение от masterdov

Mr.X, зачем нужна эта функция и как она работает

Цитата Сообщение от Mr.X

C++
1
subtrahend.erase(subtrahend.size() - 1);

?

Ну, здесь реализован обычный алгоритм деления в столбик.
Если мы делим, например, 500 на 15, то мы сначала добавляем ноль к 15 и вычитаем 150 из 500, пока остаток не станет меньше 150. Получаем остаток 50. Теперь что мы делаем? Отбрасываем ноль у 150, получая 15, и уже 15 вычитаем из 50.
В процитированной строчке кода как раз и производится это отбрасывание нуля у вычитаемого.

@masterdov · 05.11.2016, 12:52

Mr.X,А если

Сообщение от Mr.X

(subtrahend.size() - 1)

представить в виде числа , например

C++
1
2
int AAA;
AAA=subtrahend.size() - 1

что будет делать функция? или, если вместо -1, ничего не напишем или -2,+2?

@Mr.X · 05.11.2016, 15:14

Сообщение от masterdov

что будет делать функция?

Функция erase в std::string удаляет весь конец строки, начиная с указанной позиции.
Нам нужно удалить последний символ, поэтому передаем в функцию последнюю позицию.
С момента написания программы стандарты стали удобнее, теперь последний символ строки можно удалить функцией pop_back.

@makroys · 12.09.2017, 01:06

Mr.X, здравствуйте, как вашу программу можно применить к моей задаче: вводится большое число, равное факториалу определенного числа, например !n при n=20, где нужно методом деления больших чисел найти n?

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

Программированием занимаюсь недавно, поэтому 80% кода мне не понятны.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Runa 134 / 87 / 22 Регистрация: 28.08.2009 Сообщений: 363

	Деление больших чисел 04.11.2010, 14:16. Показов 21745. Ответов 10 Метки нет (Все метки) Здравствуйте, уважаемые форумчане. Необходимо разделить большое чило на большое число. Эти числа хранятся в массиве ( каждый элемент - одна цифра числа). Подскажите пожалуйста алгоритм деления, код не обязателен, просто хотя бы самую суть. Делить необходимо по простому, не используя различные методы высшей математики. Буду очень благодарна! 0

@Runa 134 / 87 / 22 Регистрация: 28.08.2009 Сообщений: 363
	08.11.2010, 10:20 [ТС]
	Огромное спасибо, все ясно. Превосходное решение задачи 0

@anrayt 0 / 0 / 0 Регистрация: 10.06.2014 Сообщений: 1
	11.06.2014, 15:20
	Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению Добавлено через 18 часов 14 минут Mr.X, Вы не могли бы в двух словах описать функции которые использовали , не удается разобраться к сожалению 0

@makroys 0 / 0 / 0 Регистрация: 12.09.2017 Сообщений: 6
	12.09.2017, 01:06
	Mr.X, здравствуйте, как вашу программу можно применить к моей задаче: вводится большое число, равное факториалу определенного числа, например !n при n=20, где нужно методом деления больших чисел найти n? Алгоритм следующий. В вашей программе в строку а вводится определенное число. А вместо строки b сделать счетчик, на который будет делиться строка a до тех пор, пока a не будет равен единице. Программированием занимаюсь недавно, поэтому 80% кода мне не понятны. 0

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

Решение