Tutorial :Fibonacci using 1 variable



Question:

I was asked the following question in an interview:

Is there any way in which Fibonacci series can be generated using only 1 variable ?

I didn't know what to answer. What should I have said?


Solution:1

Yes, you can used the closed-form expression:

where

You can calculate the expression using a double and round the result to the nearest integer. Because of the finite precision of floating point arithmetic this formula will give a wrong answer for large enough n, but I think it will work in the case when the result fits into a Java 32-bit integer.


Solution:2

Up to a point, yes (though in C, you could convert it to Java - it would look much uglier).

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

which produces:

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

:-)

The real question, of course, is: Why would you want to?


If you're curious as to how it works, it's really quite simple. The one variable is actually divided into two parts and those two parts maintain the individual values for the Fibonacci sequence. It's still technically one variable, we've just imposed some extra structure on top of it to achieve our ends.


Solution:3

Sure, using recursion:

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, ...  


Solution:4

Yes, but you still need to remember 2 values. You could take a 64-bit variable and use it as 2 32-bit vars.


Solution:5

The answer is "yes", but maybe you could be more specific.

The first example I could think of, using double recursion (that leads to an exponential complexity, not recommended):

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

Assuming a >= 0 (you could add a check for that).

(Edit - used the wrong convention of F(0) undefined, F(1) = 1)


Solution:6

After the initial 1 1, it is in theory possible to generate one value from the previous one (until machine precision comes around to bite you) via:

f = Math.round(f * PHI)  

where PHI is the constant defined in another comment:

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


Solution:7

You can always do something like this:

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

This prints (as seen on ideone.com):

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

This uses only one explicit variable, and it's essentially a linear non-recursive algorithm. It needs to be said that this is an abuse of String, though.


Solution:8

So this is evil, but:

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

My machine here starts to fall over around the 38th Fibonacci number.


Solution:9

Here's an example in C#. Shows the first 100 terms. The ratio between terms in the Fibonacci approaches the golden ratio (1.618033...), so a single variable approach simply requires a multiplication by a constant for each term.

Yay math!

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


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

Here is the java code of Fibonacci series using one variable.


Solution:11

THE PROGRAM IS FOR PRINTING UP TO 10 NUMBER BUT YOU CAN CHANGE IT.

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  

the program has some mistakes in import and in main statement but the body is full correct


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

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »