ACM解题之快速输出杨辉三角形（前68行）

题意：

本题要求计算并输出杨辉三角形的前 68 行.

Time Limit:1000MS

Memory Limit:65536K

解题：

为了能在规定时间准确输出杨辉三角形的前68行，这里我用了精准的大数相加技巧。（下篇文章，会有大数相加大数相乘的介绍。）因为杨辉三角形每一行（除了第一行）都和上一行有着不一般的联系，某一行的第k个数等于上一行的第k-1个数加上一行的第k个数（k不等于1且k小于该行行数，此行的最后新增的数为1）；所以我用了一个数组来存放某一行的数。因为杨辉三角形的对称性，我这里采取的处理方式是，数组只记住杨辉三角形的左边的数，然后在输出的时候重复输出数组。

具体看代码吧：

c++/accepted/480k/0ms

#include<iostream>

using namespace std;

#include<vector>

const int L = 15, D = 8, M = 100000000;

void out(vector<int*> &v) {   //打印函数

	for (int j = 0;j < v.size();j++)

	{

		int i = L - 1;

		while (v[j][i] == 0) i--;

		cout << v[j][i];

		while (--i >= 0) printf("%0*d", D, v[j][i]);

		cout << " ";

	}

}

void add(int p[], int q[], int r[]) {  //高精度大数相加函数

	int f = 0;

	for (int i = 0; i<L; i++) r[i] = p[i] + q[i];

	for (int i = 0; i<L; i++) { f += r[i]; r[i] = f%M; f /= M; }

}

void  pas(vector<int *> &vec1) {

	vector<int *> vec2;   //用于复制vec1数组的内容

	for (int i = 0;i < vec1.size();i++)

	{

		vec2.push_back(new int[L]);

		for (int u = 0;u < L;u++)

			vec2[i][u] = vec1[i][u];

	}

	for (int i = 1;i < vec2.size();i++)

		add(vec2[i - 1], vec2[i], vec1[i]);  //这里把相加后的结果放在vec1数组，这样就将vec1数组所记录的第k行数更新为第k+1行了！

}

int main() {

	cout << 1 << endl;  //第一行直接输出

	cout << 1 << " " << 1 << endl;  //第二行直接输出

	vector < int * > vec1;

	int a[L], b[L];

	a[0] = b[0]= 1;

	for (int j = 1; j<L; j++) a[j] = b[j] = 0;

	vec1.push_back(a);

	vec1.push_back(b);

	for (int i = 3; i < 69;i++) {

		int* t = new(int[L]);

		t[0] = 1;

		for (int j = 1; j<L; j++)   t[j] = 0;

		pas(vec1);

		vec1.push_back(t);

		out(vec1);

		cout << endl;

	}

	return 0;

}