杨辉三角形

杨辉三角形

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1,⋯

给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入描述

输入一个整数 N。

输出描述

输出一个整数代表答案。

输入输出样例

示例 1

输入

6

输出

13

评测用例规模与约定

对于 20%20 的评测用例，1\leq N\leq 101≤N≤10； 对于所有评测用例，1\leq N\leq 10000000001≤N≤1000000000。

思路：

由于 n 很小，我们可以按从上到下、从左到右的顺序不断枚举，直到 n 第一次出现后停止枚举并输出枚举的次数即可

题解：

#include<bits/stdc++.h>

using namespace std;

int main(){
	int N; 
	cin>>N;
	int a[100][100];
	for(int i=0;i< 100;i++)
		for(int j=0;j< 100;j++)
			a[i][j]=0;
	
	a[0][0]=1;
	int ans =1;//从1开始计数，第一次出现N就是这个答案		
	bool flag=false;
	for(int i=1;i<100;i++){
		for(int j=0;j<=i;j++){
			if(j==0){
			 	a[i][j]=1;	
			}else{
                //当前第i行j列的数值为i-1行j-1列的值加上i-1行j列的值 	
				a[i][j]=a[i-1][j-1]+a[i-1][j];
			}			
			ans++;
			if(a[i][j]==N) {
				cout<<ans;
				flag=true;
				break;	
			}
		}
		if(flag)break;
	}

	return 0;
}

人麻了！！！

2022/4/6

不知道是时间复杂度抄了，还是怎么了，上面得代码只能骗30分，下面给出正解链接 https://blog.nowcoder.net/detail/a7dd1b88e51d4e79b13bbf3c39e50e23

#include <bits/stdc++.h>
using namespace std;

// 打印杨辉三角前x行，帮助直观感受
void Print(int x) {
  long long int c[100][100];

  for (int i = 1; i <= x; i++) {
    c[i][0] = 1;
    printf("%lld\t", c[i][0]);
    for (int j = 1; j < i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      printf("%lld\t", c[i][j]);
    }
    printf("\n");
  }
}

// 二分方法
long long int n;
long long int C(long long int a, long long int b) {
  long long int ret = 1;
  for (long long int i = a, j = 1; j <= b; i--, j++) {
    ret = ret * i / j;
    if (ret > n) {
      return n + 1;
    }
  }
  return ret;
}

long long int GetAns(int col) {
  long long int l = col, r = max(n, (long long int)col);
  while (l < r) {
    long long int mid = (l + r) / 2;
    if (C(mid, col) >= n)
      r = mid;
    else
      l = mid + 1;
  }

  if (C(r, col) != n) { // 没有出现则返回出现位置无限大
    return 4e18;
  } else {
    return r * (r + 1) / 2 + col + 1;
  }
}

int main() {
  scanf("%lld", &n);

  long long int ans = 4e18;
  for (int i = 0; i < 20; i++) { // 枚举前20列，记录最早出现位置
    long long int cur = GetAns(i);
    ans = min(ans, cur);
  }

  printf("%lld\n", ans);
  return 0;
}