Как найти остаток от деления чисел с помощью сложения и вычитания?

Question

[Joukai]

Нужно найти остаток от делания только сложением и вычитанием

Answer 1

[rPman]

берем делитель и складываем с самим собой (т.е умножаем на 2), затем полученное число снова складываем.. до тех пор пока результат не станет больше делимого числа (эту сумму не запоминаем, берем предыдущую)
затем на выбор:
* из разницы делимого и текущей суммы, в цикле вычитаем делитель, пока результат не станет меньше нулдя (предыдущий и будет остатком)
* в процессе подсчета суммы делителя промежуточные результаты (массив из n элементов, каждый y*2*n) из разницы делимого вычитаем предыдущую сумму, если результат меньше нуля, не запоминаем результат и переходим к следующей промежуточной сумме, так до тех пор пока не пройдем по всем сохраненным суммам. Последним пробуем вычесть сам делитель.

этот алгоритм заметно эффективнее просто тупого вычитания делителя, второй вариант еще более эффективный но потребляет память log(x)

Answer 2

[pfg21]

блин ну ты ваще.
вычитаешь из делимого делитель до тех пор пока остаток от вычитания не станет меньше делителя

Comments

[Joukai]

while(a > b) {
a = a-b;
}
return a;

так?

Но мне надо это рекурсией
public static float TF(int a, int b) {
if (a > b) {
TF(a-b, b);
}
return a;
}
так не работает

[Sand]

Joukai,

public static int TF(int a, int b) {
if (a < b) {
return a;
}
return TF(a-b, b);
}