習題6.5 編寫(xiě)程序，打印楊輝三角形（即二項式系數表）
在網(wǎng)上搜了一下關(guān)于楊輝三角的介紹，才知道原來(lái)這個(gè)數學(xué)三角并不是楊輝提出的，而是由一個(gè)叫做賈憲的人提出，大約在1050年他使用這個(gè)三角進(jìn)行高次開(kāi)方運算。南宋數學(xué)家楊輝在《詳解九章算法》(1961年)記載并保存了“賈憲三角”，故稱(chēng)楊輝三角。楊輝在書(shū)中很確鑿地載明：此圖“出釋鎖算書(shū)，賈憲用此術(shù)”，所以后來(lái)都改稱(chēng)“賈憲三角”了。他所說(shuō)的圖叫做"開(kāi)方作法本源圖", 關(guān)于其詳細介紹，見(jiàn) 賈憲三角一文。
楊輝三角的形式如下：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
......
規律：除兩側的元素均為1之外，其余每個(gè)位置上數值都等于其兩個(gè)肩上的元素之和。
可能是因為這種金字塔狀的輸出不太容易用程序輸出，看到一些書(shū)上都直接紿的是如下形式：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
規律：除兩側元素均為1之外，其余每個(gè)位置上的元素值為其左上角元素與正上方元素之和，這樣便于用數組實(shí)現。
for (i = 0; i < N; i++)
{
a[i][0] = 1; /* 每行開(kāi)始值為1 */
a[i][i] = 1; /* 每行結束值為1 */
}
for (i = 2; i < N; i++)
for (j = 1; j < i; j++)
a[i][j] = a[i-1][j-1] + a[i-1][j]; /* 規律: 左上與正上元素之和 */
for (i = 0; i < N; i++)
{
for (j = 0; j <= i; j++)
printf("%-5d", a[i][j]);
printf("\n");
}
return 0;
}
運行結果(VC):
===============================================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
===============================================================
那么怎樣才能顯示成金字塔形狀呢？問(wèn)題在于如何將每行前的空格數與行號結合起來(lái)，這樣就可以在循環(huán)輸出各行時(shí)方便地輸出空格數了，觀(guān)察前面所紿的金字塔形狀的規律：
第1行 i = 0 空格數 30 ＝3 × N－3 × 0
第2行 i = 1 空格數 27 ＝3 × N－3 × 1
第3行 i = 2 空格數 24 ＝3 × N－3 × 2
......
第N行 i = i 空格數 3×N－3×i
按上述規律編寫(xiě)程序，限于屏幕顯示寬度，1個(gè)數用6位寬度最多只能輸出13行，再多的話(huà)看上去就不爽了：
#include <stdio.h>
#define N 13
int main()
{
int i;
int j;
int a[N][N];
for (i = 0; i < N; i++)
{
a[i][0] = 1;
a[i][i] = 1;
}
for (i = 2; i < N; i++)
for (j = 1; j < i; j++)
a[i][j] = a[i-1][j-1] + a[i-1][j];
for (i = 0; i < N; i++)
{
for (j = 0; j < (N * 3 - 3 * i); j++)
printf(" ");
for (j = 0; j <= i; j++)
printf("%-6d", a[i][j]);
printf("\n");
}
return 0;
}
運行結果（VC）
===============================================================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
===============================================================================
★ 關(guān)于每一行前面的輸出的空格還有一種方法。在 [016] printf格式控制符的完整格式 一文中(第一個(gè)拾遺處)提到了一種printf的輸出方式，例如定義了一個(gè)字符串ch[20]，若想以寬度為6輸出,一般會(huì )用printf("%6s", ch); 輸出,這種方法可認為是靜態(tài)的,即這個(gè)寬度不能變,有一種形式可以實(shí)現動(dòng)態(tài)輸出: printf("%*s\n", m, ch); 這里由m的值代替*位置, 即寬度*可以由變量m來(lái)確定。用上述方法可以將上面程序中的
for (j = 0; j < (N * 3 - 3 * i); j++)
printf(" ");
換成: printf("%*c", 3 * N - 3 * i, ' ');
即在每行前以c格式輸出 3*N-3*i 個(gè) ' ' (空格), 可以得到相同的結果。
一維數組:
前兩天在網(wǎng)上看了一位仁兄用一維數組做的, 當時(shí)只保存其代碼,現在找不到原帖了, 那就先把人家的程序拿來(lái)分析一下吧(稍加修改):
#include <stdio.h>
void main()
{
int N = 13; /* 維數 */
int a[80] = {0};
int b[80] = {0};
int i, j;
b[1]=1;
for (i = 1; i <= N; i++)
{
for (j = 1; j <= i; j++)
a[j] = b[j] + b[j-1];
for (j = 1; j <= i; j++) /* copy當前行a[]到b[]中以備下行的所用 */
{
b[j] = a[j];
printf("%-6d", b[j]);
}
printf("\n");
}
}
運行結果(VC):
===============================================================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
===============================================================================
★ 分析: 其思路是用一維數組做,實(shí)際上用的是兩個(gè)一維數組a[], b[].其中a[]是保存當前行各元素的值, 而b[]可以認為是一個(gè)臨時(shí)數組, 它是a[]的一個(gè)備份, 也就是說(shuō)在每行a[]元素置數完畢后,將a[]中的內容拷貝到b[]中,因為進(jìn)行下一行的運算時(shí), a[]會(huì )被重置, 而且由楊輝三角的規律知下一行要用到上一行的元素, 這樣在計算下一行的a[]時(shí)就可以用保存在b[]中的上一行的元素了(咋感覺(jué)這么啰嗦呢^_^)。也正因為如此, 在每一行運算完之后,就要將其輸出顯示, 下一行時(shí)a[]就是新值了。所以用這種方法最后程序結束時(shí)并沒(méi)有將三角中所有元素保存下來(lái)，只是在程序運行過(guò)程中將其輸出。
再看其程序的核心部分： a[j] = b[j] + b[j-1]; 其開(kāi)始定義了數組a[80],b[80]，0號元素并未使用，即每一行的元素都是從a[1]開(kāi)始的。但這個(gè)0號元素是不是真的沒(méi)用呢？稍加分析可知當然否，而且感覺(jué)這個(gè)0號元素用的挺巧妙，比如說(shuō)到第5行時(shí)(其實(shí)與第幾行沒(méi)關(guān)系)，輸出第一個(gè)元素的語(yǔ)句是 a[1]=b[1]+b[0], 由于b[1]為1, 這時(shí)0號元素就派上用場(chǎng)了,b[0]為0, 可以將每一行的第一個(gè)元素置為1, 往下走有第二個(gè)元素 a[2]=b[2]+b[1]; ...開(kāi)始按楊輝三角的規律走。同理，到最后一個(gè)元素時(shí)，a[5]=b[5]+b[4]，在上一行中只有4個(gè)元素，即此時(shí)b[]中只有4個(gè)有效元素，那這個(gè)b[5]算什么呢？其實(shí)它跟那個(gè)0號元素有相同的作用，因為初始化時(shí)數組中的所有元素都置為0，所以這時(shí)的b[5]為0，由b[4]為1可得a[5]為1。這樣可以將每一行的最后一個(gè)元素置為1。對于各行，此法均適用，實(shí)際上就是在滿(mǎn)足楊輝三角兩側值均為1的規律。
參考 [059] C語(yǔ)言中動(dòng)態(tài)分配數組(一維) 一文, 將上述程序改寫(xiě)如下(金字塔型顯示):
#include <stdio.h>
#include <stdlib.h>
void main()
{
int i, j;
int *a;
int *b;
int N;
do /* 限制一下輸出的行數在0到13之間, 超過(guò)13時(shí)一行不足矣顯示 */
{
printf("How many lines do you want to print? ");
scanf("%d", &N);
}while(N < 0 || N > 13);
printf("\n");
a = (int *) malloc((N + 1) * sizeof(int));
b = (int *) malloc((N + 1) * sizeof(int));
for (i = 0; i <= N; i++)
{
a[i] = 0;
b[i] = 0;
}
b[1]=1;
for (i = 1; i <= N; i++)
{
for (j = 1; j <= i; j++)
a[j] = b[j] + b[j-1];
for (j = 1; j <= (3 * N - 3 * i); j++) /* 每行前加空格 */
printf(" ");
for (j = 1; j <= i; j++)
{
b[j] = a[j];
printf("%-6d", b[j]);
}
printf("\n");
}
}
運行結果(VC):
===============================================================================
How many lines do you want to print? 10↙
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
===============================================================================
一維數組又一法:
在別人日志上看到一篇文章 (查看原文) , 是用一個(gè)一維數完成的, 其原程序有點(diǎn)小錯誤，稍加修改拿來(lái)分析一下吧：
#include <stdio.h>
#define N 10 /* 顯示行數 */
void main()
{
int a[N+1];
int i,j;
a[0] = a[1] = 1; /* 第二行 */
/* 打印一二行 */
printf("%-5d\n",1);
printf("%-5d%-5d\n",a[0],a[1]);
for (i = 1; i < N - 1; i++)
{
a[i + 1] = a[i]; /* 最外邊的1外移一位 */
for (j = i; j > 0; j--)
a[j] = a[j - 1] + a[j]; /* 楊輝三角的規律 */
for (j = 0; j < i + 2; j++)
printf("%-5d", a[j]);
printf("\n");
}
}
運行結果:
=======================================================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
=======================================================================
★ 分析: 此程序是以楊輝三角的前兩行為基礎的,所以前兩行的值已經(jīng)確定, 后續行由三角的規律得到。程序中用一個(gè)一維數組a[] 記錄生成的值，每一行都要刷新，數組的0 號元素作用與上一個(gè)程序(兩個(gè)一維數組實(shí)現)中的作用類(lèi)似, 疊加時(shí)生成第二個(gè)元素值,所以分配數組時(shí)要多分配一個(gè)元素，即a[N+1]。還有由于前兩行已經(jīng)提前輸出，故用循環(huán)輸出后續值時(shí)要注意條件是 i < N - 1 , 且i = 1時(shí)輸出的是第三行。按循環(huán)走上兩行就能明白其原理了, 由i = 1 時(shí)開(kāi)始， 此時(shí)應輸出第三行的值：
i=1 a[0]=1
a[1]=1
a[2]=a[1]=1
j=i=1 a[1]=a[0]+a[1]=1+1=2 => j-- => j=0 => 結束
最終a[0]=1, a[1]=2, a[2] = 1;
--------------------------------------------------------------------
i=2 a[0]=1
a[1]=2
a[3]=a[2]=1
j=i=2 a[2]=a[1]+a[2]=1+2=3 => j-- => j=1 => 繼續
j = 1 a[1]=a[0]+a[1]=1+2=3 => j-- => j=0 => 結束
最終a[0]=1, a[1]=3, a[2] = 3, a[3]=1;
……
依次類(lèi)推即可得到各行。 其巧妙之處在于a[i+1]=a[i]這句，將最外邊的1外移了一位。
當然也可以用上個(gè)程序那樣動(dòng)態(tài)分配數組實(shí)現, 不再贅述。
/* 輸入顯示行數, 為方便顯示, 在13以?xún)葹榧?*/
do
{
printf("lines: ");
scanf("%lf", &X);
} while(X <= 0 || X > 13);
printf("%d\n", 1);
for(A = 1; A <= (X - 1); A++)
{
printf("%-6d", 1);
for(n = 1; n <= A; n++)
{
s *= n;
m = (A - n + 1);
sum *= m;
t = sum / s;
printf("%-6d", (int)t);
}
printf("\n");
}
}
運行結果(VC):
=============================================================
lines: 8↙
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
=============================================================
遞推公式法:
還是在這個(gè)帖中 (查看該帖) 還有一種方法, 不知應該叫什么, 自己分析了一下, 算是看懂了,就先叫它"遞推公式法吧" , 稍加改動(dòng), 拿過(guò)來(lái)分析一下:
#include "stdio.h"
void main()
{
int c; /* 每行的元素值(循環(huán)中生成), 初值為1 */
int n; /* 顯示的行數 */
int i, j; /* 循環(huán)控制 */
/* 輸入行數,顯示13行以?xún)葹榧?*/
do
{
printf("Input n=");
scanf("%d",&n);
} while(n <= 0 || n > 13);
for(i = 0; i < n; i++)
{
for(j = 0; j < n - i; j++) /* 輸入每行前的空格 */
printf("%3c", ' ');
c=1; /* 每行開(kāi)始輸出前都將c重置為1 */
for(j = 0; j <= i; j++)
{
printf("%-3d", c);
printf("%-3c", ' ');
c = c * (i - j) / (j + 1); /* 核心: 遞推公式 */
}
printf("\n");
}
}
運行結果(VC):
=======================================================================
Input n=10↙
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
=======================================================================
★ 分析: 此方法每個(gè)元素都是在循環(huán)中由控制變量i, j 及公式 c=c*(i-j)/(j+1); 生成的, c即元素的值, 每行輸出前都將c的值置1, 這樣解決了將每行第一個(gè)值置1的問(wèn)題, 接著(zhù)由遞推公式及行值i、列值j 依次得出后面的元素。過(guò)程嘛說(shuō)出來(lái)反而啰嗦，其實(shí)按循環(huán)走上那么三四行就能明白其含義了。比如生成第四行時(shí)，i 為3，走一遍:
j = 0 時(shí): 輸出 c = 1 --> 遞推 c = 1 * (3 - 0) / (0 + 1) = 3
j = 1 時(shí): 輸出 c = 3 --> 遞推 c = 3 * (3 - 1) / (1 + 1) = 3
j = 2 時(shí): 輸出 c = 3 --> 遞推 c = 3 * (3 - 2) / (2 + 1) = 1
j = 3 時(shí): 輸出 c = 1 --> 結束
不知這個(gè)規律是發(fā)帖這位仁兄總結出來(lái)的, 還是它本身就是二項式系數的一種內在形式?？傊杏X(jué)很?！?。
另外此程序中每行前輸出空格的方法和前面提到的也不太一樣，它是用位寬控制輸出一個(gè)空格做到的，當然和前面的方法通用。即可以將
for(j = 0; j < n - i; j++) for (j = 0; j < (n * 3 - 3 * i); j++)
printf("%3c", ' '); 改為==> printf(" ");
或 ==> printf("%*c", 3 * n - 3 * i, ' ');
for(i = 2; i < N; i++) /* 遞歸賦值法 */
for(j = 1; j < i; j++)
*(*(a + i) + j) = *(*(a + i - 1) + j - 1) + *(*(a + i -1 ) + j);
for(i = 0; i < N; i++)
{
for(k = 0; k < N - i; k++) /* 每行前的空格 */
printf("%-3c", ' ');
for(j = 0; j <= i; j++)
printf("%-6d", *(*(a + i) + j));
printf("\n");
}
}
運行結果(VC):
===============================================================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
===============================================================================
函數遞規:
在別人Blog里(查看原文)又看到一個(gè)用函數遞規的方法實(shí)現的,很不錯,再拿來(lái)分析。為了便于分析，首先自己寫(xiě)了一個(gè)，其元素生成方法見(jiàn)"遞推公式法", 有了這個(gè)程序的基礎,再來(lái)分析就比較容易懂了。
#include <stdio.h>
void main()
{
int n = 5; /* 輸出行數 */
int i, j;
int c = 1;
for (i = 0; i < n; i++)
{
printf("%-4d", c = 1);
for (j = 0; j < i; j++)
{
if (i == 1) /* 若為首元素則置為1 */
printf("%-4d", 1);
else
{
if (i == j) /* 若為尾元素則置為1 */
printf("%-4d", 1);
else
printf("%-4d", c = c * (i - j) / (j + 1)); /* 生成其他位置元素 */
}
}
printf("\n");
}
}
運行結果：
===================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
===================================
有了上述那些方法的基礎,這個(gè)程序不難理解, 就是判斷一下如果是每一行的第一個(gè)元素或最后一個(gè)元素就輸出1, 否則其他元素用楊輝三角的規律生成。下面是人家的程序(有所改動(dòng))，用函數遞規實(shí)現，與上面程序不同之處就在于生成元素的方法是用函數的遞規調用。
#include <stdio.h>
int f(int m, int n) /* 函數: 求在(m, n)位置的元素值 */
{
if (n == 1) /* 若為首元素則置1 */
return 1;
else
{
if (m == n) /* 若為尾元素則置1 */
return 1;
else
return f(m - 1, n - 1) + f(m - 1, n); /* 按規律生成其他元素 */
}
}
int main(void)
{
int n = 13; /* 行數 */
int i, j;
for (i = 1; i <= n; i++)
{
for(j = 0; j < n - i; j++) /* 每行前的空格 */
printf("%3c", ' ');
for (j = 1; j <= i; j++) /* 輸出各元素 */
printf("%-6d", f(i, j));
printf("\n");
}
return 0;
}
運行結果(VC):
===============================================================================
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
===============================================================================
★ 分析:沒(méi)什么可說(shuō)的了,有了前面的東西做鋪墊。再提一下這個(gè)函數f()的功能吧: m表示行值, n表示列值, 此函數就是在求位置(m, n)的元素值, n==1表示是行的第一個(gè)元素, 將其置1,m == n 表示是行的最后一個(gè)元素, 也置為1。其他情況則值為(m-1, n-1)與(m-1, n) 位置上的元素之和, 即雙肩上的兩個(gè)元素之和。
聯(lián)系客服
