《C程序设计》（夏宝岚）
习题6.5 编写程序，打印杨辉三角形（即二项式系数表）
在网上搜了一下关于杨辉三角的介绍，才知道原来这个数学三角并不是杨辉提出的，而是由一个叫做贾宪的人提出，大约在1050年他使用这个三角进行高次开方运算。南宋数学家杨辉在《详解九章算法》(1961年)记载并保存了“贾宪三角”，故称杨辉三角。杨辉在书中很确凿地载明：此图“出释锁算书，贾宪用此术”，所以后来都改称“贾宪三角”了。他所说的图叫做"开方作法本源图", 关于其详细介绍，见 贾宪三角一文。
杨辉三角的形式如下：
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之外，其余每个位置上数值都等于其两个肩上的元素之和。
可能是因为这种金字塔状的输出不太容易用程序输出，看到一些书上都直接绐的是如下形式：
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行)。思路：先将两侧元素，即每一行的开始值与结束值均置为1，然后从第三行开始(一、二行全为1), 除首尾两个元素外的其他元素为其左上角元素与正上方元素之和。
#include <stdio.h>
#define N 10 /* 维数 */
int main()
{
int i;
int j;
int a[N][N]; /* 定义存放杨辉三角的二维数组 */
for (i = 0; i < N; i++)
{
a[i][0] = 1; /* 每行开始值为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
===============================================================
那么怎样才能显示成金字塔形状呢？问题在于如何将每行前的空格数与行号结合起来，这样就可以在循环输出各行时方便地输出空格数了，观察前面所绐的金字塔形状的规律：
第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
按上述规律编写程序，限于屏幕显示宽度，1个数用6位宽度最多只能输出13行，再多的话看上去就不爽了：
#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
===============================================================================
★ 关于每一行前面的输出的空格还有一种方法。在 [016] printf格式控制符的完整格式 一文中(第一个拾遗处)提到了一种printf的输出方式，例如定义了一个字符串ch[20]，若想以宽度为6输出,一般会用printf("%6s", ch); 输出,这种方法可认为是静态的,即这个宽度不能变,有一种形式可以实现动态输出: printf("%*s\n", m, ch); 这里由m的值代替*位置, 即宽度*可以由变量m来确定。用上述方法可以将上面程序中的
for (j = 0; j < (N * 3 - 3 * i); j++)
printf(" ");
换成: printf("%*c", 3 * N - 3 * i, ' ');
即在每行前以c格式输出 3*N-3*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
===============================================================================
★ 分析: 其思路是用一维数组做,实际上用的是两个一维数组a[], b[].其中a[]是保存当前行各元素的值, 而b[]可以认为是一个临时数组, 它是a[]的一个备份, 也就是说在每行a[]元素置数完毕后,将a[]中的内容拷贝到b[]中,因为进行下一行的运算时, a[]会被重置, 而且由杨辉三角的规律知下一行要用到上一行的元素, 这样在计算下一行的a[]时就可以用保存在b[]中的上一行的元素了(咋感觉这么啰嗦呢^_^)。也正因为如此, 在每一行运算完之后,就要将其输出显示, 下一行时a[]就是新值了。所以用这种方法最后程序结束时并没有将三角中所有元素保存下来，只是在程序运行过程中将其输出。
再看其程序的核心部分： a[j] = b[j] + b[j-1]; 其开始定义了数组a[80],b[80]，0号元素并未使用，即每一行的元素都是从a[1]开始的。但这个0号元素是不是真的没用呢？稍加分析可知当然否，而且感觉这个0号元素用的挺巧妙，比如说到第5行时(其实与第几行没关系)，输出第一个元素的语句是 a[1]=b[1]+b[0], 由于b[1]为1, 这时0号元素就派上用场了,b[0]为0, 可以将每一行的第一个元素置为1, 往下走有第二个元素 a[2]=b[2]+b[1]; ...开始按杨辉三角的规律走。同理，到最后一个元素时，a[5]=b[5]+b[4]，在上一行中只有4个元素，即此时b[]中只有4个有效元素，那这个b[5]算什么呢？其实它跟那个0号元素有相同的作用，因为初始化时数组中的所有元素都置为0，所以这时的b[5]为0，由b[4]为1可得a[5]为1。这样可以将每一行的最后一个元素置为1。对于各行，此法均适用，实际上就是在满足杨辉三角两侧值均为1的规律。
参考 [059] C语言中动态分配数组(一维) 一文, 将上述程序改写如下(金字塔型显示):
#include <stdio.h>
#include <stdlib.h>
void main()
{
int i, j;
int *a;
int *b;
int N;
do /* 限制一下输出的行数在0到13之间, 超过13时一行不足矣显示 */
{
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
===============================================================================
一维数组又一法:
在别人日志上看到一篇文章 (查看原文) , 是用一个一维数完成的, 其原程序有点小错误，稍加修改拿来分析一下吧：
#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
=======================================================================
★ 分析: 此程序是以杨辉三角的前两行为基础的,所以前两行的值已经确定, 后续行由三角的规律得到。程序中用一个一维数组a[] 记录生成的值，每一行都要刷新，数组的0 号元素作用与上一个程序(两个一维数组实现)中的作用类似, 叠加时生成第二个元素值,所以分配数组时要多分配一个元素，即a[N+1]。还有由于前两行已经提前输出，故用循环输出后续值时要注意条件是 i < N - 1 , 且i = 1时输出的是第三行。按循环走上两行就能明白其原理了, 由i = 1 时开始， 此时应输出第三行的值：
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;
……
依次类推即可得到各行。 其巧妙之处在于a[i+1]=a[i]这句，将最外边的1外移了一位。
当然也可以用上个程序那样动态分配数组实现, 不再赘述。
二项式定理:
既然杨辉三角为二项式系数表,那能不能用二项式定理来编呢? 我没有思路, 看到一个帖 (查看原帖) 中有人用C++写了一个, 不过怎么也看不明白其原理, 用C稍加修改,程序先放到这, 想明白了再补上:
#include <stdio.h>
void main()
{
double A, n, s, sum, m, X;
double t;
s = 1;
sum = 1;
/* 输入显示行数, 为方便显示, 在13以内为佳 */
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
=============================================================
递推公式法:
还是在这个帖中 (查看该帖) 还有一种方法, 不知应该叫什么, 自己分析了一下, 算是看懂了,就先叫它"递推公式法吧" , 稍加改动, 拿过来分析一下:
#include "stdio.h"
void main()
{
int c; /* 每行的元素值(循环中生成), 初值为1 */
int n; /* 显示的行数 */
int i, j; /* 循环控制 */
/* 输入行数,显示13行以内为佳 */
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; /* 每行开始输出前都将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
=======================================================================
★ 分析: 此方法每个元素都是在循环中由控制变量i, j 及公式 c=c*(i-j)/(j+1); 生成的, c即元素的值, 每行输出前都将c的值置1, 这样解决了将每行第一个值置1的问题, 接着由递推公式及行值i、列值j 依次得出后面的元素。过程嘛说出来反而啰嗦，其实按循环走上那么三四行就能明白其含义了。比如生成第四行时，i 为3，走一遍:
j = 0 时: 输出 c = 1 --> 递推 c = 1 * (3 - 0) / (0 + 1) = 3
j = 1 时: 输出 c = 3 --> 递推 c = 3 * (3 - 1) / (1 + 1) = 3
j = 2 时: 输出 c = 3 --> 递推 c = 3 * (3 - 2) / (2 + 1) = 1
j = 3 时: 输出 c = 1 --> 结束
不知这个规律是发帖这位仁兄总结出来的, 还是它本身就是二项式系数的一种内在形式。总之感觉很牛×。
另外此程序中每行前输出空格的方法和前面提到的也不太一样，它是用位宽控制输出一个空格做到的，当然和前面的方法通用。即可以将
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, ' ');
递规法:
又在一个帖中 (查看该帖) 看到一种方法, 作者说是用递规法, 我没能理解是什么意思, 因为还不太懂指针的用法, 所以对程序中为每个元素赋值的语句还看不懂。但是总觉得叫"递规法"好像不太恰当。这个程序也是用一个二维数级存储杨辉三角的，再看一下程序的结构, 我想其原理应该和上面提到的"二维数组"实现的方法是相同的, 只是在对每个元素赋值以及在数组中取值输出时没有用数组下标的形式, 而是用的指针的方式直接存取。修改了一下，还是先放到这，弄懂了再补上(为便于显示, 只输出了13行)：
#include<stdio.h>
#define N 13
void main()
{
int i,j,k;
int a[N][N]; /* 存储杨辉三角 */
for(i = 0; i < N; i++)
{
**(a + i) = 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(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里(查看原文)又看到一个用函数递规的方法实现的,很不错,再拿来分析。为了便于分析，首先自己写了一个，其元素生成方法见"递推公式法", 有了这个程序的基础,再来分析就比较容易懂了。
#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
===================================
有了上述那些方法的基础,这个程序不难理解, 就是判断一下如果是每一行的第一个元素或最后一个元素就输出1, 否则其他元素用杨辉三角的规律生成。下面是人家的程序(有所改动)，用函数递规实现，与上面程序不同之处就在于生成元素的方法是用函数的递规调用。
#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
===============================================================================
★ 分析:没什么可说的了,有了前面的东西做铺垫。再提一下这个函数f()的功能吧: m表示行值, n表示列值, 此函数就是在求位置(m, n)的元素值, n==1表示是行的第一个元素, 将其置1,m == n 表示是行的最后一个元素, 也置为1。其他情况则值为(m-1, n-1)与(m-1, n) 位置上的元素之和, 即双肩上的两个元素之和。
★ 终于写完了。想这个问题一个多星期，自己的思路总是有限的，只会用二维数组做。在网上搜集了以上各种方法，忽然发现原来分析别人的代码也是一种乐趣，也可以学到许多东西。在此向各种方法的原创者表示感谢！
[补充] 2007.5.22
网友skylark1111111@163.com在提供的方法(见新BLog评论):
运行结果：
============================
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
============================
评论