从帕斯卡三角形中检索值

Question

我有一个一维数组，它保存帕斯卡三角形的值，从左到右计算数字。

int pascal[10] = { 1, 1, 1, 1, 2, 1, 1, 3, 3, 1 };

如何使用它快速找到两个数字的组合？

例如找到 3 选择 1，我会在数组中查找答案 3。如何正确计算我需要查看的索引？

如果我想继续构建 Pascal 的三角形，如何在不进行树递归的情况下使用这个数组来构建它？类似于递归关系

Answer 1

如果您坚持使用数组而不是通过公式计算它，那么您可以使用以下（C# 示例）：

int Choose_N_over_K(int N, int K)
{
    int[] pascal  = new[] { 1, 1, 1, 1, 2, 1,1, 3, 3, 1, 1,4,6,4,1};    
    var index = (N * (N + 1) / 2 +  K  );
    return (pascal[index]);
}


void Main()
{
        Console.WriteLine(Choose_N_over_K(4,2));
}

给予（以 4 比 2 为例）：

我们简单地计算数组中的索引，因为三角形中的每一行都比前一行多一个元素并且我们知道如何对数字求和1..N:

// 0: 1  start index 0
// 1: 1 1  start index 1
// 2: 1 2 1  start index 3 
// 3: 1 3 3 1 start index 6
// 4: 1 4 6 4 1 start index 10

从帕斯卡三角形中检索值

Retrieving a value from pascals triangle

arrays

combinations

pascals-triangle