首页 > 搜索 > 打印杨辉三角c语言队列算法,杨辉三角(Pascal Triangle)的几种C语言实现及其复杂度分析

打印杨辉三角c语言队列算法,杨辉三角(Pascal Triangle)的几种C语言实现及其复杂度分析

互联网 2020-10-22 22:36:04
在线算命,八字测算命理

 

说明 

     本文给出杨辉三角的几种C语言实现,并简要分析典型方法的复杂度。

     本文假定读者具备二项式定理、排列组合、求和等方面的数学知识。

 

 

一  基本概念

     杨辉三角,又称贾宪三角、帕斯卡三角,是二项式系数在三角形中的一种几何排列。此处引用维基百科上的一张动态图以直观说明(原文链接http://zh.wikipedia.org/wiki/杨辉三角):

     从上图可看出杨辉三角的几个显著特征:

     1. 每行数值左右对称,且均为正整数。

     2. 行数递增时,列数亦递增。

     3. 除斜边上的1外,其余数值均等于其肩部两数之和。

     杨辉三角与二项式定理有密切关系,即杨辉三角的第n行(n=0…MAX_ROW)对应二项式(a+b)n展开(Binomial Expansion)的系数集合。例如,第二行的数值1-2-1为幂指数为2的二项式(a+b)2展开形式a2 + 2ab + b2的系数,即

     应用组合公式可推导出杨辉三角的特征1和3,如下:

 

 

 

二  题目要求

     用C语言编程打印出MAX_ROW行杨辉三角数,如(MAX_ROW=5):

1

1    1

1    2    1

1    3    3    1

1    4    6    4    1

1    5   10   10    5    1

…… …… …… ……

     并分析程序所用的加法和乘法次数,比较其复杂度。

 

 

三  算法实现

     因整型数值输出位宽限制,本节实现中将杨辉三角行数限制为10。该限制并不影响算法实现的完整性和表达性。

3.1 基本算法

     直接利用特征3求解杨辉值,即第i行的第j个数等于第i-1行的第j-1个数与第j个数之和,用二维数组形式表达即为a[i][j] = a[i-1][j-1] + a[i-1][j]。

     算法实现如下:

1 void BasicYangHui(void) 2 { 3 int dwRow = 0, dwCol = 0, aTriVal[MAX_ROW][MAX_COL] = {{0}}; 4 5 for(dwRow = 0; dwRow < MAX_ROW; dwRow++) 6 { 7 aTriVal[dwRow][0] = aTriVal[dwRow][dwRow] = 1;//若为i行0或i列,则i行j列杨辉值为1 8 } 9 10 for(dwRow = 2; dwRow < MAX_ROW; dwRow++)11 {12 for(dwCol = 1; dwCol < dwRow; dwCol++) //否则,i行j列杨辉值为i-1行中第j-1列与第j列值之和13 aTriVal[dwRow][dwCol] = aTriVal[dwRow-1][dwCol-1] + aTriVal[dwRow-1][dwCol];14 }15 16 //输出杨辉三角值17 for(dwRow = 0; dwRow < MAX_ROW; dwRow++)18 {19 for(dwCol = 0; dwCol = 1; dwCol--)11 {12 aTriVal[dwCol] = aTriVal[dwCol] + aTriVal[dwCol-1];13 }14 aTriVal[0] = 1; //首列置115 16 for(dwCol = 0; dwCol = 0; dwCol--)21 {22 printf("%5d", aTriVal[dwCol]); //反向输出aTriVal[dwCol],构成后半行杨辉值23 }24 printf("\n");25 }26 }

     以下给出另一种覆盖算法。该算法未使用折半处理,但使用临时变量暂存待覆盖的右肩值(即示意图中前行同列值),并从首列开始从左至右计算并覆盖。

1 void EfficientYangHui2(void) 2 { 3 int dwRow = 0, dwCol = 0, dwLeft = 0, dwRight = 0; 4 int aTriVal[MAX_ROW+1] = {1}; 5 6 for(dwRow = 0; dwRow < MAX_ROW; dwRow++) 7 { 8 dwLeft = 0; 9 for(dwCol = 0; dwCol
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多