电力建设规范下载网站,国内外知名建设设计网站,90设计官网,网站建设台词文章目录[蓝桥杯 2021 省 B] 杨辉三角形题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路#xff1a;全部代码#xff1a;[蓝桥杯 2021 省 B] 杨辉三角形
题目描述
下面的图形是著名的杨辉三角形: 如果我们按从上到下、从左到右的顺序把所有数排成一列…
文章目录[蓝桥杯 2021 省 B] 杨辉三角形题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路全部代码[蓝桥杯 2021 省 B] 杨辉三角形
题目描述
下面的图形是著名的杨辉三角形: 如果我们按从上到下、从左到右的顺序把所有数排成一列可以得到如下数列
1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, \ldots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…
给定一个正整数 NNN请你输出数列中第一次出现 NNN 是在第几个数。
输入格式
输入一个整数 NNN 。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
6样例输出 #1
13提示
对于 20%20 \%20% 的评测用例, 1≤N≤101 \leq N \leq 101≤N≤10;
对于所有评测用例, 1≤N≤1091 \leq N \leq 10^91≤N≤109 。
蓝桥杯 2021 第一轮省赛 B 组 H 题。
思路
1·以斜着看首先我们可以从中间把这个三角形劈成两半因为左右对称留左半。左半有了肯定就是最先出现的
2.看图第一行得数都是C(0,N)第二行都是C(1,N)第三行都是C(2,N)以此类推第i行就是C(i,N)也就是说每一行的数都可以用组合数来表示大小需要有一个求组合数的函数
//求组合数
long long C(int a, int b)
{long long x 1, y 1;for (int i a, j b; j 1; i--, j--){x x * i;y y * j;if (x / y n){ //如果在这过程中已经大于N了就没必要再继续了return x / y;}}return x / y;
}2.我们知道了这个数的大小与行和列有关那这就转变为在第i行第j列的数的大小,我们可以发现这个的每一行的第一个数的的组合数下面的那个数都是从2i开始的所以我们可以用二分法来找L2iRn
for (int i 0; i 14; i) // 遍历行{long long L 2 * i, // 为什么是2*iR n, mid;while (L R){mid (L R) / 2;if (C(mid, i) n){R mid - 1;}else if (C(mid, i) n){L mid 1;}else if (C(mid, i) n){flag true;break;}}3这样我们可以找到这个数的i和j然后可以发现找到一个数的i和j之后这个数所在的位置就是 所在行-1可以发现是一个等差数列然后在加上在本行的位置就能得出结果公式为(j 1) * j / 2 i 1;
if (flag true){cout (mid 1) * mid / 2 i 1;break;}4.在找得时候我们用二分的方法来找节省时间 qwq,博主是个大笨蛋找不到规律根本Orz
全部代码
#include iostream
using namespace std;
int n;
long long C(int a, int b)
{long long x 1, y 1;for (int i a, j b; j 1; i--, j--){x x * i;y y * j;if (x / y n){ // 如果在这过程中已经大于N了就没必要再继续了return x / y;}}return x / y;
}
// 一个十分简单的算组合数的函数
int main()
{cin n;bool flag false;for (int i 0; i 14; i) // 遍历行{long long L 2 * i, // 为什么是2*iR n, mid;while (L R){mid (L R) / 2;if (C(mid, i) n){R mid - 1;}else if (C(mid, i) n){L mid 1;}else if (C(mid, i) n){flag true;break;}}if (flag true){cout (mid 1) * mid / 2 i 1;break;}}system(pause);
}
