#include <iostream>
#include <time.h>
#include <conio.h>
using namespace std;
unsigned long long  fib_1(int n);
unsigned long long  fib_2(int n);
unsigned long long  fib_3(int n);
unsigned long long  num_schmb_1 = 0;
unsigned long long  num_schmb_2 = 0;
unsigned long long  num_schmb_3 = 0;
int main() {
	clock_t start_1, finish_1;
	clock_t start_2, finish_2;
	clock_t start_3, finish_3;
	int n;
	int choice = 0;
	unsigned long long fib1;
	unsigned long long fib2;
	unsigned long long fib3;
	cout << "Ce numar din sirul lui Fibonacci doriti sa aflati: ";
	cin >> n;
	while (true) {
		cout << endl;
		cout << "1. Algoritmul recursiv" << endl;
		cout << "2. Algoritmul iterativ" << endl;
		cout << "3. Algoritmul divizarii" << endl;
		cout << "0. Exit" << endl;
		cout << "Optiunea: ";
		cin >> choice;
		if (choice == 1) {
			start_1 = clock();
			fib1 = fib_1(n);
			finish_1 = clock() - start_1;
			cout << "\n\nUtilizind algoritmul 1" << endl;
			cout << "Numarul lui fibonacci este: " << fib1 << endl << "S-au produs "
				<< num_schmb_1 << " interschimbari in " << (float)finish_1 / CLOCKS_PER_SEC << " secunde." << endl;
		}
		if (choice == 2) {
			start_2 = clock();
			fib2 = fib_2(n);
			finish_2 = clock() - start_2;
			cout << "\nUtilizind algoritmul 2" << endl;
			cout << "Numarul lui fibonacci este: " << fib2 << endl << "S-au produs "
				<< num_schmb_2 << " interschimbari in " << (float)finish_2 / CLOCKS_PER_SEC << " secunde." << endl;
		}
		if (choice == 3) {
			start_3 = clock();
			fib3 = fib_3(n);
			finish_3 = clock() - start_3;
			cout << "\nUtilizind algoritmul 3" << endl;
			cout << "Numarul lui fibonacci este: " << fib3 << endl << "S-au produs "
				<< num_schmb_3 << " interschimbari in " << (float)finish_3 / CLOCKS_PER_SEC << " secunde." << endl;
		}
		if (choice == 0){ return 0; }
	}
}
unsigned long long fib_1(int n) {
	if (n <= 2)  return 1 ;
		num_schmb_1++;
		return fib_1(n - 1) + fib_1(n - 2);
}
unsigned long long fib_2(int n) {
	unsigned long long fib_num = 0;
	unsigned long long k = 1;
	for (int i = 0; i < n; i++) {
		fib_num = k + fib_num;
		k = fib_num - k;
		num_schmb_2 ++;
	}
	return fib_num;
}
unsigned long long fib_3(int n) {
	unsigned long long i = 1;
	unsigned long long j = 0;
	unsigned long long k = 0;
	unsigned long long h = 1;
	unsigned long long t;
	while (n > 0) {
		if ((n % 2) != 0) {
			t = j*h;
			j = (i*h) + (j*k) + t;
			i = (i*k) + t;
			num_schmb_3++;
		}
		t = h*h;
		h = (2 * k*h) + t;
		k = (k*k) + t;
		n = n / 2;
		num_schmb_3 ++;
	}
	return j;

}