Последовательности чисел Фибоначчи

#java

Подскажите по коду, правильный ли он или что можно доделать и дописать.
Как можно организовать это с циклом while?

Задача:

Выведите на экран первые 11 членов последовательности Фибоначчи.
Напоминаем, что первый и второй члены последовательности равны единицам,
а каждый следующий — сумме двух предыдущих.

public class Test {
 public static void main(String [] args){
     int a = 1;
     int b = 1;
     int n;
     int sum_fib;
     Scanner s = new Scanner(System.in);
     n = s.nextInt();
     for(int i = 0; i < n; i++){
         sum_fib = a + b;
         a = b;
         b = sum_fib;
         System.out.print(sum_fib + " ");
     }
 }
}

    

Ответы

Ответ 1

Я бы написал просто

System.out.print("1 1 2 3 5 8 13 21 34 55 89");


А в вашем коде все нормально. По-моему, единственный способ плохо написать вычисление
последовательности Фибоначчи - это

int fib(int i) {
    if (i == 1) return 1;
    if (i == 2) return 1;
    return fib(i - 1) + fib(i - 2);
}


то есть способ с использованием рекурсии.


Ответ 2

Приведу алгоритм получения Fib(i) за O(logN).  

Рассмотрим матрицу:  

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


Произведение матриц:  

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


показывает, что можно получить любое число Фибоначчи возведя матрицу One в степень N.  

Воспользовавшись алгоритмом быстрого возведения в степень, можно реализовать Поиск
n-го числа Фибоначчи за 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]);
  }
}


Вывод:  


  1024:
  4506699633677819813104383235728886049367860596218604830803023149600030645708721396248792609141030396244873266580345011219530209367425581019871067646094200262285202346655868899711089246778413354004103631553925405243  
  
  4096:
  4612001732280431247456445708563614127173224997617390534215059226137357133453956236072775985077061637311848907129417864574275423997101439882308358166652317363373656716074141072814493065517475413688262677419077617088948496309673353922704120725679705669386361748442871720790233981292904246541321855474289727005675146240418903692583131115962989146454578739972233255840007113102596686397958930124518885822059783685448190039658062872691964066428723178769322339485834664335313247796472730324095846596733944704930052412653763777113749102514483039561246866695780115646150369678333299122486379683222039167477498691611996122878629556831081616202064636498715093853352203252703786287926199052408354498825123496861419106453928530148716831934981264321286848387438601077819789292236505514653845305057927646386419899455438488952785050077521931600327064840520442470066917947




Сложно сказать, на каком размере задачи этот алгоритм превзойдёт линейный, потому
что произведение матриц даёт довольно большую константу.


Ответ 3

Ваш программный код, конечно, работает, вот только он не выводит первых два члена
последовательности Фибоначчи, а именно, равные 1, а так, у Вас всё правильно в коде,
и он выводит все члены последовательности, начиная с третьего. К примеру, можно решить
данную задачу через рекурсию, так как это самый очевидный способ решения данной задачи
на "естественную" рекурсию (первый способ):

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) + " ");
        }
    }
}


Либо данную задачу можно решить с помощью цикла while, к примеру данным способом
(второй способ):

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++;
        }
    }
}


Надеюсь, Вам пригодится хотя бы один из способов решения задачи.


Ответ 4

Поддерживаю @dzhioev, а через while, также:

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


Ответ 5

Я могу предложить еще такой вариант исполнения 

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] + " ");
        }
    }
}


Ответ 6

Только начал учить Java, пришел к такому:

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);
        }

    }
}


Ответ 7

private static List fibonacchiList(int num) {
        List 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;
    }


Ответ 8

Во-первых, можно по формуле Бине вычислить n-e число Фибоначчи. Но нужно быть весьма
осторожным с округлением дробей. Вот одна из возможных реализаций на Java:

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));
}


Данный алгоритм, хотя и работает с асимптотикой O(log n), но где-то после 70-го числа
Фибоначчи начнет давать погрешность (зависит от способа округления). Кроме того, после
92-го числа, возвращаемое значение достигнет предела long и будет выдавать максимальный
long. 

Еще один способ, как правильно ответил @vp_arth, это нахождение чисел Фибоначчи с
помощью возведения матриц в степень (теорию см., например, здесь). 

Представим n-e число Фибоначчи и два предыдущих ему числа как:



Тогда, если обозначить матрицу



получаем:



Отсюда, для нахождения n-го числа Фибоначчи достаточно возвести матрицу P в степень 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;
}


Асимптотика такого алгоритма O(log n).

Версии решения с рекурсией, можно улучшить так называемой мемоизацией: 

Если каждое значение, найденное при вызове рекурсивной функции вычисления числа Фибоначчи,
запоминать в таблице вместе со значением параметра, переданного при вызове, то функция,
прежде чем повторно выполнять то же самое вычисление, могла бы поискать в этой таблице
уже готовое решение. Этот приём и называется мемоизацией.

Например, уже найденные значения можно сохранять в коллекции cache = Map, где ключом будет номер числа Фибоначчи, а значением само число (например,
так cache.put(n, result)). Таким образом, алгоритм перед тем как вычислять очередную
ветвь рекурсии, мог бы искать значение в Map (например, так cache.containKey(n)) и
брать его оттуда, вместо вычисления.

Решение c циклом лучше, чем для рекурсии без мемоизации, но его асимптотика O(n)
и, следовательно, хуже (медленнее) асимптотики вычисления с помощью матриц.


Ответ 9

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


Тоже вроде работает :)


Ответ 10

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;
}


Ответ 11

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);
    }
}


Ответ 12

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=b-a;
      count++;
    }
    return result;
  }
  public static void main(String[] args) {
    Fiba(5);
  }
}


Ответ 13

Самое простое и краткое решение:

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 + " ");
        }
    }
}


Ответ 14

Как по мне проще этого ничего нет

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();
    }
}


Ответ 15

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
Ответ 16

Все хорошо в коде, но начинатся вывод должен с 1 и 1, из чего получается 2.

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] + " ");
    }


Ответ 17

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);//вывод значений на экран
        }
    }
}