Submission

PPPPPPPPPP

Score: 100

User: kami

Problemset: อนุกรม

Language: cpp

Time: 0.001 second

Submitted On: 2024-10-16 23:47:12

#include <stdio.h>
#define MAX 100

void add(int fib1[], int fib2[], int res[], int len1, int len2, int *reslen){
    int carry = 0;
    int maxlen = len1 > len2 ? len1 : len2;

    for(int i = 0; i < maxlen; i++){
        int d1 = i < len1 ? fib1[i] : 0;
        int d2 = i < len2 ? fib2[i] : 0;

        int sum = d1 + d2 + carry;
        res[i] = sum%10;
        carry = sum/10;
    }

    if(carry > 0){
        res[maxlen++] = carry;
    }
    *reslen = maxlen;
}

void copy_array(int source[], int dest[], int len){
    for(int i = 0; i < len; i++){
        dest[i] = source[i];
    }
}

void print(int f[], int len){
    for(int i = len - 1; i >= 0; i--){
        printf("%d",f[i]);
    }
}

void fib(int n){
    int fib1[MAX] = {};
    int fib2[MAX] = {};
    int res[MAX] = {};

    fib1[0] = 1;
    fib2[0] = 1;

    int len1 = 1, len2 = 1, reslen = 1;

    if(n <= 2){
        printf("1");
        return;
    }

    for(int i = 3; i <= n; i++){
        add(fib1, fib2, res, len1, len2, &reslen);

        copy_array(fib2, fib1, len2);
        len1 = len2;
        copy_array(res, fib2, reslen);
        len2 = reslen;

        if(i == n){
            print(res, reslen);
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    fib(n);
}