You must output the required member of the sequence, provided that the first term is 1 , and the second is any number from the console.

It turns out to be done through a cycle, and how can it be done through recursion?

 import java.util.Scanner; class Test { Scanner sc = new Scanner(System.in); int b = sc.nextInt(); int c = sc.nextInt(); int a = 1; int sum; void fibonacci() { for (int i = 0; i < c; i++) { sum = a + b; a = b; b = sum; System.out.println("sum=" + sum); } } } public class JavaApplication { public static void main(String[] args) { Test t = new Test(); t.fibonacci(); } }
  • If the second term of the sequence is not 1 , then it is no longer Fibonacci numbers (sequence), but simply a linear recurrent sequence. - Regent
  • Just as in Fibonacci, each successive number is equal to the sum of the two previous numbers. - Sergey1127
  • I understand. The problem is that a superficial reading of a question with such a title can lead to the closure of a question as a duplicate or to incorrect answers that do not take into account the variable second term in the sequence. - Regent

2 answers 2

With setting the values ​​of the first two elements of the sequence and using recursion, we get this:

 private static class MySequence { private final int firstElement, secondElement; public MySequence(int firstElement, int secondElement) { this.firstElement = firstElement; this.secondElement = secondElement; } public int calculate(int index) { if (index <= 1) return firstElement; if (index == 2) return secondElement; return calculate(index - 1) + calculate(index - 2); } } public static void main(String[] args) { int firstElement = 1; Scanner scanner = new Scanner(System.in); int secondElement = scanner.nextInt(); int requiredElementIndex = scanner.nextInt(); MySequence sequence = new MySequence(firstElement, secondElement); System.out.println(sequence.calculate(requiredElementIndex)); }

    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 (Luke) by raising the matrix One to the power N

    Using the algorithm of fast exponentiation, you can search for the nth number in O(logN)

    When starting from the matrix [0, 1] we get the well-known Fibonacci series, but we can start with any pair of numbers and get any Luke number

     import java.math.BigInteger; public class Fib { public 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 BigInteger LukNumber(int i0, int i1, int N) { if (N == 0) return BigInteger.valueOf(i0); BigInteger[][] P = pow(ONE, N); return BigInteger.valueOf(i0).multiply(P[0][0]).add(BigInteger.valueOf(i1).multiply(P[0][1])); } public static void main(String[] args) { int secondNumber = 2; // Фибоначчи 0, 1, .. for (int i = 5; i < 10; ++i) System.out.println(i+": "+LukNumber(0, 1, i)); for (int i = 5; i < 10; ++i) System.out.println(i+": "+LukNumber(1, secondNumber, i)); System.out.println(1024+": "+LukNumber(1, secondNumber, 1024)); } }

    Conclusion:

     5: 5 5: 13 6: 8 6: 21 7: 13 7: 34 8: 21 8: 55 9: 34 9: 89

    1024;

    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.