java - 如何将Pascal Triangle Generator从2-D数组转换为1-D数组？

我有个问题。

我已经使用2-D数组在Java中制作了一个Pascal Triangle Generator程序，它通常很简单。
但是，我似乎无法弄清楚如何仅使用一维数组来编程相同的东西。

有没有人有什么建议？我会尽可能地尝试插入一次代码，但我一般是这样问的。将2D数组转换为1D数组时应该考虑什么？

谢谢。

最佳答案

到目前为止发布的所有答案都给出了将2D数组转换为1D数组的解决方案。据我所知，将Pascal三角形存储在静态尺寸的2D数组中效率很低，因为大约有一半的条目未使用。

主要问题是三角形是……很好，是三角形，而矩形2D矩阵相对容易展开。

但是，展开三角形仍然非常简单。您只需要弄清楚每个偏移量在哪里。考虑将您的Pascal三角形存储在一维数组中，如下所示：

1,1,1,1,2,1,1,3,3,1

考虑帕斯卡三角形中的第i行。它的第一个条目位于一维数组的第（1 + 2 + ... + i-1）个条目中。这是一个简单的算术级数和，其求和为（i-1）（i）/ 2。因此，编写一些函数，例如：

int getArrayOffset(int row, int offset) {
  // assert(row>0);
  return (row*(row-1))/2 + offset - 1;
}

int calculateEntry(int row, int offset, int[] triangle) {
  triangle[getArrayOffset(row,offset)] = triangle[getArrayOffset(row-1,offset-1)]+triangle[getArrayOffset(row-1,offset)];
}

void calculatePascal(int n) {
  int [] triangle = new int[getArrayOffset(n+1,1)];
  for (int row=1; row <=n; row++) {
    triangle[getArrayOffset(row,1)]=1;
    triangle[getArrayOffset(row,row)]=1;
    for (int offset=2; offset < row; offset++) {
       calculateEntry(row,offset,triangle);
    }
  }
}

关于java - 如何将Pascal Triangle Generator从2-D数组转换为1-D数组？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20822590/