#include <iostream>
#include <math.h>

using namespace std;

void nhap(int &n) {
	do {
		cout<<"Nhap so nguyen duong > 1: "; cin>>n;
		if (n <= 1) cout<<"Vui long nhap lai"<<endl; 
	} while (n <= 1);
}

int fibonacci1(int n) {
    int a1 = 1, a2 = 1;
    if (n == 1 || n == 2) return 1;
    int a;
    for (int i = 3; i <= n; i++) {
        a = a1 + a2;
        a1 = a2;
        a2 = a;
    }
    return a;
}

int fibonacci2(int n) {
    if (n == 1 || n == 2) return 1;
    return fibonacci2(n - 1) + fibonacci2(n - 2);
}

void inra_fibonacci(int n) {
	for (int i = 1; i <= n; i++)
		cout<<fibonacci1(i)<<" ";
}

int main() {
	int n;
	nhap(n);
	cout<<"So Fibonacci thu "<<n<<" la: "<<fibonacci1(n)<<endl;
	cout<<"So Fibonacci thu "<<n<<" la: "<<fibonacci2(n)<<endl;
	cout<<"Danh sach "<<n<<" so fibonacci dau tien la: "<<endl;
	inra_fibonacci(n);
	return 0;
}