Решение пройти мимо максимального значения целого числа?

Question

Здравствуйте, уважаемое сообщество,

Я уже давно думаю об этом, но, похоже, не могу найти решение.

У меня есть int[][] bino = new int[15][], в котором я вычисляю первые 15 строк пирамиды паскалей, и мне не разрешено менять тип (без двойной, длинной и т. Д.).

Мы знаем, что факультет 12 - 479001600

Максимальное значение int равно 2147483647, так что fac (12) по-прежнему вписывается в него.

Теперь, для последних 3 строк, это становится сложным.

Fac (13) - 6227020800, что слишком велико для int.

Так что получается, что для строк 13, 14 и 15 это не будет отображать правильные числа (потому что 6227020800 мод 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;
}

Answer 1

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(), но вы должны понять идею.

Answer 2

В треугольнике Паскаля каждое число является суммой двух чисел непосредственно над ним. Если задача состоит в том, чтобы просто напечатать первые 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();
    }
} 

Answer 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;
}