首页 > 代码库 > UVa 485 - Pascal's Triangle of Death

UVa 485 - Pascal's Triangle of Death

題目:打印Pascal三角到第一个到达10^60的行。

分析:字符串、大整數、模擬。f(i,j)= f(i-1,j-1)+ f(i-1,j) {組合數公式}。

說明:注意不小于10^60的數字有61位(⊙_⊙)。

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int P[220][220][70] = {0};

int main()
{
	for (int i = 0 ; i < 210 ; ++ i)
		P[i][0][0] = P[i][i][0] = 1;
	printf("1\n");
	for (int i = 1 ; i < 210 ; ++ i) {
		int end = 0,max = 0;
		printf("1 ");
		for (int j = 1 ; j < i  ; ++ j) {
			for (int k = 0 ; k < 65 ; ++ k) {
				P[i][j][k] += P[i-1][j][k]+P[i-1][j-1][k];
				if ( P[i][j][k] > 9 ) {
					P[i][j][k+1] += P[i][j][k]/10;
					P[i][j][k] %= 10;
				} 
			}
			end = 64;
			while (!P[i][j][end]) -- end;
			if (max < end) max = end;
			while (end >= 0) printf("%d",P[i][j][end --]);
			printf(" ");
		}
		printf("1\n");
		if (max >= 60) break;
	}
	return 0;
}

UVa 485 - Pascal's Triangle of Death