当前位置:首页 > C++知识 > 正文内容

【数论】杨辉三角

亿万年的星光2年前 (2023-02-01)C++知识2254

一、起源

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

可以看出,它与上节课讲的二项式系数一样。


二、特点

  • 每个数等于它上方两数之和。

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

  • 第n行的数字有n项。

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

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

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

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

  • C(n+1,i)=C(n,i)+C(n,i-1)。

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

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

  • ……



三、实现方式

二维数组实现:

#include<bits/stdc++.h>
using namespace std;
#define N 100
int main() 
{
	int a[N][N];
	int n,i,j; 
	cin>>n;
	for(i=1;i<=n;i++)
	 for(j=1;j<=i;j++)
	 {
	 	if(j==1||j==i)//该行的第一个和该行的最后一个数据都是1 
	  		a[i][j]=1;
		else	  
	  		a[i][j]=a[i-1][j-1]+a[i-1][j];//杨辉三角基本公式
	 }
	 //下面为输出数据 
	 	for(i=1;i<=n;i++)
	 	{
	 		for(j=1;j<=i;j++)
	 		{
	 			cout<<a[i][j];
		  	}
		  cout<<endl;
	 	}
 		return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【STL】二分查找函数(算法)—binary_search

【说明】binary_search() 实现了一个二分查找算法。它会在前两个参数指定范围内搜索等同于第三个参数的元素。指定范围的迭代器必须是正向迭代器而且元素必须可以使用 < 运算符来比较。这个...

【数据结构】队列—基本操作

【数据结构】队列—基本操作

一、C++实例分析       C++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数,一个是元素类型,一个容...

指针(三):指针与函数

1.交换的例子#include<iostream> #include<cstdio> #include<cstring> using namespa...

C++整型的数据范围

数据类型标识符占字节数数值范围数值范围短整型short [int]2(16位)-32768~32767-2^15 到2^15  -1整型[long] int4(32位)-...

【题解】组合数学

【题解】组合数学

一、排列与组合口诀:有序排列,无序组合,分类相加,分步相乘。1.排列数公式:表示的含义是从n个数中选出m个进行排队,有多少种不同的排法。从n个不同的元素中任取m(m≤n)个元素的所有排列的个数,叫做从...

【算法】前缀和与差分(3)二维数组前缀和

【算法】前缀和与差分(3)二维数组前缀和

0.前言前面的一篇文章,介绍了一维数组的前缀和,这篇文章中,介绍一下二维数组的前缀和1.定义二维数组的前缀和就是按照二维数组求和。公式如下:那二维前缀和中一个f[i][j]表示的意思就是以(1,1)为...