杨辉三角（蓝桥杯2021年H）

输入一个数字，看杨辉三角压缩矩阵第几个数与之相等。

#include<iostream>
using namespace std;
/*
typedef struct Node {int* data;int size;Node* next;
}Node,*Linklist;
*/
int C(int a,int b) {//求解组合数int c = 1,div = 1;if (b == 0) {c = 1;}else {for (int i = 0; i < b; i++) {c *= (a - i);}for (int j = 1; j <= b; j++) {div *= j;}c /= div;}return c;
}
int main(){//Linklist head = new Node;//Linklist rear = head;//rear->next = nullptr;int n, index = 0;cin >> n;for (int i = 0;; i++) {//Linklist node = new Node;//node->size = i+1;//node->next = nullptr;for (int j = 0; j <= i;j++) {//node->data[j] = C(i,j);index++;if (n == C(i, j)) {cout << index;return 0;}}//rear->next = node;//rear = node;}//return 0;
}

算法改进，基于行最大的二分查找

#include<iostream>
using namespace std;
int n;
int C(int a,int b) {int v = 1, div = 1;if (b != 0) {if (a > 20) {return C(a - 1, b - 1) + C(a - 1, b);}else {for (int i = 0; i < b; i++) {v *= (a - i);}for (int j = b; j >= 1; j--) {div *= j;}return v/div;}}
}
void nom_serch(int left) {for (int i = left;;i++) {for (int j = 0; j <= i/2;j++) {if (C(i,j) == n) {cout << i * (i + 1) / 2 + j + 1;return;}}}
}
void t_div_serch(int left,int right) {int mid = (left + right) / 2;if (C(mid,mid/2)<n) {t_div_serch(mid+1,right);}else if(C(mid, mid / 2) > n){nom_serch(left);}else {cout <<mid * (mid + 1) / 2 + mid / 2 + 1;return;}
}
int main() {cin >> n;t_div_serch(0,n);return 0;
}