每日一题之杨辉三角

题目描述

下面的图形是著名的杨辉三角形：

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

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

输入描述

输入一个整数 N。

输出描述

输出一个整数代表答案。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) { // 直接处理n=1的情况
        cout << 1;
        return 0;
    }

    vector<vector<int>> a(100, vector<int>(100, 0)); // 使用动态数组防止栈溢出[3,9]
    a[0][0] = 1;
    bool found = false;

    for (int i = 1; i < 100; ++i) {
        a[i][0] = 1; // 每行首元素为1
        for (int j = 1; j <= i; ++j) { // 每行最多i+1个元素[7,10](@ref)
            a[i][j] = a[i-1][j] + a[i-1][j-1];
            if (a[i][j] == n) {
                // 位置公式：前i行的元素总数 + 当前列索引 +1
                cout << (i*(i+1))/2 + j + 1; // 修正位置计算公式
                found = true;
                break;
            }
        }
        if (found) break;
    }

    return 0;
}

暴力解法，可以通过%40的样例

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

int main() {
    long long n;
    cin >> n;
    
    // 处理特殊情况：数字1在杨辉三角中首次出现的位置是1
    if (n == 1) {
        cout << 1;
        return 0;
    }
    
    // 初始化组合数存储数组（经验值44723为最大可能行数）
    vector<long long> a(44723 + 1);  
    a[0] = 1;  // 第0行初始值C(0,0)=1
    
    // 遍历行号i（对应实际行号为i-1）
    for (int i = 3; i <= 44723; i++) { 
        // 从中间向两边计算（利用对称性优化）
        for (int j = i / 2; j > 0; j--) { 
            // 处理奇数行的中心元素（值为左右两数之和的2倍）
            if (j == i / 2 && (i & 1)) { 
                a[j] = a[j - 1] * 2;  // 中心对称优化
            } else {
                a[j] = a[j - 1] + a[j];  // 组合数递推公式C(n,k)=C(n-1,k-1)+C(n-1,k)
            }
            
            // 命中目标值时计算位置
            if (a[j] == n) {
                // 位置公式：前i-1行总元素数 + 当前行位置索引 +1
                cout << i * (i - 1) / 2 + j + 1;
                return 0;
            }
        }
    }
    
    /* 未找到时的处理逻辑：
       当N为质数时，首次出现在第N+1行第2个位置
       总位置 = 前N行元素数 + 2 = N(N+1)/2 + 2 
    */
    cout << n * (n + 1) / 2 + 2;
    return 0;
}