解决帕斯卡三角形和牛顿二项式的算法方法

引言

杨辉三角是按照形成规则排列成表格形式的自然数序列。
这是一个包含9行的三角形示例，为了便于理解，行和列已编号（从零开始）

请注意

• 所有行都以数字1开头和结尾；
• 每一行都比其前一行多一个元素。

实际上，这个三角形是一个方阵（T），其中每个元素可以通过以下方式之一获得，其中L是行索引，C是列索引：

T(L,C) = 1, 如果 C = 0 或 L = C
T(L,C) = T(L-1,C) + T(L-1,C-1), 如果 L >= C （斯蒂芬的关系）
（其中 L >= 0 且 C >= 0）

还要注意，（第n+1）行的元素是(a + b) ⁿ展开式的系数。换句话说，要获得二项式(a + b) ²的展开系数，只需查看三角形的第3行即可得到：

(a + b) ² = 1a² + 2ab +1b² 

历史简述

该三角形的第一个已知参考文献归功于阿拉伯人Al-Karaji（953-1029）。此后，来自不同国家的几位数学家都进行了相关的研究，其中，我们引用以下几位：

• 奥马尔·海亚姆（波斯，1048-1131）
• 贾宪（中国，1100-1109）
• 杨辉（中国，1238-1298）
• 卡西（伊朗，1380-1429）
• 彼得鲁斯·阿皮亚努斯（萨克森，1501-1552）
• 迈克尔·斯蒂费尔（德国，1487-1567）
• 尼科洛·塔尔塔利亚（意大利，1499-1577）

法国数学家布莱兹·帕斯卡（1623-1667）对该三角形的规律进行了系统研究，并发表了一篇题为《算术三角形论》的文章，他在其中阐述了“每一行中的数字表示从N个对象集合中选择P个对象的不同方式的数量”。这听起来不就是组合学吗？

帕斯卡是一位哲学家、物理学家、神学家、作家，并且他还有时间在1642年发明了第一台机械计算器，以帮助他的父亲，他也是一位数学家。因此，他被认为是计算机发明的先驱之一。
除了对三角形的研究，帕斯卡还在几何学、微积分基础、概率论、流体力学、静体力学等许多其他领域留下了著作。

三角形最著名的应用是多项式方程的系数。然而，还有许多其他应用，其中我们重点介绍以下几项：

• 斐波那契数列；
• 幂运算；
• 加法；
• 等等。

在帕斯卡之后，沃利斯、牛顿和莱布尼茨等数学家也利用了这个三角形有趣的性质。

背景

为了测试这里介绍的算法，我建议使用以下工具

C++ 语言
Python 语言
Pascal 语言
Haskell 语言

使用代码

以下是通过迭代、递归和函数式范式求解杨辉三角的算法。在所有算法中，我们有以下变量：
L → 数组行索引
C → 数组列索引

1) 迭代算法

// Purpose: Printing the Pascal's triangle iteratively using the Stifel's Relation 
// Parameter: The number of rows you want 
// Language: C++
// Author: Jose Cintra (jose.cintra@html-apps.info)

#include <iostream>
#include <stdlib.h>
#include <iomanip> // Formatted output
using namespace std;
int main(int argc, char *argv[])
  {
  int N;
  cout << "The Pascal's Triangle\n";
  cout << "Enter the number of lines: "; 
  cin >> N;
  int T[N][N];
  // generates Triangle using the Stifel's Relation
  for (int L = 0;(L<N);L++)
    for (int C = 0;(C <= L);C++)
      {
      if ((C == 0) || (L == C))
        T[L][C] = 1;
      else 
        T[L][C] = T[L-1][C] + T[L-1][C-1];  
      }
  // Print triangle 
  for (int L = 0;(L<N);L++)
    {
    for (int C = 0;(C<=L);C++)
       {
       cout << setw(6) << T[L][C];
       }
    cout << "\n";
    }
  return 0;
  }

关注点

1. 请注意，我们在这里忽略了 L < C 的元素。
2. 如果我们考虑到一行中从中间开始的元素是重复的，即 T (L, L - C) = T (L, C)，那么这个算法可以得到改进。

2) 递归算法

# Purpose: Printing the Pascal's Triangle recursively using the Stifel's Relation
# Parameter: The number of rows you want 
# Language: Python 2.X.X
# Author: Jose Cintra (jose.cintra@html-apps.info)

def triangulo(n,k):

    if (k == 0) or (k == n):
      retorno = 1
    else:
      retorno = triangulo(n-1, k-1) + triangulo(n-1, k)
    return retorno

print "The Pascal's Triangle"
num = int(raw_input('Enter the number of lines: '))
for n in range(0,num):
    for k in range(0,n+1):
        print triangulo(n, k),
    print
    

关注点

1. 这个递归版本不是最高效的；
2. “for”循环也可以通过递归实现，但出于性能考虑，我们更倾向于保留它，否则我们将有一个递归函数调用另一个函数。

3) 函数式算法

-- Purpose: Printing the Pascal's Triangle through the functional paradigm
-- Language: Haskell 

pascal :: Int -> [[Integer]]
triangulo = iterate (\row -> zipWith (+) ([0]++row) (row++[0])) [1]
pascal n = take n triangulo

看点

函数式语言主要基于递归列表处理。这个算法实际上是一个优雅的解决方案，但仍然存在性能问题。

4) 无需数组的替代解决方案

二项式系数 可以解释为从L个元素的集合中选择C个元素的方式的数量。 在组合解释中，给定L个元素，选择C个元素的方式为：

T(L,C) = L! / (C!(L - C)!

{ 
Purpose: Printing the Coefficients of The Newton' Binomial
Language: Pascal
Author: Jose Cintra (jose.cintra@html-apps.info)
}

var L, C, power, coef: integer;
begin
writeln('The Newtons''s Binomial');
write('Enter the power of the binomial: ');
readln(power);
coef := 1;
L := power;
writeln('Coefficients:');
write(coef);
for C := 1 to L do
  begin
  coef := (coef * (L - C + 1)) div C;
  write(coef:6);
  end;
writeln;

end.

看点

这个算法更有效，因为它不依赖于数组或事先的长处理。

结论

就是这样了！

上面算法给出的结果是针对最多六位数的数字格式化的。如果您需要更大的数字，请更改此设置。

一如既往，在我们用常规语言实现算法时需要考虑的一点是，*三角形元素*的值往往会迅速增长，导致结果溢出。解决方案是采用支持任意精度数字的库或语言。函数式语言在大多数情况下没有这种缺陷。

希望这有帮助。 欢迎提出问题和评论。

在此处下载源代码

再见..