/*
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);//遞推公式
}