Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.83/40: Рейтинг темы: голосов - 40, средняя оценка - 4.83
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131

Длинная арифметика: деление с остатком двух чисел, находящихся в двусвязном списке

03.05.2017, 14:10. Показов 7894. Ответов 35
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток.
Подскажите, как реализовать деление с остатком двух чисел, находящихся в двусвязном списке, узлы которого - цифры.
Оба числа - положительные.

Первое что пришло в голову - пока число x меньше числа y
Производить умножение y на i, и увеличивать i на единицу.
Когда же будет больше - отнять от получившегося исходный x.
Но вот с реализацией как-то всё очень плохо..

P.S.
Использовать шаблоны - нельзя.
ООП - тоже.
Вообще, по заданию нужно найти НОД. Я же взял алгоритм с вычитанием. В итоге числа 99999999999 и 9 по понятным причинам считает очень долго.
Если можно как-то улучшить мою уже реализованную идею - буду благодарен.

Нужны только идеи
За ранее благодарен
0
Лучшие ответы (1)
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
03.05.2017, 14:10
Ответы с готовыми решениями:

Длинная арифметика, деление чисел
https://www.cyberforum.ru/attachment.php?attachmentid=393890&stc=1&d=1398936287 Помоги с решием , желательно код.Заранее спасибО!

Длинная арифметика. Реализовать деление и умножение целочисленных чисел
Добрый день. Нужно реализовать деление и умножение целочисленных чисел Читал http://e-maxx.ru/algo/big_integer , деление длинного на...

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

35
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
03.05.2017, 14:13
Teratore, деление "в стоблик" из курса школьной математики помнишь?
Вот так и дели. Подробнее можно глянуть во, вроде, третьем томе Кнута.
1
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
03.05.2017, 14:35  [ТС]
Цитата Сообщение от nonedark2008 Посмотреть сообщение
деление "в стоблик" из курса школьной математики помнишь?
ну, такое, вспоминать буду. Вчера пытался, как-то не вышло толком. Можете кратко набросать алгоритм??(не школьного деления)
Я делал как-то так:
К примеру, есть
419 делить на 5
4 на 5 - не делится, записывал 4-ку во временную переменную. Брал потом единицу, плюсовал ее, умножив на 10.
41 делил на 5.

Вопрос, новую переменную заводить под хранение нового числа и остатка?
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
03.05.2017, 14:41
Лучший ответ Сообщение было отмечено Teratore как решение

Решение

Code
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
Деление a / b
 
quot = 0;    // частное
rem = a;    // остаток
sub = b;
add = 1;
shifts = 1;
while( sub < rem )
{
    sub <<= 1;    // сдвиг на 1 цифру
    add <<= 1;    // сдвиг на 1 цифру
    shifts++;
}
 
while( shifts )
{
    while( rem >= sub )
    {
        rem -= sub;
        quot += add;
    }
    sub >>= 1;    // сдвиг на 1 цифру
    add >>= 1;    // сдвиг на 1 цифру
    shifts--;
}
Вроде так
1
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
03.05.2017, 14:41
Цитата Сообщение от nonedark2008 Посмотреть сообщение
третьем томе Кнута
Во втором.
Цитата Сообщение от Teratore Посмотреть сообщение
Можете кратко набросать алгоритм?
Глянь вот тут
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
03.05.2017, 14:47  [ТС]
Цитата Сообщение от GoldenId Посмотреть сообщение
sub <<= 1; // сдвиг на 1 цифру
add <<= 1; // сдвиг на 1 цифру
Без побитовых никак?
Просто у меня с ними плохо, да и проще тогда уже сразу взять алгоритм Евклида, где есть побитовые.
Просто их тогда тоже придется реализовывать для списка..

Цитата Сообщение от nonedark2008 Посмотреть сообщение
Глянь вот тут
Последний пост - то что нужно, буду пробовать
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
03.05.2017, 15:00
Цитата Сообщение от Teratore Посмотреть сообщение
Без побитовых никак?
-->
Цитата Сообщение от GoldenId Посмотреть сообщение
на 1 цифру
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
03.05.2017, 15:17  [ТС]
Цитата Сообщение от GoldenId Посмотреть сообщение
-->
Смысл побитовых я то понимаю, сами алгоритмы с побитовыми(в том числе и ваш, мне не понятен)
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
03.05.2017, 15:27
Teratore, на 1 цифру, не на 1 бит.
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
03.05.2017, 15:30  [ТС]
Цитата Сообщение от GoldenId Посмотреть сообщение
на 1 цифру,
Упс..
Извиняюсь, сейчас еще раз попробую разобрать.
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
03.05.2017, 15:38
Цитата Сообщение от Teratore Посмотреть сообщение
сами алгоритмы с побитовыми
Представь свои числа в двоичной системе счисления и возрадуйся. Тогда деление можно реализовать только битовыми сдвигами и вычитаниями. Правда эффективность такого алгоритма довольно низкая =)
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
03.05.2017, 15:40  [ТС]
Цитата Сообщение от GoldenId Посмотреть сообщение
a = 121;
b = 4;
quot = 0; // частное
rem = a; // остаток rem = a = 121
sub = b; // sub = b = 4
add = 1;
shifts = 1;
while( sub < rem ) 1.( 4<121 ) 2. (40 < 121)
{
sub <<= 1; // 1. сдвиг на 1 цифру sub = 40; 2. sub =400
add <<= 1; // 2. сдвиг на 1 цифру add =10; 2. add = 100;
shifts++; // 1. 2; 2. 3
}
while( shifts ) while (3)
{
while( rem >= sub ) 121 >=400; ??/
{
rem -= sub;
quot += add;
}
sub >>= 1; // сдвиг на 1 цифру // 1. 40; 2. 4 3. 0??
add >>= 1; // сдвиг на 1 цифру // 2. 10 2. 1 3. 0??
shifts--;
}
Хм.. Что-то не так опять делаю.

Цитата Сообщение от nonedark2008 Посмотреть сообщение
Представь свои числа в двоичной системе счисления и возрадуйся. Тогда деление можно реализовать только битовыми сдвигами и вычитаниями. Правда эффективность такого алгоритма довольно низкая =)
Тяжко пока идет, по побитовым толком ничего и не было. Так вскольз в вузе пробежались..
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
04.05.2017, 20:46  [ТС]
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
LongNumber * Mod(LongNumber *A, LongNumber *B)
    {
        LongNumber * tempNumb = (LongNumber *)malloc(sizeof(LongNumber));
        tempNumb->Head = tempNumb->Tail = NULL;
        tempNumb->size = 0;
        Item * tempfirst = A->Tail;
        Item * tempsecond = B->Tail;
 
        while (true)
        {
            while (tempNumb->size <= B->size)
            {
                AddDigit(tempNumb, tempfirst->digit);
                tempfirst = tempfirst->prev;
            }
            if (MoreThen(tempNumb, B) == false)
            {
                AddDigit(tempNumb, tempfirst->digit);
            }
 
            LongNumber * Iterator = (LongNumber *)malloc(sizeof(LongNumber));
            Iterator->Head = Iterator->Tail = NULL;
            LongNumber * IteratorHelp = (LongNumber *)malloc(sizeof(LongNumber));
            IteratorHelp->Head = IteratorHelp->Tail = NULL;
            Iterator->size = IteratorHelp->size = 0;
            AddDigit(Iterator, 1);
            AddDigit(IteratorHelp, 1);
            LongNumber * С = (LongNumber *)malloc(sizeof(LongNumber));
            С->Head = С->Tail = NULL;
            С->size = 0;
            while (true)
            {
                С = Multi(Iterator, B);
                if (MoreThen(С, tempNumb))
                    break;
                LongSumLong(Iterator, IteratorHelp);
            }
            A = Minus(A, С);
            if (MoreThen(A, B) == true) //вот тут проблемы.
            {
                continue;
            }
            else    return A;
 
        }
Вот, набросал тут. Мучился с умножением, но вроде получилось.
Деление так и не отмучал..

Что происходит:
в tempNumber пихается первое число, состоящее из цифр А, которое будет делится на B.
в C - записываю произведение итератора на B, пока оно не станет больше чем tempNumb. Как только стало - останавливаю цикл.
Делаю 2 переменные итераторы. Одна - сам итератор, вторая переменная которая будет его увеличивать на единицу.
Не получается довести до конца, может кто-нибудь помочь?
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
04.05.2017, 21:13
Попробуйте назвать Ваши переменные осмысленно. Может помочь. Мне помогало.
Цитата Сообщение от Teratore Посмотреть сообщение
в tempNumber пихается первое число
- остаток (на момент окончания работы кода, инициализируется делимым, A), reminder.
Цитата Сообщение от Teratore Посмотреть сообщение
Делаю 2 переменные итераторы.
- так понимаю, частное (на момент окончания кода, инициализируется нулём), quotient и добавляемое к нему, инициализируется единицей), add.
Если так, то у Вас не хватает вычитаемого (инициализируемого делителем, b) из остатка - sub.
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
04.05.2017, 23:20  [ТС]
Цитата Сообщение от GoldenId Посмотреть сообщение
Попробуйте назвать Ваши переменные осмысленно. Может помочь. Мне помогало.
Хорошо, попробую завтра.
Цитата Сообщение от GoldenId Посмотреть сообщение
Если так, то у Вас не хватает вычитаемог
Изначально у меня идея такая:
Взять делить, и умножать на переменную итератор, всё это занести в переменную C к примеру, итератор будет увеличиваться на единицу каждый раз. К какому-то моменту, эта переменная C станет больше чем делимое.
От С потом отпнять делимое, и получить остаток.
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
04.05.2017, 23:27
Цитата Сообщение от Teratore Посмотреть сообщение
Взять делить
Это какой язык?
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
04.05.2017, 23:30  [ТС]
Цитата Сообщение от Teratore Посмотреть сообщение
Взять делить,
Взять делитель.
Цитата Сообщение от Teratore Посмотреть сообщение
От С потом отпнять делимое, и получить остаток.
от С потом отнять делимое, и получить остаток.
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
04.05.2017, 23:41
Цитата Сообщение от Teratore Посмотреть сообщение
Взять делитель.
Отнимать нужно от переменной, инициализируемой делимым.
Цитата Сообщение от Teratore Посмотреть сообщение
от С потом отнять делимое
Отнимать нужно переменную, инициализируемую делителем,
Цитата Сообщение от Teratore Посмотреть сообщение
и умножать на переменную итератор
сдвигаемую на 1 цифру каждый раз. При первом проходе для поиска старшей позиции сдвиг влево, при втором проходе для вычитания, сдвиг вправо.
0
2 / 2 / 2
Регистрация: 10.12.2015
Сообщений: 131
05.05.2017, 13:12  [ТС]
Цитата Сообщение от GoldenId Посмотреть сообщение
Деление a / b
quot = 0; // частное
rem = a; // остаток
sub = b;
add = 1;
shifts = 1;
while( sub < rem )
{
sub <<= 1; // сдвиг на 1 цифру
add <<= 1; // сдвиг на 1 цифру
shifts++;
}
while( shifts )
{
while( rem >= sub )
{
rem -= sub;
quot += add;
}
sub >>= 1; // сдвиг на 1 цифру
add >>= 1; // сдвиг на 1 цифру
shifts--;
}
Вы предлагаете таким способом делать?? Или по другому как-то?

Я просто не до конца пока понимаю, что к чему..

По поводу "сдвигов" я правильно понимаю, что при сдвиге влево, мы убираем из числа нулевой разряд? (Т.е. было 124) стало 12? При сдвиге в право - убираем первую цифру, т.е. 1 и получаем 24.
0
 Аватар для GoldenId
142 / 143 / 64
Регистрация: 11.11.2010
Сообщений: 877
Записей в блоге: 10
06.05.2017, 02:28
Цитата Сообщение от Teratore Посмотреть сообщение
Я просто не до конца пока понимаю, что к чему..
Первым циклом while ищется старшая позиция вычитаемого sub, вторым циклом это вычитаемое вычитается из остатка, одновременно с чем сдвинутая на соотв число разрядов единица прибавляется к частному.

Цитата Сообщение от Teratore Посмотреть сообщение
По поводу "сдвигов" я правильно понимаю, что при сдвиге влево, мы убираем из числа нулевой разряд? (Т.е. было 124) стало 12?
Это сдвиг вправо.

Цитата Сообщение от Teratore Посмотреть сообщение
По поводу "сдвигов" я правильно понимаю, что при сдвиге влево, мы убираем из числа нулевой разряд? (Т.е. было 124) стало 12? При сдвиге в право - убираем первую цифру, т.е. 1 и получаем 24.
Можете умножать и делить на основание Вашей системы счисления, но это более дорогая по времени операция.

Если делите длинные числа - Ваша задача позаботиться, чтобы во всех нужных переменных было достаточное количество разрядов. Если арифметика целочисленная - то только соответствующих целым степеням основания системы счисления.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
06.05.2017, 02:28
Помогаю со студенческими работами здесь

Длинная арифметика: операция сравнения двух чисел (A >= B)
Привет всем! помогите пожалуйста кодом. Необходимо реализовать операцию сравнения двух длинных чисел A&gt;=B Заранее спасибо

Длинная арифметика. Перемножение двух больших чисел
Насчет алгоритма выполнения не могу пока что сказать ничего. Дело в том, что после того, как ввожу первое число и нажимаю Enter, каретка...

Длинная арифметика. Вычитание двух положительных чисел
Доброго времени суток! У меня не получается сделать вычитание двух длинных положительных чисел... Пыталась разбираться по чужим кодам -...

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

Длинная арифметика. Умножение двух длинных чисел.
Есть 2 числа, храняющиеся в int векторах, нужна функция, которая возвращает их произведение также в виде вектора. Либо простой и понятно...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru