HDU 1250(大数相加)

Love The Way You Lie 2022-09-20 12:35 184阅读 0赞

题意：如题。

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    
    char* plus(char a[], char b[], char c[]);
    
    const int F = 4;
    const int N =  7037; // 7037 刚好, 7038 超过
    const int digits = 2005;
    char Fibonacci[N][digits+1];
    
    void main()
    {
        char tmp1[digits+1], tmp2[digits+1];
        for (int i = 0; i < F; ++i)
        {
            Fibonacci[i][0] = '1';
            Fibonacci[i][1] = '\0';
        }
        for (int j = F; j < N; ++j)
        {
            plus(Fibonacci[j-4], Fibonacci[j-3], tmp1);
            plus(Fibonacci[j-2], Fibonacci[j-1], tmp2);
            plus( tmp1, tmp2, Fibonacci[j] );
            // plus( plus(Fibonacci[j-4], Fibonacci[j-3], tmp1), plus(Fibonacci[j-2], Fibonacci[j-1], tmp2), Fibonacci[j] );
        }
        int n;
        while (scanf("%d", &n) != EOF)
        {
            printf("%s\n", Fibonacci[n-1]);
        }
    }
    
    char* plus(char a[], char b[], char c[])
    {
        int alen = strlen(a);
        int blen = strlen(b);
        int maxlen, minlen;
        char *max;
        if (alen > blen)
        {
            max = a;
            maxlen = alen;
            minlen = blen;
        }
        else
        {
            max = b;
            maxlen = blen;
            minlen = alen;
        }
        int *p = new int[maxlen+1];
        memset(p, 0, maxlen * sizeof(int));
        int i, k, j;
        for (i = 0, k = 0; i < minlen; ++i)
        {
            k = (a[alen - i - 1] - '0') + (b[blen - i - 1] - '0') + k;
            p[i] = k % 10;
            k /= 10;
        }
        while (i < maxlen)
        {
            k = max[maxlen - i - 1] - '0' + k;
            p[i] = k % 10;
            k /= 10;
            ++i;
        }
    
        j = 0;
        if (p[i] = k)
        {
            c[j++] = p[i] + '0';
        }
        for (i -= 1; i >= 0; --i)
        {
            c[j++] = p[i] + '0';
        }
        c[j] = '\0';
        delete[] p;
        return c;
    }