c - 斐波那契修正黑客排名

Question

我在 Hackerrank 上遇到了这个问题，涉及算法部分的动态规划。

A series is defined in the following manner:

Given the nth and (n+1)th terms, the (n+2)th can be computed by the following relation T(n+2) = (Tn+1)^2 + T(n)

So, if the first two terms of the series are 0 and 1: the third term = 1^2 + 0 = 1 fourth term = 1^2 + 1 = 2 fifth term = 2^2 + 1 = 5 ... And so on.

Given three integers A, B and N, such that the first two terms of the series (1st and 2nd terms) are A and B respectively, compute the Nth term of the series.

Input Format

You are given three space separated integers A, B and N on one line.

Input Constraints 0 <= A,B <= 2 3 <= N <= 20

Output Format

One integer. This integer is the Nth term of the given series when the first two terms are A and B respectively.

Note

Some output may even exceed the range of 64 bit integer.

我的代码如下:

int main() {
    int A,B,N;
    scanf("%d%d%d", &A, &B, &N);
    if (N == 1) {printf("%d\n", A); return 0;}
    if (N == 2) {printf("%d\n", B); return 0;}
    unsigned long long int C[3];
    C[0] = A; C[1] = B; C[2] = (B*B)+A;
    while((N-3)>0){
       C[0] = C[1];
       C[1] = C[2];
       C[2] = (C[1]*C[1])+C[0];
       N--;
    }
    printf("%llu\n", C[2]);

    return 0;
}

当我提交它时，它仅通过了 2/10 的测试用例(第一个和最后一个，如果这有帮助的话)。

由于我尝试使用自定义输入来查看它是否有效，并且显然它有效(0 1 5给出5)，我开始认为问题在于，正如注释所说，输出可能太大。

这是LINK解决问题

如何让这个大数字适合数组？

Answer 1

您的实现问题是溢出。不要被 A、B 和 N 的小值所迷惑。数字 T(n)快速成长。

每当我遇到需要大整数的竞争性编程任务时，我都会使用内置支持大整数的编程语言。因此解决这个问题的一种方法是使用 Python。

第二个选项是您可以实现例程来加和乘大整数(对于大整数的给定表示)。这些并不难实现。

这是我的 Python 实现。

A, B, N = (int(x) for x in raw_input().split())
if N == 1: print(A)
elif N == 2: print(B)
else:
    for i in range(2, N):
        F = A + B*B
        A = B
        B = F
    print(F)

当您使用值 A=2 执行上述代码时，我将让您发现输出。 , B=2 ，和N=20 .