#algorithm #division #base #integer-division
#алгоритм #деление #База #целочисленное деление
Вопрос:
Целые числа представлены в виде списка целых чисел, например:
- [13, 2] (D2 в базе 16)
- [1, 3, 6] (136 в базе 10)
Нам разрешено использовать цифры только по отдельности, они не могут быть преобразованы в целые числа с базовым 10.
Я хотел реализовать деление способом «бумага и карандаш«, иначе называемым «длинным делением«, но оказывается, что для этого требуется, чтобы префиксы делителя и делимого были целыми числами по основанию 10, чтобы иметь возможность выполнять целочисленное деление по основанию 10.
например: чтобы найти 11131/1177, нам нужно сначала найти 1113/1177
Есть ли какой-либо способ разложить деление, подобное 1113/1177, на более мелкие шаги, которые не потребуют никаких делений, кроме таких, чтобы делитель находился в замкнутом диапазоне [1, база — 1]?
Есть ли какой-либо другой способ выполнить это деление не так, как «бумага и карандаш»?
Комментарии:
1. Что вам нужно уметь делать: вычитать, сравнивать, умножать многозначное число на однозначное число. Чтобы найти
1113 / 117в базе B, выполните двоичный поиск в диапазоне [1, B-1]. Для каждой попытки умножьте 117 на цифру кандидата и сравните с 1113. После нахождения наибольшей цифры D такой, чтобы117 * D <= 1113вычесть 117 * D из 1113. Затем переходите к следующему шагу длинного деления.2. Вам не нужно базовое 10 деление. Paper-and-pensil работает одинаково в любой базе.
3. @user58697 Я думаю, что вы пропустили суть моей проблемы. Я не могу выполнить какое-либо деление с делителем вне [1, база — 1] независимо от базы, потому что это потребовало бы от меня преобразования списка целых чисел в одно число, что мне не разрешено делать. Базовое 10 деление также является единственным доступным в типичной реализации int, кроме битовых сдвигов
4. @user3386109 Я ищу более «прямое» решение, но предложенное u на самом деле правильное, так что спасибо
5. Я не понимаю значения базы 10 в этом вопросе. Большинство компьютеров представляют числа в базе 2.