c++ - 寻找系列的第N个术语

我有一个简单的问题。

我有N个数字的数组A []。我必须执行此操作:

for(i = 2; i<=N; i++)
    A[i] = A[i] + A[i-1]

到数组A [] k次。在执行此操作k次之后，我必须输出第X个索引元素。

用蛮力去做，将导致TLE。

我在寻找某种模式，但是，我找到了一个不理想的解决方案。

您能帮我一下，找到一些更有效的解决此问题的方法。

我有一个例子来澄清这个问题。

假设数组A是[1,2,3]，然后我需要执行3次上述操作:

第一回合后的阵列:A=[1,3,6]第2回合后的阵列:A=[1,4,10]第三回合后的阵列:A=[1,5,15]
因此，如果我现在需要查找数组的第二个元素，则为5。

最佳答案

我看一下Pascal的三角形(就像@MBo所说的那样)，您可能会注意到，在k次之后，每个数字在最终结果中相加的次数等于对角线后面的三角形中的一个正方形。让我们看一个例子:



该图像对应于前三个元素的四次迭代。因此，您可以看到，输入的k是否等于要返回的元素的索引数，n是否等于要返回的元素的索引，我们要做的就是将对角线中的每个数字乘以蓝色，直到红色行(图像配置对应于k = 4和n = 2)。

之后，我们有以下公式:



现在，为了改进计算上面显示的公式的方式，我们可以使用动态编程并从0 ... k + n计算阶乘函数(请注意，序列中较大的数字为k-1 + n)。这样我们就可以在恒定时间内访问factorial(n)。同样，如果我们在求和内扩展组合因子，我们会注意到因果(k - 1 + i - i)! = (k - 1)!如此，我们可以将其置于求和之外。

这是代码:

#include "stdafx.h"
#include "iostream"

using namespace std;

int findingXth(int a[], int n, int k, int factorial[]){

    if (k == 0)
        return a[n];

    int result = 0;

    for (int i = 0; i <= n; ++i)
    {
        int up = k - 1 + i;
        result += (factorial[up] / factorial[i]) * a[n - i];
    }
    return result / factorial[k - 1];
}

int main(int argc, _TCHAR* argv[])
{
    int a[3] = { 1, 2, 3 };
    int n = 2;
    int k = 3;

    int factorial[100000]; // probably the expecification of the problem has some upper bounds for n and k (the length of the factorial array can be set to n+k+1);
    factorial[0] = 1;

    for (int i = 1; i < n + k; i++)
    {
        factorial[i] = factorial[i - 1] * i;
    }

    int result = findingXth(a, n, k, factorial);

    std::cout << result;

    return 0;
}

关于c++ - 寻找系列的第N个术语，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35262774/