Как насчёт challenge'а?

(Reply to this) (Parent) (Thread)

Я, признаться, не понял, в чем проблема. Как при делении в столбик не определить текущую цифру неполного частного? Ну, рассмотрение начальных цифр делителя и делимого сводит количество априорных вариантов к двум (ну или к трем, но вроде к двум), дальше надо умножить делимое на меньший из двух априорных вариантов неполного частного и сравнить с делимым.

(Reply to this) (Parent) (Thread)

Сколько начальных цифр делимого и делителя рассматривается?
И сколько остаётся вариантов и какие они?

(Reply to this) (Parent) (Thread)

Вроде по одной хватает, чтобы осталось (не более чем) три варианта. Если умножать не "с конца", а "с начала", то число вариантов быстро уменьшится до двух. Самое сложное, когда у делителя первая цифра 1. Я могу сформулировать более четко, но не вижу в этом, признаться, никакого челленджа.

(Reply to this) (Parent) (Thread)

Если брать одну цифру от делителя, то ошибка может достигать половины основания системы счисления. Как раз, когда у делителя первая цифра 1. А вовсе не три варианта. Скажем, для десяти имеем 5: 100/19=5, 10/1=10.

Челлендж как раз и состоит в том, чтобы сформулировать искомое правило сразу, полностью и чётко.
Имеется ввиду, что никто не держит у себя в голове чёткой процедуры деление (она, впрочем, не особо нужна).

(Reply to this) (Parent) (Thread)

Действительно. Ну если по две цифры брать, то получится О(1) проверок, потому что отношение двух соседних двузнычных чисел есть 1+О(1/n) (n --- основание системы), так что относительная погрешность частного будет 1+O(1/n), поэтому абсолютная будет O(1).

(Reply to this) (Parent) (Thread)

Почти верно. Осталась ещё одна неточность:
иногда от делимого надо брать три цифры.
Кнут в Искусстве программирования делает очень похоже. Только он в начале
несколько раз удваивает делитель, чтобы старшая цифра была не меньше половины основания.

(Reply to this) (Parent) (Thread)

Не понял, зачем и когда три цифры надо.

(Reply to this) (Parent) (Thread)

Когда делим 100 на 19, например.

(Reply to this) (Parent) (Thread)

так вроде если делить 110 на 19, не сильно больше получается?

(Reply to this) (Parent) (Thread)

Это правда, но проблема в том, что по сути мы все равно делим трёхзначное число на двузначное.
В противном случае мы бы делили 10 на 19 и получили бы 0.

(Reply to this) (Parent)

Начнём пробовать с 1.

Мы начинаем домножать делитель на пробу "слева" и при этом считаем, сколько осталось от делимого и имеем оценку, сколько у нас может добавиться от хвоста. С каждым шагом от хвоста может добавиться на порядок меньше. Если от делимого осталось больше, чем делитель + оценка добавки от хвоста, значит пробу нужно увеличить на один, если осталось меньше, чем делитель - ответ получен.

Формально проб много, но не более двух пойдут дальше двух цифр.

(Reply to this) (Parent)