Предполагая, что мы интерпретируем это как «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;