关于杨辉三角形的一些规律(更详细地去看参考):
下面这些图都来自其他人所做图片
因为杨辉三角形是对称的,并且与二项式有关:
将左半部分(左半部分的编号肯定比右半部分小,不考虑右半部分)一个斜行,一个斜行地去看,会发现同一斜行中,越往左下,数越大,同一行中,越往右数越大。所以从最里面的斜行往外找,比如要找20(第一次出现在第3斜行的开头,位置在第6行(都从第0算起)),则其他斜行中要出现20,那编号一定比第3斜行的编号大。
而对称轴,即每个斜行开头(右上角)的数字的规律是:比如第K斜行,则为。
而每个斜行末尾的数字规律是:比如第k斜行,则为,为什么会有出现n呢?因为第n行的第1个(从第0开始算)数字必定是n,且该数在第n行为最后一次出现。并且第k斜行中,每个数都是所在行的第k个位置。
题目:
我的代码:
关于组合函数为何这样写,看这里:排列函数与组合函数-CSDN博客
#include <iostream> #include <vector> using namespace std; long long n; long long CC(int a, int b) { //组合数公式 a为C的下标,b为C的上标:C=a!/((a-b)!*b!) long long result = 1; for (int i = a, j = 1; j <= b; i--, j++) { result = result * i / j; if (result > n) return result; //当该组合数还没有算完就发现已经大于n,则在往下算已经没有意义。直接跳出 } return result; } bool check(int k) { //利用二分查找,去找等于n的数 long long L = k * 2; //每个斜行的下届(开头)是2k, long long R = n; //每个斜行的上界(末尾)是n,也就是第n行,因为第n行的第2个数必定会出现n if (L > R) return false; //因为n肯定会在第n行出现且最后一次出现,而第k斜行的开头数所在的行数为2k, //如果斜行开头数所在行数比第n行还大,则肯定无法在该第2k行找到等于n的数 while (L < R) //这里的条件得是<,等循环结束时,R=L,在后续的if语句判断相不相等 { long long mid = L + R >> 1; //将L+R的数右移1位,相当于(L+R)/2; if (CC(mid, k) >= n) R = mid; //如果在mid中点找到,则R会一直为该次的mid位置,只剩下L在移动 else L = mid + 1; } if (CC(R, k) != n) return false; //等二分结束发现不等于,则返回0 cout << R * (R + 1) / 2 + k + 1 << endl; //第R行前面有R行,数字之和为等差数列(1+2+3+...),在第R行中,第k位置数字是改行从0开始算,所以k+1 return true; } int main() { cin >> n; for (int k = 16; ; k--) { if (check(k)) //如果找到后则跳出for循环 break; } return 0; }
二分查找的另一种写法:
bool check(int k) { //利用二分查找,去找等于n的数 long long L = k * 2; //每个斜行的下届(开头)是2k, long long R = n; //每个斜行的上界(末尾)是n,也就是第n行,因为第n行的第2个数必定会出现n if (L > R) return false; //因为n肯定会在第n行出现且最后一次出现,而第k斜行的开头数所在的行数为2k, //如果斜行开头数所在行数比第n行还大,则肯定无法在该第2k行找到等于n的数 while (L <= R) //这里的条件得是<=,因为最后一次循环时,R=L。要去看该位置是否为要找的。 { long long mid = L + R >> 1; //将L+R的数右移1位,相当于(L+R)/2; if (CC(mid, k) == n) { cout << mid * (mid + 1) / 2 + k + 1 << endl; //第mid行前面有R行,数字之和为等差数列(1+2+3+...),在第mid行中,第k位置数字是改行从0开始算,所以k+1 return true; } if (CC(mid, k) > n) R = mid-1; else L = mid + 1; } return false; //等二分结束发现不等于,则返回0 }
参考:
【算法竞赛】杨辉三角 | 杨辉三角与组合数的关系 | 杨辉三角的算法应用 | c++代码实现公式获取杨辉三角位置的值_利用杨辉三角计算组合数-CSDN博客
AcWing 3418. 杨辉三角形 - AcWing