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