杨辉三角算法集锦.docx

1、杨辉三角算法集锦杨辉三角算法集锦 /* Name: 杨辉三角算法集锦 分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法 */ #include #include using namespace std; const int MAXROW = 40; void PrintBlank(int n); int Com(int n, int m); int Try(int row, int cel); void Fun_1(int row); void Fun_2(int row); void Fun_3(int row); void Fun_4(int row); v

2、oid Fun_5(int row); void Fun_6(int row); void Fun_7(int row); void Fun_8(int row); void Fun_9(int row); int main() int row; cin row; Fun_1(row); cout Fun_2(row); cout Fun_3(row); cout Fun_4(row); cout Fun_5(row); cout Fun_6(row); cout Fun_7(row); cout Fun_8(row); cout Fun_9(row); system( return 0; /

3、输出n个空格 void PrintBlank(int n) for (int i=0; i cout /使用二维数组输出杨辉三角 void Fun_1(int row) const int DIS = 6; int blank = 32; int aMAXROWMAXROW = 0; for (int i=0; i PrintBlank(blank-=DIS/2);/输出第i行空格 for (int j=0; j if (j = 0 | j = i) aij = 1; else /规律: 左上与正上元素之和 aij = ai-1j-1 + ai-1j; cout if (j = i) cout

4、 /使用队列输出杨辉三角 void Fun_2(int row) const int DIS = 6; int max = row + 2; int blank = 30; int *a = new intmax; int front, rear; front = 0; a0 = 1; rear = 1; a1 = 1; PrintBlank(blank);/输出第一行空格 while (front != (rear+1)%max) if (afront = 1 & a(front+1)%max = 1)/到i-1行尾部 rear = (rear+1)%max; arear = 1; /第i行

5、尾部 rear = (rear+1)%max; arear = 1; /队尾进入第i+1行 cout front = (front+1)%max; /对头进入第i行 PrintBlank(blank-=DIS/2);/输出第i行空格 /处理中间数据 rear = (rear+1)%max; arear = afront + a(front+1)%max; if (front != rear)/队列非空时输出 cout front = (front+1)%max; /删除对头元素 delete a; /使用两个一维数组代替二维数组输出杨辉三角 void Fun_3(int row) const

6、int DIS = 6; int blank = 33; int *a = new introw; /存储下一行 int *b = new introw;/存储输出行 b0 = 1; for (int n=1; n /输出第n行 PrintBlank(blank-=DIS/2); cout cout if (n = row)/已经到最后一行则不再复制 continue; /生成第n+1行数据 a0 = b0; for (int i=1; i ai = bi + bi-1; an = 1; /复制第n+1行数据 for (int i=0; i bi = ai; delete a; delete

7、b; /使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：很巧妙 void Fun_4(int row) const int DIS = 6; int blank = 30; int *a = new introw; /存储输出行 int left, right; /输出第一行 PrintBlank(blank);/输出第1行空格 cout a0 = 1;/左侧数据永远为1 for (int n=1; n left = a0; /生成第n行数据 for (int i=1; i right = ai; ai = left + right;/left=ai-1，right=ai left =

8、 right; an = 1;/设置右侧的数据1 /输出第n行 PrintBlank(blank-=DIS/2); cout cout delete a; /使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：方法同Fun_4，但更具有技巧，有点难懂 void Fun_5(int row) const int DIS = 6; int blank = 33; int *a = new introw; /存储输出行 for (int i=1; i a0 = 1; int left, right; for (int n=1; n left = 0; /生成第n行数据 for (int i=0;

9、 i right = ai; ai = left + right;/left=ai-1，right=ai left = right; /输出第n行 PrintBlank(blank-=DIS/2); for (int i=0; i cout cout delete a; /使用一个一维数组输出杨辉三角；两侧的1不变，计算中间的元素 void Fun_6(int row) const int DIS = 6; int blank = 30; int *a = new introw; /输出第一行 PrintBlank(blank);/输出第1行空格 cout a0 = 1;/最左侧为1，永远不变

10、 for (int n=1; n an = 1; /设置最右侧的1 for (int i=n-1; i0; i-)/设置中间的元素，由于ai的值变化，故应从右到左计算 ai += ai-1; /杨辉三角的规律 /输出第n+1行 PrintBlank(blank-=DIS/2); for (int i=0; i cout cout delete a; /使用二项式定理输出杨辉三角 void Fun_7(int row) const int DIS = 6; int blank = 30; /输出第一行 PrintBlank(blank);/输出第1行空格 cout for (int i=1; i

11、 PrintBlank(blank-=DIS/2);/输出第i行空格 for (int j=0; j cout cout /输出组合c(n,m) int Com(int n, int m) int s1 = 1; int s2 = 1; m = (m n/2) ? (n - m) : m;/取小的，以减少计算量 for (int i=1; i s1 *= n; s2 *= i; if (s1 % s2 = 0)/防止溢出 s1 /= s2; s2 = 1; n-; return s1; /使用组合公式推论输出杨辉三角 :C(n,m) = (n-m+1)/m * C(n,m-1) void Fu

12、n_8(int row) const int DIS = 6; int blank = 30; /输出第一行 PrintBlank(blank);/输出第1行空格 cout for (int n=1; n int c = 1; PrintBlank(blank-=DIS/2);/输出第i行空格 cout for (int m=1; m c = c * (n - m + 1) / m; cout cout /使用递归方法输出杨辉三角 :C(n,k) = 1 (k=0或者n=k);C(n,k) = C(n-1,k-1) + C(n-1,k) void Fun_9(int row) const int DIS = 6; int blank = 33; for (int n=0; n PrintBlank(blank-=DIS/2);/输出第i行空格 for (int m=0; m cout cout /递归函数，输出杨辉三角 :C(n,k) = 1 (k=0或者n=k);C(n,k) = C(n-1,k-1) + C(n-1,k) int Try(int n, int k) if (k = 0 | k = n)/在左右两侧返回1 return 1; return Try(n-1,k-1) + Try(n-1,k);/递推公式