杨辉三角形 - 蓝桥云课 (lanqiao.cn)
题目描述
题目分析
40分写法：
可以自己手动构造一个杨辉三角，然后进行循环，用cnt记录下循环数的个数，看哪个数与要找的数一样，输出cnt
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int a[N][N], x, cnt;
int main()
{a[1][1] = 1;for(int i = 2; i <= 1000; i ++){for(int j = 1; j <= i; j ++){a[i][j] = a[i - 1][j - 1] + a[i - 1][j];}}cin >> x;for(int i = 1; i <= 1000; i ++){for(int j = 1; j <= i; j ++){cnt ++;if(a[i][j] == x){cout << cnt << '\n';return 0;}}}return 0;
}50分写法：找规律（假定在第二列出现）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main()
{cin >> n;cout << n * (n + 1) / 2 + 2;return 0;
}
/*
1 3 1 + 2
2 5 3 + 2
3 8 6 + 2
4 12 10 + 2
5 17 15 + 2
...
n n * (n + 1) + 2
*/80分写法：上面两个结合
满分写法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll c(int a, int b)//组合数
{ll res = 1;for(int i = b, j = 1; j <= a; j ++, i --){res = res * i / j;}return res;}
bool check(ll k)//找在k行的哪个数
{ll l = 2 * k, r = max(2 * k, n);while(l < r){ll mid = l + r >> 1;if(c(k, mid) >= n)r = mid;else l = mid + 1;}if(c(k, r) != n)return false;cout << r * (r + 1) / 2 + k + 1;
}
int main()
{cin >> n;int k = 16;while(true){if(check(k))break;k --;}return 0;
}
