当前位置:   article > 正文

【蓝桥杯经典数学题】杨辉三角形

【蓝桥杯经典数学题】杨辉三角形

杨辉三角一图览

			  			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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

前言

由图可知杨辉三角具有对称性,很多时候可以折半计算,节省时间
同时我们可以以排列组合的方式将杨辉三角展现出来

借个图先
在这里插入图片描述

求杨辉三角任意一行

我们在编程界中经常把排列组合中的公式用A(a,b),C(a,b)表示
比如C(5,2) = 10
那么对n-1行的公式可以写成
C(n,r) = (n-r + 1)/ r * C(n,r-1);
杨辉三角的每一行初始值为C(n,0) = 1

又根据杨辉三角的对称性,我们可以折半计算,在计算中心轴左边的值的同时也能将右边的值算出来

该公式的应用
lP1118 [USACO06FEB]Backward Digit Sums G/S

代码

#include <iostream>

using namespace std;

const int N = 30;

int n,sum;
bool st[N];
int a[N];
int delta[N];

void getdelta()
{
	delta[0] = delta[n-1] = 1;
	
	if(n > 1)
	{
		for(int i = 1;i*2 <= n;++i)
			delta[i] = delta[n-i-1] = (n-i) * delta[i-1]/i;
	}
} 

bool dfs(int u,int num,int v)
{
	if(v > sum) return false;
	
	if(u == n)
	{
		if(v == sum)
		{
			a[u] = num;
			return true;
		}
		return false;
	}
	
	st[num] = true;
	
	for(int i = 1;i <= n;++i)
	{
		if(!st[i] && dfs(u + 1,i,v + delta[u] * i))
		{
			a[u] = num;
			return true;
		}
	}
	st[num] = false;
	
	return false;
}
int main()
{
	cin>>n>>sum;
	
	getdelta();//得到第n层杨辉三角 
	
	if(dfs(0,0,0)) for(int i = 1;i <= n;++i) cout<<a[i]<<' ';
	
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

求杨辉三角某一值起始位置

经过多数人的研究,已经找到了一种非常精妙的方法来快速确定任意值的起始位置,所耗时间只需4ms

首先再看一次图

			  			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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

我们可以将杨辉三角的右半边删掉,因为杨辉三角的对称性,显而易见我们能推导出任意值的起始位置一定在左半边

			  			1
					1		
				1		2      
			1       3	    
		1		4		6		
	1		5		10	
1		6		15		20	
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

得到该图后我们发现,我们可以通过斜行位置与行位置来确定某一值
假设起始行数与斜行都为0
比如我们求C(6,3),组合数C(6,3) = 20
该过程代码

long long C(int a, int b) //C(a,b)
{
   long long res = 1;
   for (int i = a, j = 1;j <= b;--i, ++j)
   {
   		res = res * i / j;
   }
   return res;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

同时我们可以确定,这一斜行找到的值的位置,总会比他上面一个斜行找到同一值的位置要小
因此我们可以倒着枚举每一斜行来寻找某一值,找到的位置一定是起始位置

而且每一斜行k的起始行数n,总有一种规律 2*k = n

现在我们总结一下前面找到的规律
1.通过斜行与行的位置可以推断某一值
2.倒着枚举每一斜行可以找到该值的第一次出现位置
3.斜行k * 2 = 斜行起始行数n
4.由123点我们可以通过二分查找行来寻找该值,起始行为2*k,终点行为n(选择n是因为n足够大)
补充一点,如果已知某一行数n,可以推断该行之前总共有C(n,2)个数,在把斜行看做列,即可得到某一值的位置公式

pos = (n + 1)*n / 2 + k +1;
  • 1

例题
P8749 [蓝桥杯 2021 省 B] 杨辉三角形
实现代码

#include <iostream>

using namespace std;

long long n;

long long C(int a, int b) //C(a,b)
{
	long long res = 1;
	for (int i = a, j = 1;j <= b;--i, ++j)
	{
		res = res * i / j;
		if (res > n) return res;//防止超过n直接爆long long,提前退出
	}
	return res;
}
int main()
{
	cin >> n;

	if (n == 1)//因为C(2,1)不存在,需要特判
	{
		cout << 1 << endl;
		return 0;
	}
	for (int i = 16;i >= 1;--i)
	{
		long long l = 2 * i, r = max(l, n);//有可能l比n大

		while (l < r)//二分查找左端点
		{
			long long mid = (l + r) >> 1;
			if (C(mid, i) < n) l = mid + 1;
			else r = mid;
		}

		if (C(l, i) == n)
		{
			cout << (l + 1) * l / 2 + i + 1 << endl;
			return 0;
		}
	}

	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/439345
推荐阅读
相关标签
  

闽ICP备14008679号