Fibonacci

Lab C Beginner 10 points

Read n (1–40) and print the first n Fibonacci numbers (starting 0 1).

Input

One integer.

Output

One line.

Example

Input

Output

0 1 1 2 3 5 8 13 21 34

Sample input available Sample output available

Editor

Hints

Keep the last two values and update both each step.

Solution explanation

The iterative version uses constant memory and is very fast.

Show solution

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        printf("%d", a);
        if (i < n - 1) printf(" ");
        int next = a + b;
        a = b;
        b = next;
    }
    printf("\n");
    return 0;
}

Output

Answer