Fibonacci number sequences

I will give the algorithm for obtaining Fib(i) for O(logN) .

Consider the matrix:

  | F0, F1 | = | 0 1 | = One | F1, F2 | | 1 1 | 

Matrix product:

 [ F(n-2), F(n-1) ] * One = [ F(n-1), F(n)] 

shows that you can get any Fibonacci number by raising the matrix One to the power N

Using the algorithm of fast exponentiation, you can search for the n-th Fibonacci number for O(logN)

 import java.math.BigInteger; public class Fib { public final static BigInteger[][] ONE = {{BigInteger.ZERO, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ONE}}; public static BigInteger[][] mul(BigInteger[][] a, BigInteger[][] b) { BigInteger[][] res = { {a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])), a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))}, {a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])), a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))} }; return res; } public static BigInteger[][] pow(BigInteger[][] a, int k) { if (k == 0) return ONE; if (k == 1) return a; if (k == 2) return mul(a, a); if (k % 2 == 1) return mul(ONE, pow(a, k - 1)); return pow(pow(a, k / 2), 2); } public static void main(String[] args) { System.out.println(1024+": "+pow(ONE, 1024)[0][1]); System.out.println(4096+": "+pow(ONE, 4096)[0][1]); } } 

Conclusion:

1024: 45066626338778198131043832357288860493678605962186048303030231496000645708721396248796609141030396244873266580345011219530209367425182383383383383383383383383383383383383383383383387781381310363833817825

4096:

It is difficult to say at what size of the problem this algorithm will exceed the linear one, because the product of matrices gives a fairly large constant.

Your program code, of course, works, only it does not output the first two members of the Fibonacci sequence, namely, equal to 1, and so, you have everything correctly in the code, and it displays all the members of the sequence, starting with the third. For example, you can solve this problem through recursion, since this is the most obvious way to solve this problem on "natural" recursion (the first method):

 public class Test { private static int f(int index) { if (index <= 0) { return 0; } else if (index == 1) { return 1; } else if (index == 2) { return 1; } else { return f(index - 1) + f(index - 2); } } public static void main(String[] args) { int n = 11; for (int i = 1; i <= n; i++) { System.out.print(f(i) + " "); } } } 

Or this task can be solved using a while , for example, in this way (the second method):

 public class Test { public static void main(String[] args) { int n = 11; int a = 1, b = 1; System.out.print(a + " " + b); int fib = 2, i = 2; while (i < n) { fib = a + b; a = b; b = fib; System.out.print(" " + fib); i++; } } } 

I hope you can use at least one way to solve the problem.

I support @dzhioev , and through the while, also:

 int i=0; sum_fib = 1; while(i++ < n){ System.out.print(sum_fib + " "); sum_fib = a + b; a = b; b = sum_fib; } 

I can offer another version of this

 public class phybonacci { public static void main(String[] args) { int roll[] = new int[20]; for (int i = 0; i <20; i++) { if (i == 0) roll[i] = 1; if (i == 1) roll[i] = 1; if (i > 1) roll[i] = roll[i - 1] + roll[i - 2]; System.out.print(roll[i] + " "); } } } 

Just started to learn Java , came to this:

 package fibonachi; public class New { public static void main(String[] args) { int i = 0; int a = 1; int b = 0; for (i = 0; i <= 10; i++) { if (i == 0) { System.out.println("Элемент последовательности 0 = 0"); } int fibb = a + b; a = b; b = fibb; int d=i+1; System.out.println("Элемент последовательности " + d+ " = " + fibb); } } } 

 private static List<Integer> fibonacchiList(int num) { List<Integer> numbers = new LinkedList<>(); int res = 0; int count = 0; while (count != num) { if (count == 0 || count == 1) { numbers.add(1); count++; } else { res = numbers.get(count - 1) + numbers.get(count - 2); numbers.add(res); count++; } } return numbers; } 

First, you can use the Binet formula to calculate ne the Fibonacci number. But you need to be very careful with rounding fractions. Here is one of the possible Java implementations:

 public long fibBine(final long n) { double p = (1 + Math.sqrt(5)) / 2; double q = 1 / p; return (long) ((Math.pow(p, n) + Math.pow(q, n)) / Math.sqrt(5)); } 

This algorithm, although it works with O (log n) asymptotics, but somewhere after the 70th, Fibonacci will start giving an error (depending on the rounding method). In addition, after the 92nd, the return value will reach the long limit and will return the maximum long .

Another way, as @vp_arth correctly answered, is to find the Fibonacci numbers using the power of matrices (see the theory, for example, here ).

Imagine ne Fibonacci number and the two previous numbers as:

Then, if we denote the matrix

we get:

Hence, to find the n-th Fibonacci number, it suffices to raise the matrix P to the power n:

 public static long fib(long n) { if (n <= 0) return 0; long i = (int) (n - 1); long a = 1, b = 0, c = 0, d = 1, tmp1,tmp2; while (i > 0) { if (i % 2 != 0) { //если степень нечетная //умножаем матрицу на вектор tmp1 = d * b + c * a; tmp2 = d * (b + a) + c * b; a = tmp1; b = tmp2; } //умножаем матрицу на саму себя tmp1 = (long) (Math.pow(c, 2) + Math.pow(d, 2)); tmp2 = d * (2 * c + d); c = tmp1; d = tmp2; i = i / 2; //уменьшаем степень вдвое } return a + b; } 

Asymptotics of such an algorithm O (log n).

Versions of the solution with recursion can be improved by the so-called memoization:

If each value found in the call to the recursive Fibonacci number calculation function is stored in the table along with the value of the parameter passed in the call, the function could look for a ready-made solution in this table before re-doing the same calculation. This technique is called memoization.

For example, the values ​​already found can be stored in the cache = Map<Integer, Integer> collection, where the key will be the Fibonacci number number and the number itself (for example, cache.put(n, result) ). Thus, the algorithm, before computing the next branch of recursion, could search for a value in the Map (for example, cache.containKey(n) ) and take it from there instead of the calculation.

A solution with a cycle is better than for recursion without memoization, but its asymptotic behavior is O (n) and, therefore, worse (slower) asymptotic calculation using matrices.

 int a = 0; for (int i = 1; i<999 ; i=i+a) { a+=i; System.out.println(i); System.out.println(a); } 

It also seems to work :)

 int i = 0, n = 11; int[] f = new int[n]; while (i < n) { f[i] = (i < 2) ? 1 : f[i-2]+f[i-1]; System.out.print(f[i]+" "); ++i; } 

 public static void main(String[] args) { Scanner s = new Scanner(System.in); System.out.print("Введите любое число: "); int n = s.nextInt(); int a = 1 int b = 1; int fib = 2 int i = 2; System.out.println("Фибоначчи числа " + n + ":" ); System.out.print(a + " " + b); while (i < n) { fib = a + b; a = b; b = fib; i++; System.out.print(" "+ fib); } } 

 public class Fibbonaci { public static int result=0; public static int count=0; public static int a=1, b=1; public static int Fiba(int number) { while (count<=number){ System.out.print(a+" "); b=b+a; a=ba; count++; } return result; } public static void main(String[] args) { Fiba(5); } } 

The simplest and most concise solution:

 import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Ideone { public static void main (String[] args) { int a[] = new int[11]; a[0] = 1; a[1] = 1; for(int i = 2; i<11; i++){ a[i] = a[i-1] + a[i -2]; } for(int o : a){ System.out.print(o + " "); } } } 

As for me, this is nothing easier

 public class Fibonachy { public static void fibo() { int fibo1 = 1; int fibo2 = 0; int fibonachi; for (int i = 0; i < 10; i++) { fibonachi = fibo1 + fibo2; fibo1 = fibo2; fibo2 = fibonachi; System.out.print(fibonachi + ", "); } } public static void main(String[] args) { fibo(); } } 

 public class Fib { public static void main(String[] args) { for (int i = 1; i <= 15; i++) fib(i); } static void fib(int n){ int f = 0; int temp1 = 1; int temp2 = 1; for (int i = 1; i<n; i++) { f = temp1; temp1 = temp2; temp2 = temp1+f; } System.out.print(f + " "); } } 

How do you like this solution?

Everything is good in the code, but the output should start with 1 and 1, from which 2 is obtained.

 public static void main(String[] args) { int n1 = 1, n2 = 1, sum = 1; int [] mas = new int[20]; mas[0] = 1; for(int i = 1; i < mas.length; i++){ mas[i] = sum; sum = n1 + n2; n1 = n2; n2 = sum; } for(int i = 0; i < mas.length; i++){ System.out.print(mas[i] + " "); } 

 public class fibonacci { public static void main(String[] args) { int a = 1; //переменная которая будет использоваться как предпредыдущий член "уровнения" int b = 1; //переменная которая будет использоваться как предыдущий член "уровнения" System.out.print(a + " " + b); //выводит на экран первые две последовательности членов Фибоначчи int x = 9; //переменная используемая для лимита повторения цикла int i = 0; //переменная, которая будет использоваться для старта отсчёта цикла int sum = 0; //переменная используемая как результат функции, а в последующих "жизнях" цикла, как предыдущий член последовательности /*while(i < x){ //задаём количество повторений - "жизни" цикла sum = a + b; // первый результат a = b; // помещаем предыдущий член последовательности в первую переменную для инициации предпредыдущего члена последовательности b = sum;// помещаем предыдущий член последовательности во вторую переменную для инициации предыдущего члена последовательности System.out.print(" " + sum); //вывод значений на экран i++; // новый повтор цикла }*/ for(i = 0; i < x; i++){ //задаём количество повторений - "жизни" цикла sum = a + b; // первый результат a = b; // помещаем предыдущий член последовательности в первую переменную для инициации предпредыдущего члена последовательности b = sum;// помещаем предыдущий член последовательности во вторую переменную для инициации предыдущего члена последовательности System.out.print(" " + sum);//вывод значений на экран } } }