杨辉三角的在编程中实现
杨辉三角在编程实现中较为容易。最常见的算法便是用上一行递推计算；也有运用和组合的对应关系而使用阶乘计算的，然而后者速度较慢且阶乘容易溢出。编程的输出大多相类，此处并不过多添加截图。
C、C++、C#、Java 语言之间的语法也大多相类，因此这里也不会将每一种算法都在这些语言中各实现一遍。要在这些语言的版本间修改，实际上只需注意一些简单的语法和函数名称的改变，如 C 的 int yh[M][M] 应改写为 Java 的 int[][] yh = new int[M][M]、C# 的 int[,] yh=new int[M,M]；C printf 应使用 Java 的 System.out.print、C# 的 Console.Write 、C++ 中更智能的 cout 来替换。 以下的代码均用标准 C 语言写成，可以被包括 MSVC（含 VC6）、GCC 的多种 C 编译器编译。
这个算法使用只行列位置和左侧的数值算出数值： /* yh-rt1.c - 时间和空间最优算法 */#include <stdio.h>#include <stdlib.h>int main(){ int s = 1, h; // 数值和高度 int i, j; // 循环计数 scanf(%d, &h); // 输入层数 printf(1\n); // 输出第一个 1 for (i = 2; i <= h; s = 1, i++) // 行数 i 从 2 到层高 { printf(1 ); // 第一个 1 for (j = 1; j <= i - 2; j++) // 列位置 j 绕过第一个直接开始循环 //printf(%d , (s = (i - j) / j * s)); printf(%d , (s = (i - j) * s / j)); printf(1\n); // 最后一个 1，换行 } getchar(); // 暂停等待 return 0;}
默认求直角三角形，可通过注释的开关或使用编译器的 -D 定义开关调节等腰三角形和菱形输出。如果觉得复杂，可按照 define 使用的情况剔除因不符合 ifdef 条件从而未启用的代码之后阅读。
这个算法创建了一个二维数组，并且通过上一行的数值求当前行。在反过来再次打印时，这个程序会使用以前算好的值，从而节省了重复迭代的时间。 /* yh-2d.c - 二维数组迭代 */#include<stdio.h>#define M 10 // 行数// #define PYRAMID // 金字塔，会额外填充空格// #define REVERSE // 反向再来一次，得到菱形int main(void){ int a [M][M], i, j; // 二维数组和循环变量，a[行][列] for (i = 0; i<M; i++) // 每一行 {#ifdef PYRAMID for (j = 0;j <= M-i; j++) printf ( );#endif // 填充结束 for (j = 0; j <= i; j++) // 赋值打印 printf(%4d, (a[i][j] = (i == j || j == 0) ? 1 : // 首尾置 1 a[i - 1][j] + a[i - 1][j - 1] )); // 使用上一行计算 printf(\n); }#ifdef REVERSE for(i = M-2; i >= 0; i--) {#ifdef PYRAMID for (j = 0;j <= M - i; j++) printf( );#endif // 填充结束 for (j = 0;j <= i; j++) printf(%4d,a[i][j]); // 直接使用以前求得的值 printf(\n); }#endif // 菱形结束 getchar(); // 暂停等待}这一个使用大数组写成，风格更接近教科书上的 VC6 代码。 /* yh-rt3.c - 较为暴力的大数组 */#include <stdio.h>#include string.hint main(){ int a[10000]; //容器，由n*(n+1)/2<=10000可知，n<=141 int b,CR,i; //b为当前行数，CR为要求显示的行数，i为循环数 printf(请输入要显示的行数（3~141）：); scanf(%d,&CR); YHSJ(CR); a[1]=a[2]=1; //前两行数值少且全为1，故直接输出 printf(%d\n,a[1]); printf(%d %d\n,a[1],a[2]); for(b=3;b<=CR;b++) //从第三行开始判断 { for(i=b;i>=2;i--) //从倒数第一个数开始加 a[i]=a[i]+a[i-1]; //杨辉三角的规律，没有值的数组默认为0 for(i=1;i<=b;i++) //显示循环 printf(%d ,a[i]); printf(\n); // 换行 } return 0;}这个版本使用队列的方式输出。 #include <stdio.h>#include <stdlib.h>#define EMPTY 1#define OFLOW 2#define INVAL 3#define MAX_Q 100typedef int DataType; // 数据类型选择typedef struct{ DataType elem[MAX_Q]; int front, rear; } LinkQ;// 队列及检查宏#define InitQ(Q) LinkQ Q; Q.front=Q.rear=-1;#define _EQ(Q,e) Q.elem[(Q.rear=(Q.rear+1)%MAX_Q)]=e#define EnQ(Q,e) if((Q.rear+1)%MAX_Q==Q.front) Exit(OFLOW,Overflow); _EQ(Q,e)#define DeQ(Q,e) e=Q.elem[(Q.front=(Q.front+1)%MAX_Q)]#define Front(Q) Q.elem[(Q.front+1)%MAX_Q]// 退出int Exit(int err, char msg[]) { puts(msg); exit(err); return err; }int main(void){ int n=1,i,j,k,t; InitQ(Q); printf(please enter a number:); scanf(%d,&n); if (n<=0) { printf(ERROR!\n); exit(INVAL); } for(i=0;i<n;i++) printf( ); puts(1); EnQ(Q,1); EnQ(Q,1); for(i=1;i<n;i++) { for(k=0;k<n-i;k++) printf( ); EnQ(Q,1); for(j=0;j<i;j++){ DeQ(Q,t); printf(%3d ,t); EnQ(Q,t+Front(Q)); } EnQ(Q,1); DeQ(Q,t); printf(%d\n,t); } return 0;} 来自易语言自带的例子。
以下为全文。 .版本 2.程序集 启动窗口程序集 .程序集变量 帕斯卡三角阶数, 整数型, , , 帕斯卡三角行数 .程序集变量 帕斯卡三角, 文本型, , , 形成的帕斯卡三角.子程序 __启动窗口_创建完毕' 使用算法：递归调用 ' 问题：求帕斯卡（杨辉）三角 ' 问题描述：取N阶的帕斯卡（杨辉）三角并显示 ' 问题分析： ' 运用递归的方法取N层帕斯卡三角，并显示。三角形边界上的数都是1，内部的每个数是位于它上面的两个数之和。 ' 假设f(row, col)表示杨辉三角的第row行的第col个元素，那么：f(row, col) = 1 (col = 1 或者 row = col)，也就是递归的停止条件。f(row, col) = f(row - 1, col - 1) + f(row - 1, col)，也就是上一行的两个相邻元素的和。递归调用求解。 ' 备注：.子程序 _计算图形按钮_被单击 .局部变量 行数, 整数型, , , 帕斯卡三角行数 .局部变量 列数, 整数型, , , 帕斯卡三角列数 .局部变量 询问返回, 整数型, , , 信息框返回的结果编辑框2.内容 = “” 帕斯卡三角 = “” ' 判断输入的值 .判断开始 (编辑框1.内容 = “”) 信息框 (“输入错误!”, 0, ) ' 当数值过大时，给出提示 .判断 (到数值 (编辑框1.内容) > 20) 询问返回 = 信息框 (“您输入的数值过大，处理数据时程序将会有一段时间无响应，是否继续？”, #是否钮 + #询问图标, “请问：”) .如果真 (询问返回 = #是钮) ' 如果确定，调用求帕斯卡三角 求帕斯卡三角 () .如果真结束 ' 数据较小时调用求帕斯卡三角 .判断 (编辑框1.内容 ≠ “” 且 到数值 (编辑框1.内容) ≤ 20) 求帕斯卡三角 () .默认.判断结束 .子程序 求帕斯卡三角 .局部变量 行数, 整数型, , , 帕斯卡三角行数 .局部变量 列数, 整数型, , , 帕斯卡三角列数' 要求的帕斯卡三角的总行数 帕斯卡三角阶数 = 到数值 (编辑框1.内容) － 1 .变量循环首 (0, 帕斯卡三角阶数, 1, 行数) .变量循环首 (0, 行数, 1, 列数) ' 取帕斯卡三角元素放到当前行里 帕斯卡三角 = 帕斯卡三角 + 到文本 (取帕斯卡三角元素 (行数 + 1, 列数 + 1)) + “,” .变量循环尾 () 帕斯卡三角 = 取文本左边 (帕斯卡三角, 取文本长度 (帕斯卡三角) － 1) + #换行符 ' 没层需去尾都好加换行符 .变量循环尾 () ' 显示结果 编辑框2.内容 = 帕斯卡三角 .子程序 取帕斯卡三角元素, 整数型, , 取帕斯卡三角中元素的子程序 .参数 行数, 整数型, , 帕斯卡三角行数 .参数 列数, 整数型, , 帕斯卡三角列数.如果 (列数 = 1 或 行数 = 列数) ' 每行的外围两个元素为1 返回 (1) .否则 ' 其余的部分为上一行的(行数 - 1)和(行数)元素之和 返回 (取帕斯卡三角元素 (行数 － 1, 列数 － 1) + 取帕斯卡三角元素 (行数 － 1, 列数)) .如果结束 # -*- coding: utf-8 -*-#!/usr/bin/env pythondef pas_triangles(): a = [1] while True: yield a a = [sum(i) for i in zip([0] + a, a + [0])]if __name__ == __main__: g = pas_triangles() for n in range(10): print(next(g))
