Решите n выберите k для больших чисел, используя 64-битные числа без переполнения - PullRequest
0 голосов
/ 27 апреля 2020

У меня есть это назначение:

Напишите программу, используя 64-разрядные целые числа, которая отображает значение n , выберите k для данного n и k . Ваша программа не должна иметь доступа к каким-либо функциям с множественной точностью, таким как BigInteger в Java.

Как бы это сделать, не вызывая переполнения?

1 Ответ

3 голосов
/ 27 апреля 2020

Предполагая, что мы интерпретируем это как «display n выбирают k, предполагая, что n и k - неотрицательные длинные значения, а n выбирают k, как известно, соответствуют длинным», это, безусловно, возможно. Поскольку это задание, я не буду напрямую ссылаться на решение, упомяну только, что оно присутствует в классе LongMath в Guava. Однако я попытаюсь в общих чертах описать, как это работает.

Стандарт l oop для вычисления n select k выглядит примерно как

if (k > n / 2) {
  k = n - k;
}
long result = 1;
for (int i = 1; i <= k; n--, i++) {
  result *= n;
  result /= i;
}
return result;

Использование этого неизмененного, безусловно, переполнит большие достаточно значений. Однако важным фактом является то, что на каждом шаге for l oop деление является точным без остатка. Вы можете сделать это, заметив, что когда вы выполняете l oop для заданного значения i, вы только что вычислили n, выберите i.

Итак, вам нужно переписать тело этого l oop таким образом, чтобы оно не переполнялось, при условии, что результат сам по себе не переполняется.

Пусть d будет наибольшим общим делителем result и i. Пусть resultD = result / d и iD = i / d, так что result = resultD * d и i = iD * d. Таким образом, мы можем переписать дробь от result * n / i до (resultD * d * n) / (iD * d) до (resultD * n) / iD. Мы знаем, что эта дробь является точным целым числом, и мы знаем, что resultD и iD не имеют общего делителя (мы все это поделили), поэтому n / iD само должно быть целым числом. Таким образом, мы можем переписать это как resultD * (n / iD) и сделать все это в long математике, без дробей, без двойных чисел.

Поскольку мы убедились, что k <= n / 2, значение result только увеличивается в этом для l oop не уменьшается. Кроме того, n / iD определенно подходит для long, поскольку n / iD <= n и n подходят для long. Таким образом, resultD * (n / iD) будет переполнен только в том случае, если фактическое значение n, выбранное k, будет переполнено.

Итак, что вы хотите для своего l oop, это

long result = 1;
for (int i = 1; i <= k; n--, i++) {
  // calculate resultD and iD...somehow
  result = resultD * (n / iD);
  // do something appropriate in the case of overflow, e.g. throwing or
  // returning Long.MAX_VALUE
}
return result;
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...