1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
|
public class Fibo {
public static void main(String[] args) {
for (int i = 0; i < 20; i++) {
print(i);
}
print2(50);
print2(92);
print2(93);
}
private static void print(int i) {
System.out.println(
"i=" + i + ", fibo=" + fibo(i) + ", fibo2 " + fibo2(i) + ", fibo3 " + fibo3(i) + ", fibo4 " + fibo4(i));
}
private static void print2(int i) {
System.out.println("i=" + i + ", fibo2 " + fibo2(i) + ", fibo3 " + fibo3(i) + "+ fibo4 " + fibo4(i));
}
public static long fibo(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return fibo(n - 1) + fibo(n - 2);
}
public static long fibo2(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
long a = 1;
long b = 0;
for (int i = 1; i < n; i++) {
long tmp = a;
a = b + a;
b = tmp;
}
return a;
}
public static long fibo3(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
}
int n_2 = n / 2;
if (n % 2 == 0) {
long r1 = fibo3(n_2);
long r2 = fibo3(n_2 + 1);
// fibo(2n)=fibo(n)*(fibo(n-1)+fibo(n+1);
return r1 * (r2-r1 + r2);
}
long r1 = fibo3(n_2);
long r2 = fibo3(n_2 + 1);
// fibo(2n+1)=fibo(n)*fibo(n)+fibo(n+1)*fibo(n+1);
return r1 * r1 + r2 * r2;
}
public static long fibo4(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
long l[] = recurseFibo4(n);
return l[0];
}
public static long[] recurseFibo4(int n) {
if (n == 0) {
return new long[] { 0, 1 };
}
if (n == 1) {
return new long[] { 1, 1 };
}
if (n == 2) {
return new long[] { 1, 2 };
}
int n_2 = n / 2;
if (n % 2 == 0) {
long l[] = recurseFibo4(n_2);
long r1 = l[0];
long r2 = l[1];
long a = r1 * (r2 - r1 + r2);
long b = r1 * r1 + r2 * r2;
return new long[] { a, b };
}
long l[] = recurseFibo4(n - 1);
long r1 = l[0];
long r2 = l[1];
long a = r2;
long b = r1 + r2;
return new long[] { a, b };
}
} |
Partager