Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/18: Рейтинг темы: голосов - 18, средняя оценка - 4.50
 Аватар для Virts
26 / 26 / 22
Регистрация: 08.06.2013
Сообщений: 106

Многократное "длинное" деление (длинного на короткое)

11.10.2014, 22:35. Показов 3528. Ответов 9
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
В общем есть задача на перевод с одной системы счисления в другие, где нужно использовать длинную арифметику (деление длинного на короткое). Само деление я смог написать, но не могу правильно повторять его и брать остаток (делю число в десятичной системе). Не буду писать много, чтобы не запутать, ниже опишу лишь цикл деления и его переменные.
C++
1
2
3
4
5
6
7
8
9
10
for(int i = 0; i<count; i++) {
        rez[i] = (long_dv[i] + ost * 10);
        ost = rez[i] % sys_sch;
        rez[i] = rez[i] / sys_sch;
    }
/* count - количество цифр числа, rez[i] - массив 
с частным от деления, long_dv - массив, где лежит число
 (в десятичной системе) ost - остаток от деления, sys_sch - 
система счисления, в которую нужно перевести (ну, или просто делитель, по-сути). 
*/
Понимаю, что если первые элементы меньше делителя, то на начале будут нули, но сам массив отдельно сдвинуть я смогу, проблема не в этом. Весь этот цикл нужно взять в еще один, который будет выполнятся до тех пор, пока число не "доделится" полностью, и не будет заполнен массив "остатков" от каждого деления. Но как узнать нужное количество итераций - я понять не могу. Буду очень благодарен за помощь, скажу честно, что на задачу убиваю уже второй день.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.10.2014, 22:35
Ответы с готовыми решениями:

Деление длинного числа на длинное
Всем привет! Решил написать длинную арифметику в самом ее классическом варианте, когда все операции производятся школьным столбиком....

Деление длинного на длинное и печать периода если он есть
Всем доброй ночи форумчане. Прошу помощи, буду рад любому совету или коду. Деление длинного на длинное написал, сейчас нужно чтобы выводил...

Деление длинного числа на короткое
Нужно реализовать деление двух больших чисел (произвольно больших), конкретно деление длинного числа на короткое (это приоритет) и длинного...

9
 Аватар для ronaldo
94 / 48 / 63
Регистрация: 16.06.2014
Сообщений: 386
12.10.2014, 09:39
Перевод из десятичной в любую с/с с основанием, меньшим, чем число:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
int main(){
    int rez,ost,chislo,sys_sch,i=0;
    cin>>rez;
    cin>>sys_sch;
    while(rez>=sys_sch) {ost=rez%sys_sch;
                        rez=rez/sys_sch;
                        chislo+=ost*pow(10,i++);
   }
    chislo+=rez*pow(10,i);
    cout<<chislo<<endl;   
    getch();    
    return 0;
}
0
 Аватар для Virts
26 / 26 / 22
Регистрация: 08.06.2013
Сообщений: 106
13.10.2014, 16:43  [ТС]
Спасибо, но нужна "long arithmetic"

Добавлено через 6 часов 53 минуты
Тема актуальна

Добавлено через 21 час 22 минуты
актуально
0
 Аватар для Virts
26 / 26 / 22
Регистрация: 08.06.2013
Сообщений: 106
14.10.2014, 20:05  [ТС]
вверх
0
Эксперт С++
 Аватар для Avazart
8484 / 6151 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
14.10.2014, 20:24
http://e-maxx.ru/algo/big_integer
0
 Аватар для Virts
26 / 26 / 22
Регистрация: 08.06.2013
Сообщений: 106
15.10.2014, 23:25  [ТС]
Здесь описан алгоритм деления длинного на короткое:
C++
1
2
3
4
5
6
7
8
int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
    long long cur = a[i] + carry * 1ll * base;
    a[i] = int (cur / b);
    carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();
Правда, от моего немного отличается: во-первых, почему они начинают деление с конца?
во-вторых, что значит 1ll здесь? (base, я так понимаю, система счисления, которой задано число на входе)
в-третьих, что делает этот цикл?
C++
1
2
 while (a.size() > 1 && a.back() == 0)
    a.pop_back();
0
Эксперт С++
 Аватар для Avazart
8484 / 6151 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
16.10.2014, 00:33
Цитата Сообщение от Virts Посмотреть сообщение
во-вторых, что значит 1ll здесь?
C++
1
long long int i= 1;
Т.е подчеркивают что тип единицы long long.

Цитата Сообщение от Virts Посмотреть сообщение
в-третьих, что делает этот цикл?
Обрезку незначащих нулей впереди.

Добавлено через 43 секунды
Цитата Сообщение от Virts Посмотреть сообщение
Правда, от моего немного отличается: во-первых, почему они начинают деление с конца?
Я не помню нужно смотреть как они там записывают.
1
 Аватар для Virts
26 / 26 / 22
Регистрация: 08.06.2013
Сообщений: 106
16.10.2014, 00:45  [ТС]
спасибо, еще только один вопрос, но он и есть самым проблемным)
Алгоритм самого деления мне ясен, но уже не один день долблюсь, чтобы иметь возможность брать "конечный" остаток от деления числа, а потом делать повторения до тех пор, пока число не поделится полностью. Только таким способом додумался зделать программу для перевода с разных систем счислений. Но вот брать остаток и контролировать итерации не получается. Иногда бывает, что в массив вписываются по две цифры, так же возможны ситуации, когда число после деления вовсе не уменьшается, а бывает, что уменьшается сразу на 2 цифры, соотвественно количество новых итераций нужно изменять в соотвествии с этим, но как "контролировать" все эти процессы сразу не знаю, хотя писал уже 3 разных подхода для деления...
0
Эксперт С++
 Аватар для Avazart
8484 / 6151 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
16.10.2014, 00:51
А задача учебная? Ибо есть готовые библиотеки работы с длинными числами типа gmp и NTL
0
 Аватар для Virts
26 / 26 / 22
Регистрация: 08.06.2013
Сообщений: 106
16.10.2014, 20:53  [ТС]
учебная, я реализовал её просто через "двоичные куски", то есть преподаватель мне галочку поставил, но говорит, что для уверенности разберись с таким подходом (ведь кроме систем счислений нужно было и в длинную арифметику "врубится"), а так еще и про BigInteger читал, но готовые библиотеки не вариант

Добавлено через 19 часов 52 минуты
вверх
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
16.10.2014, 20:53
Помогаю со студенческими работами здесь

Деление длинного числа но короткое
Дано два числа А В надо чему равно a mod b=? i a div b=? Длинная арифметика

Деление длинного числа на короткое.
Помогите срочно решить задачу! Даны два целых числа A и B. Требуется найти целую часть от их частного. Входные данные Во входном...

Деление длинного на длинное
#ifndef INTEGERLONGS_HPP_INCLUDED #define INTEGERLONGS_HPP_INCLUDED ...

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

Длинная арифметика. Чистый СИ. Деление длинного HEX на короткое INT
Всем привет. Не знаю с чего начать.... Есть 8-ми битный микроконтроллер.......... Возникла задача вычитать и делить большие (ну по...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru