超过整数最大值的解决方案？

Question

你好亲爱的社区,

我一直在考虑这个问题很长一段时间但似乎无法找到解决方案.

我有我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;
}

Answer 1

AFAICT你只使用resp.需要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;
}

注意:如果我做lim_fac()对了,我不是百分百确定,但你应该明白这一点.