如何不使用数组实现打印“杨辉三角形”?

一、杨辉三角形1.1 杨辉三角形的概念

杨辉三角,是二项式系数在三角形中的一种几何排列。在欧洲,这个表叫做帕斯卡三角形。帕斯卡(1623—-1662)是在1654年发现这一规律的,比杨辉要迟393年,比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一,它把二项式系数图形化,把组合数内在的一些代数性质直观地从图形中体现出来,是一种离散型的数与形的结合 。

我们先看一下杨辉三角形的打印结果:

如何不使用数组实现打印“杨辉三角形”?
1.2 杨辉三角形的性质

杨辉三角形有很多性质:

1). 每行端点与结尾的数为1.

2). 每个数等于它上方两数之和。

3). 每行数字左右对称,由1开始逐渐变大。

4). 第n行的数字有n项。

5). 前n行共[(1+n)n]/2 个数。

6).第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。

7). 第n行的第m个数和第n-m+1个数相等 ,为组合数性质之一。

8). 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和,这也是组合数的性质之一。即 C(n+1,i)=C(n,i)+C(n,i-1)。

9). (a+b)^n^的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。

10). 将第2n+1行第1个数,跟第2n+2行第3个数、第2n+3行第5个数……连成一线,这些数的和是第4n+1个斐波那契数;将第2n行第2个数(n>1),跟第2n-1行第4个数、第2n-2行第6个数……这些数之和是第4n-2个斐波那契数。

11). 将第n行的数字分别乘以10^(m-1)^,其中m为该数所在的列,再将各项相加的和为11^(n-1)^。 11^0^=1,

11^1^=1 * 10^0^ + 1 * 10^1^=11,

11^2^=1×10^0^+2×10^1^^+1×10^2^=121,

11^3^=1×10^0^+3×10^1^+3×10^2^+1×10^3^=1331,

11^4^=1×10^0^+4×10^1^10^2^+4×10^3+1×10^4=14641,

11^5^=1×10^0^+5×10^1^+10×10^2^+10×10^3^+5×10^4^+1×10^5^=161051。

12). 第n行数字的和为2^(n-1)^。1=2^(1-1)^,1+1=2^(2-1)^,1+2+1=2^(3-1)^,1+3+3+1=2^(4-1)^,1+4+6+4+1=2^(5-1)^,1+5+10+10+5+1=2^(6-1)^。

13). 斜线上数字的和等于其向左(从左上方到右下方的斜线)或向右拐弯(从右上方到左下方的斜线),拐角上的数字。1+1=2,1+1+1=3,1+1+1+1=4,1+2=3,1+2+3=6,1+2+3+4=10,1+3=4,1+3+6=10,1+4=5。

14). 将各行数字左对齐,其右上到左下对角线数字的和等于斐波那契数列的数字。1,1,1+1=2,2+1=3,1+3+1=5,3+4+1=8,1+6+5+1=13,4+10+6+1=21,1+10+15+7+1=34,5+20+21+8+1=55。

实现杨辉三角形的打印也有很多方式,今天我为大家介绍两种方式:

使用数组的方式:这也是网上比较常见的方式。需要使用数组,所以效率较低。不使用数组的方式:不需要使用数组,所以效率较高。二、使用数组的方式2.1 示意图

根据上面的性质,如果我们要打印一个11行的杨辉三角形,我们可以将整个排列看做是一个n行,0-n列的矩阵,再结合上面的性质8,我们将这个矩阵用一个二维数组来实现,如下图:

如何不使用数组实现打印“杨辉三角形”?
2.2 代码分步实现

2.2.1 根据示意图,我们先定义一个二维数组:

int n = 11;//要几行的数据 int[][] values = new int[n][];//定义n行,但暂时每行的列数先不定义

2.2.2 生成二维数组,根据杨辉三角形性质,n行的数字个数为n:

for(int i = 0;i < values.length ; i++){ values[i] = new int[i + 1];//行0有1列,行1有2列,….,行n有n+1列 }

2.2.3 填充二维数组:

for(int i = 0;i < values.length ; i++){ values[i] = new int[i + 1];//行0有1列,行1有2列,….,行n有n+1列 for(int j = 0 ; j < values[i].length ; j++){ //根据性质1,每行的首尾都为:1 if(j == 0 || j == value[i].lenght – 1){ values[i][j] = 1; }else if(i > 1){//根据性质8,除首尾外的其它数字 = 上方数 + 上方左侧的数 values[i][j] = values[i – 1][j] + values[i – 1][j – 1]; } } }

2.2.4 完整代码:

public class YangHui { public static void main(String[] args) { yangHui(8); } private static void yangHui3(int n) { int[][] values = new int[n][];//定义n行,但暂时每行的列数先不定义 for(int i = 0;i < values.length ; i++){ values[i] = new int[i + 1];//行0有1列,行1有2列,….,行n有n+1列 for(int j = 0 ; j < values[i].length ; j++){ //根据性质1,每行的首尾都为:1 if(j == 0 || j == values[i].length – 1){ values[i][j] = 1; }else if(i > 1){//根据性质8,除首尾外的其它数字 = 上方数 + 上方左侧的数 values[i][j] = values[i – 1][j] + values[i – 1][j – 1]; } } } print(values); } private static void print(int[][] values) { for(int i = 0; i < values.length; i++) { for(int j = 0; j < values[i].length; j++) { System.out.printf(“%-4d”, values[i][j]); } System.out.println(); } } }

数组的方式比较好理解,但需要创建二维数组,效率较低,接下来我们看一下不需要数组的写法。

三、不使用数组的方式3.1 算法说明

根据性质6,第n行的m个数可表示为 C(n-1,m-1),即为从n-1个不同元素中取m-1个元素的组合数。

我们将其表示为C(i , j)的组合数,那么就有以下算法:

1、例如:i=3、j=2的位置上,值为C(3,2),即(3*2)/(1*2)=3/1 * 2/2 = 3 2、例如:i=5、j=3的位置上,值为C(5,3),即(5*4*3)/(1*2*3)= 5/1 * 4/2 * 3/3 = 5 * 2 * 1 = 10 3、例如:i=7、j=4的位置上,值为C(7,4),即(7*6*5*4)/(1*2*3*4) = 7/1 * 6/2 * 5/3 * 4/4 = 353.2 代码实现

根据上述算法,我们就可以很方便的写出以下代码:

private static void yangHui2(int n) { for(int i = 0; i < n; i++) {//行 for(int j = 0; j <= i; j++) {//列 //计算每列的值 int value = 1; for(int k = 0; k < j; k++) { value = value * (i-k) / (k+1); } System.out.printf(“%-4d”, value); } System.out.println(); } }

免责声明:文章内容来自互联网,本站仅作为分享,不对其真实性负责,如有侵权等情况,请与本站联系删除。
转载请注明出处:如何不使用数组实现打印“杨辉三角形”? https://www.dachanpin.com/a/cyfx/11839.html

赞 (0)
上一篇 2023-05-12 03:49:15
一高级工程师发帖:好的代码不需要注释!网友吵翻了
下一篇 2023-05-12 03:50:20

相关推荐

  • 重磅!央行再度“降息”,下调10个BP!A股又获助力,创业板大涨3

    首席固定收益分析师张旭对券商中国记者表示,事实上,在月初投放流动时,央行强调是在“维护疫情防控特殊时期银行体系流动性合理充裕”。很显然,央行当前对资金利率的“照顾”并非主要源于对宏观经济的担忧。疫情对经济的影响是暂时的,中国经济长期向好、高质量增长的基本面没有变化。因此,在持续两周的流动性“照顾”之后,央行通过公开市场缩量的方式引导资金利率的回归常态是大势所…

    2023-05-12
  • 青海省多措施助力高校毕业生就业创业

    青海省人力资源和社会保障厅相关负责人介绍,为给高校毕业生就业创业提供保障,青海省先后出台《贯彻落实国务院关于做好当前和今后一段时期就业创业工作意见的实施意见》《关于进一步引导和鼓励高校毕业生到基层工作的实施意见》等20多个政策和配套文件,为高校毕业生到基层、到企业、到省外就业和自主创业、参军入伍全程保驾护航。还组织开展“央企专场招聘活动”、“就业网络联盟招聘…

    2023-05-17
  • 林芝市为青年就业创业打造“五大高地”

    (责编:旦增卓色、柴济东)   “我来自墨脱县,大学毕业后一度迷茫,后来参加了林芝市组织的电商培训班,萌生了创业的想法,这才有了现在的墨脱门珞石锅合作社,也带动了我家乡的乡亲们脱贫致富。”来自墨脱县的青年创业者巴珍说。   2018年以来,林芝市深入实施“125”战略行动,即“紧盯一个目标,夯实两大保障,打造五大高地”,率先在全区完成高校毕业生就业率达到90…

    2023-05-13
  • 券商看市:关注创业板蓝筹股机会

      招商证券认为,汇率升值,央行外汇占款还是为负,这暗示了三个方面。一是,人民币汇率“价”和跨境数据“量”的背离。原因主要是价格的走势,并不仅仅反映外汇市场供求的真实变化,还受其他因素影响。二是,验证关于外汇市场供求维持弱平衡的判断。三是,债市开放可能带来批发外汇市场的央行外汇占款的降幅小于零售外汇市场的变化。因此,随着债市开放和季节性贸易顺差扩大,虽然下半…

    创业分享 2023-05-22
  • 女装创业新手怎么选择供应商?诗菲度详细教程

    ① 凡本网注明“稿件来源:本网的所有文字、图片和音视频稿件,版权均属本网所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转贴或以其他方式复制发表。已经本网协议授权的媒体、网站,在下载使用时必须注明“稿件来源:本网”,违者本网将依法追究责任。 对于没有经验的服装创业新手来说,选择合适的女装货源供应商及货源是他们首先就要考虑的问题。在之前的文…

    创业分享 2023-05-12

发表回复

登录后才能评论

联系我们

在线咨询: QQ交谈

邮件:362039258@qq.com

工作时间:周一至周五,9:30-16:30,节假日休息