Фибоначчи с использованием 1 переменной

Question

я был задан следующий вопрос в интервью:

Есть ли способ, в котором ряд Фибоначчи могут быть получены с использованием только 1 переменной?

Я не знал, что ответить. Что я должен был сказать?

Answer 1

Да, вы можете использоваться closed-form expression:

где

Вы можете вычислить выражение с помощью double и округлить результат до ne arest integer. Из-за конечной точности арифметики с плавающей запятой эта формула даст неправильный ответ для достаточно большого числа n, но я думаю, что он будет работать в случае, когда результат вписывается в 32-битное целое число Java.

Answer 2

Да, но вы все равно должны помнить 2 значения. Вы можете взять 64-битную переменную и использовать ее как 2 32-битных vars.

Answer 3

Конечно, с помощью рекурсии:

public class Test { 

    public static int fib(int n) { 
     return n < 2 ? n : fib(n-1) + fib(n-2); 
    } 

    public static void main(String[] args) { 
     for(int i = 0; i <= 10; i++) { 
      System.out.print(fib(i)+", "); 
     } 
     System.out.println("..."); 
    } 
} 

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 

Answer 4

Ответ "да", но, возможно, вы могли бы быть более конкретными.

Первый пример, который я мог думать, используя двойной рекурсии (что приводит к экспоненциальному сложности, не рекомендуется):

int fib(int a) { 
    if (a < 2) { 
    return 1 
    } else { 
    return fib(a-1) + fib(a-2); 
    } 
} 

Предполагая> = 0 (можно добавить проверку для этого).

(Edit - используется неправильный условность F (0) неопределенную, F (1) = 1)

Answer 5

До некоторой степени, да (хотя в C вы можете преобразовать его в Java - это выглядело бы намного уродливее).

#include <stdio.h> 
#include <stdlib.h> 

int main (void) { 
    unsigned long i = 1; 
    printf ("0\n"); 
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) { 
     printf ("%d\n", i & 0xffff); 
     i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff)); 
    } 
    return 0; 
} 

, который производит:

0 
1 
1 
2 
3 
5 
8 
13 
21 
34 
55 
89 
144 
233 
377 
610 
987 
1597 
2584 
4181 
6765 
10946 
17711 
28657 

:-)

Реальный вопрос, конечно, есть: Почему вы хотите?

---

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

Answer 6

После первоначального 1 1, это теоретически возможно генерировать одно значение из предыдущего (до машины точности не приходит укусить вас) с помощью:

f = Math.round(f * PHI) 

где PHI это константа, определенная в другом комментарии :

static final double PHI = (1 + Math.sqrt(5))/2;

Answer 7

Вы всегда можете сделать что-то вроде этого:

String theOneVar = "100;0;1"; 
    while (true) { 
     if (theOneVar.split(";")[0].equals("0")) break; 
     System.out.println(theOneVar.split(";")[1]); 
     theOneVar = String.format("%s;%s;%s", 
      Integer.parseInt(theOneVar.split(";")[0]) - 1, 
      theOneVar.split(";")[2], 
      new BigInteger(theOneVar.split(";")[1]).add(
       new BigInteger(theOneVar.split(";")[2]) 
      ) 
     ); 
    } 

Это печатает (as seen on ideone.com):

0 
1 
1 
2 
3 
5 
8 
13 
: 
: 
83621143489848422977 
135301852344706746049 
218922995834555169026 

Это использует только один явный переменной, и это по существу линейный нерекурсивна алгоритм. Нужно сказать, что это злоупотребление String.

Answer 8

Вот пример на C#. Показывает первые 100 терминов. Отношение между членами в Фибоначчи приближается к золотому отношению (1.618033 ...), поэтому для одного переменного подхода просто требуется умножение на константу для каждого члена.

Yay математика!

double fib = 1; 
for (int i = 0; i < 100; i++) 
{ 
    Console.WriteLine("" + fib); 
    fib = Math.Round(fib *= 1.6180339887d); 
} 

Answer 9

Так что это зло, но:

static String fibRecord = "x;"; 

static int nextFib() { 
    try { 
    return fibRecord.indexOf(';'); 
    } finally { 
    fibRecord = fibRecord.replaceAll("(x*);(x*)", "$1$2;$1"); 
    } 
} 

public static void main(String[] ignored) { 
    for (int i=0; i < 30; i++) { 
    System.out.println(nextFib()); 
    } 
} 

Моя машина здесь начинает падать вокруг 38-го числа Фибоначчи.

Answer 10

class fibo{ 
    public static void main (String args[]) { 
    long i = 1; 
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) { 
     System.out.println(i & 0xffff); 
     i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff)); 
    } 
    } 
} 

Ниже представлен код java-кода серии Fibonacci с использованием одной переменной.

Answer 11

ПРОГРАММА ДЛЯ ПЕЧАТИ ДО 10 НОМЕР, НО ВЫ МОЖЕТЕ ИЗМЕНИТЬ ЭТО.

import java. i o.*; 

class q 
{ 

public static void main()throws IO Exception 

{ 

int n=0; 

for(int i=1; i<=10 ; i++) 

{ 

    System.out.print(n +" "); 

    n=(int)Math.round(n*1.618) 

    } 

} 

} 


1.618 = PHI 

программа имеет некоторые ошибки в импорте и в главном заявлении, но тело полно правильно

Answer 12

public class test { 


public static void main(String[] args) { 
int arr[]=new int[13]; 
arr[0]=0; 
arr[1]=1; 

for(int i=2;i<=12;i++){ 
arr[i]=arr[i-1]+arr[i-2]; 
} 
for(int i=0;i<=arr.length-1;i++){ 
System.out.print(arr[i]+" "); 
} 

} 

}