杨辉三角算法集锦 -- 业余空间-- 编程爱好者博客

/* Name: 杨辉三角算法集锦 Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处 Author: goal00001111 Date: 27-11-08 19:04 Description: 分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法算法思路详见代码注释——注释很详细，呵呵 */#include<iostream>#include<iomanip>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);void 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 << endl; Fun_2(row); cout << endl; Fun_3(row); cout << endl; Fun_4(row); cout << endl; Fun_5(row); cout << endl; Fun_6(row); cout << endl; Fun_7(row); cout << endl; Fun_8(row); cout << endl; Fun_9(row); system("pause"); return 0;}//输出n个空格 void PrintBlank(int n){ for (int i=0; i<n; i++) cout << ' ';}//使用二维数组输出杨辉三角 void Fun_1(int row){ const int DIS = 6; int blank = 32; int a[MAXROW][MAXROW] = {0}; for (int i=0; i<row; i++) { PrintBlank(blank-=DIS/2);//输出第i行空格 for (int j=0; j<=i; j++) { if (j == 0 || j == i) a[i][j] = 1; else //规律: 左上与正上元素之和 a[i][j] = a[i-1][j-1] + a[i-1][j]; cout << setw(DIS) << a[i][j]; if (j == i) cout << endl; } } }//使用队列输出杨辉三角 void Fun_2(int row){ const int DIS = 6; int max = row + 2; int blank = 30; int *a = new int[max]; int front, rear; front = 0; a[0] = 1; rear = 1; a[1] = 1; PrintBlank(blank);//输出第一行空格 while (front != (rear+1)%max) { if (a[front] == 1 && a[(front+1)%max] == 1)//到i-1行尾部 { rear = (rear+1)%max; a[rear] = 1; //第i行尾部 rear = (rear+1)%max; a[rear] = 1; //队尾进入第i+1行 cout << setw(DIS) << 1 << endl; //输出第i-1行尾部 front = (front+1)%max; //对头进入第i行 PrintBlank(blank-=DIS/2);//输出第i行空格 } //处理中间数据 rear = (rear+1)%max; a[rear] = a[front] + a[(front+1)%max]; if (front != rear)//队列非空时输出 cout << setw(DIS) << a[front]; //输出对头 front = (front+1)%max; //删除对头元素 } delete []a;}//使用两个一维数组代替二维数组输出杨辉三角void Fun_3(int row){ const int DIS = 6; int blank = 33; int *a = new int[row]; //存储下一行 int *b = new int[row];//存储输出行 b[0] = 1; for (int n=1; n<=row; n++) { //输出第n行 PrintBlank(blank-=DIS/2); for (int i=0; i<n; i++) cout << setw(DIS) << b[i]; cout << endl; if (n == row)//已经到最后一行则不再复制 continue; //生成第n+1行数据 a[0] = b[0]; for (int i=1; i<n; i++) a[i] = b[i] + b[i-1]; a[n] = 1; //复制第n+1行数据 for (int i=0; i<=n; i++) b[i] = a[i]; } delete []a; delete []b;}//使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：很巧妙 void Fun_4(int row){ const int DIS = 6; int blank = 30; int *a = new int[row]; //存储输出行 int left, right; //输出第一行 PrintBlank(blank);//输出第1行空格 cout << setw(DIS) << 1 << endl; a[0] = 1;//左侧数据永远为1 for (int n=1; n<row; n++) { left = a[0]; //生成第n行数据 for (int i=1; i<n; i++)//设置中间数据 { right = a[i]; a[i] = left + right;//left=a[i-1]，right=a[i] left = right; } a[n] = 1;//设置右侧的数据1 //输出第n行 PrintBlank(blank-=DIS/2); for (int i=0; i<=n; i++) cout << setw(DIS) << a[i]; cout << endl; } delete []a;}//使用一个一维数组和两个临时变量代替二维数组输出杨辉三角：方法同Fun_4，但更具有技巧，有点难懂 void Fun_5(int row){ const int DIS = 6; int blank = 33; int *a = new int[row]; //存储输出行 for (int i=1; i<row; i++)//赋初值0，这个很重要，因为后面有用到 a[i] = 0; a[0] = 1; int left, right; for (int n=1; n<=row; n++) { left = 0; //生成第n行数据 for (int i=0; i<n; i++) { right = a[i]; a[i] = left + right;//left=a[i-1]，right=a[i] left = right; } //输出第n行 PrintBlank(blank-=DIS/2); for (int i=0; i<n; i++) cout << setw(DIS) << a[i]; cout << endl; } delete []a;}//使用一个一维数组输出杨辉三角；两侧的1不变，计算中间的元素 void Fun_6(int row){ const int DIS = 6; int blank = 30; int *a = new int[row]; //输出第一行 PrintBlank(blank);//输出第1行空格 cout << setw(DIS) << 1 << endl; a[0] = 1;//最左侧为1，永远不变 for (int n=1; n<row; n++) { a[n] = 1; //设置最右侧的1 for (int i=n-1; i>0; i--)//设置中间的元素，由于a[i]的值变化，故应从右到左计算 { a[i] += a[i-1]; //杨辉三角的规律 } //输出第n+1行 PrintBlank(blank-=DIS/2); for (int i=0; i<=n; i++) cout << setw(DIS) << a[i]; cout << endl; } delete []a;}//使用二项式定理输出杨辉三角 void Fun_7(int row){ const int DIS = 6; int blank = 30; //输出第一行 PrintBlank(blank);//输出第1行空格 cout << setw(DIS) << 1 << endl; for (int i=1; i<row; i++) { PrintBlank(blank-=DIS/2);//输出第i行空格 for (int j=0; j<i; j++) { cout << setw(DIS) << Com(i, j); } cout << setw(DIS) << 1 << endl;//输出每行最后一个1 } }//输出组合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<=m; 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 Fun_8(int row){ const int DIS = 6; int blank = 30; //输出第一行 PrintBlank(blank);//输出第1行空格 cout << setw(DIS) << 1 << endl; for (int n=1; n<row; n++) { int c = 1; PrintBlank(blank-=DIS/2);//输出第i行空格 cout << setw(DIS) << c; //输出每行第一个1 for (int m=1; m<n; m++)//输出中间元素 { c = c * (n - m + 1) / m; cout << setw(DIS) << c; } cout << setw(DIS) << 1 << endl;//输出每行最后一个1 } }//使用递归方法输出杨辉三角 :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<row; n++) { PrintBlank(blank-=DIS/2);//输出第i行空格 for (int m=0; m<=n; m++)//输出中间元素 { cout << setw(DIS) << Try(n, m); } cout << endl;//输出每行最后一个1 } }//递归函数，输出杨辉三角 :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);//递推公式 }

博客介绍

正文

杨辉三角算法集锦2008-11-27 19:18:00

评论