Решение пройти максимальное значение целого числа?
Здравствуйте уважаемое сообщество,
Я думал об этом уже довольно давно, но, похоже, не могу найти решения.
У меня есть int[][] bino = new int[15][], в котором я вычисляю первые 15 строк пирамиды паскалей, и мне не разрешено менять тип (без двойных, длинных и т. д.).
Мы знаем, что на факультете из 12 человек 479001600 человек.
Максимальное значение int - 2147483647, поэтому fac (12) все еще подходит.
Теперь с последними 3 строками все усложняется.
Fac (13) - 6227020800, что слишком велико для int.
Итак, что происходит, так это то, что для строк 13, 14 и 15 не отображаются правильные числа (потому что 6227020800 mod 2147483647 = 1932053506, что означает, что fac (13) = 1932053506 в моем примере).
Вопрос в том, есть ли способ как-то еще отображать правильные числа, не меняя тип поля в int[][] bino = new int[15][]). Все остальное можно изменить.
public static void main(String args[])
{
int[][] bino = new int[15][]; //Create 2d array for pascal pyramid
for(int i = 0; i < bino.length;i++)
for(int j = 0; j < bino[i].length;j++)
{
binos[i][j] = nOverk(i,j)
}
}
public int nOverk(int n, int k)
{
return(fac(n) / (fac(k) * fac((n-k))));
}
public int fac(int z) //Calculats the faculty of a number
{
int res = 1;
if (z == 0 || z == 1)
return 1;
for(int i = 2; i <= z; i++)
res *= i;
return res;
}
Ответы 3
Простое решение - использовать long, однако вы можете использовать int для больших чисел (и сэкономить работу), вместо этого вычислив fac(a)/fac(b), что более эффективно.
public static void main(String... args) {
int[][] bino = new int[15][]; //Create 2d array for pascal pyramid
for (int i = 0; i < bino.length; i++) {
bino[i] = new int[i + 1];
for (int j = 0; j < i + 1; j++) {
bino[i][j] = nOverk(i, j);
}
}
}
static int nOverk(int n, int k) {
int min = Math.min(k, n - k);
int max = Math.max(k, n - k);
return fac(n, max) / fac(min, 1);
}
static int fac(int hi, int lo) {
if (hi == 0 || hi == 1)
return 1;
int res = 1;
for (int i = lo + 1; i <= hi; i++)
res *= i;
return res;
}
AFAICT вы используете только соотв. нужен fac() для nOverk(). В термине fac(n) / (fac(k) * fac((n-k)))) вы можете исключить некоторые факторы, сохранив временные значения в допустимом диапазоне.
Например, вместо nOverk(4,2) = 4*3*2*1 / ((2*1) * (2 * 1)) вы просто вычисляете (4 * 3) / (2 * 1). Могут быть крайние случаи, когда это не помогает, но я думаю, что задача определена таким образом, и это помогает.
public int nOverk(int n, int k)
{
return (lim_fac(n, k) / lim_fac(k, k));
}
private int lim_fac(int z, int n) //Calculats the "limited" faculty of a number, by multiplying n factors.
{
int res = 1;
if (n == 0) {
return 1;
}
if (n == 1) {
return z;
}
for (int i = z - n + 1; i <= z; i++) {
res *= i;
}
return res;
}
Примечание: я не уверен на 100%, правильно ли я понял lim_fac(), но вы должны уловить идею.
В треугольнике Паскаля каждое число представляет собой сумму двух чисел прямо над ним. Если задача состоит только в том, чтобы напечатать первые 15 строк, вам действительно не нужно использовать факториал.
public static void main(String[] args) {
int n = 15;
int[][] pascal = new int[n+1][];
// initialize first row
pascal[1] = new int[1+2];
pascal[1][1] = 1;
// fill in Pascal's triangle
for (int i = 2; i <= n; i++) {
pascal[i] = new int[i+2];
for (int j = 1; j < pascal[i].length - 1; j++)
pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
}
// print results
for (int i = 1; i <= n; i++) {
for (int j = 1; j < pascal[i].length - 1; j++) {
System.out.print(pascal[i][j] + " ");
}
System.out.println();
}
}
Это, вероятно, лучший ответ, и он должен быть принятым.
в
longможно хранить большие значения, чем в int, или BigInteger. Я обнаружил, что рекомендуется использовать тип данныхlong, если возможно, если нет, то biginteger - см. stackoverflow.com/a/17416986/4892907