新郑整站优化百度快照查询入口

常见算法-巴斯卡三角形（Pascal）

1、说明

巴斯卡（Pascal）三角形基本上就是在解 nCr，因为三角形上的每一个数字各对应一个nCr，其中 n 为 row，而 r 为 column，如下：

　　　　0C0

　　　1C0 1C1

　　2C0 2C1 2C2

　3C0 3C1 3C2 3C3

对应的数据如下图所示：

                 1

　　　 1       1

　　 1       2      1

　 1      3       3     1

巴斯卡三角形中的 nCr 可以使用以下这个公式来计算，以避免阶乘运算时的数值溢位：

        nCr = [(n-r+1)/r] * nCr-1

        nC0 = 1

2、C++代码

#include<iostream>
using namespace std;long Pascal(int n, int r) {long p = 1;for (int i = 1; i <= r; i++) {p = p * (n - i + 1) / i;}return p;
}void PrintPascal(int t) {int n, r;for (n = 0; n <= t; n++) {for (r = 0; r <= n; r++) {int i;if (r == 0) {for (i = 0; i <= (t - n); i++) {cout << "  ";}}else {cout << "  ";}cout << Pascal(n, r);}cout << endl;}
}int main() {PrintPascal(12);// n=0, r=0		"   ""   ""   ""   "" 1 "					||	"   ""   ""   ""   ""0c0"// n=1, r=0		"   ""   ""   "" 1 ""   "" 1 "				||	"   ""   ""   ""1c0""   ""1c1"//		r=1// n=2, r=0		"   ""   "" 1 ""   "" 2 ""   "" 1 "			||	"   ""   ""2c0""   ""2c1""   ""2c2"//		r=1//		r=2// n=3, r=0		"   "" 1 ""   "" 3 ""   "" 3 ""   "" 1 "	||	"   ""3c0""   ""3c1""   ""3c2""   ""3c3"//		r=1//		r=2//		r=3return 0;
}