using static System.Console;
using static System.Math;
 
public class Program {
	public static void Main() {
		for (int i = 0; i < 20; i++) WriteLine($"{Fib(i)}, {FibIte(i)}, {FibRec(i)}");
	}
	static int Fib(int n) {
		double sqrt5 = Sqrt(5);
		double p1 = (1 + sqrt5) / 2;
		double p2 = -1 * (p1 - 1);
		return (int)((Pow(p1, n) - Pow(p2, n)) / sqrt5);
	}
	static int FibIte(int n) {
		int a = 0;
		int b = 1;
		for (int i = 0; i < n; i++) {
			int temp = a;
			a = b;
			b = temp + b;
		}
		return a;
	}
	static int FibRec(int n) => n < 2 ? n : FibRec(n - 1) + FibRec(n - 2);
}
 
//https://pt.stackoverflow.com/q/54456/101

dXNpbmcgc3RhdGljIFN5c3RlbS5Db25zb2xlOwp1c2luZyBzdGF0aWMgU3lzdGVtLk1hdGg7CgkJCQkJCnB1YmxpYyBjbGFzcyBQcm9ncmFtIHsKCXB1YmxpYyBzdGF0aWMgdm9pZCBNYWluKCkgewoJCWZvciAoaW50IGkgPSAwOyBpIDwgMjA7IGkrKykgV3JpdGVMaW5lKCQie0ZpYihpKX0sIHtGaWJJdGUoaSl9LCB7RmliUmVjKGkpfSIpOwoJfQoJc3RhdGljIGludCBGaWIoaW50IG4pIHsKCQlkb3VibGUgc3FydDUgPSBTcXJ0KDUpOwoJCWRvdWJsZSBwMSA9ICgxICsgc3FydDUpIC8gMjsKCQlkb3VibGUgcDIgPSAtMSAqIChwMSAtIDEpOwoJCXJldHVybiAoaW50KSgoUG93KHAxLCBuKSAtIFBvdyhwMiwgbikpIC8gc3FydDUpOwoJfQoJc3RhdGljIGludCBGaWJJdGUoaW50IG4pIHsKCQlpbnQgYSA9IDA7CgkJaW50IGIgPSAxOwoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CgkJCWludCB0ZW1wID0gYTsKCQkJYSA9IGI7CgkJCWIgPSB0ZW1wICsgYjsKCQl9CgkJcmV0dXJuIGE7Cgl9CglzdGF0aWMgaW50IEZpYlJlYyhpbnQgbikgPT4gbiA8IDIgPyBuIDogRmliUmVjKG4gLSAxKSArIEZpYlJlYyhuIC0gMik7Cn0KCi8vaHR0cHM6Ly9wdC5zdGFja292ZXJmbG93LmNvbS9xLzU0NDU2LzEwMQ==