Nth output sum of (N-2)th and (N-1)th

Question

I cannot figure this question out no matter what i try, i may just be over thinking it, can i get a little help? Ive already tried a variety of different for loops and I can;t figure out how to get these values

for(int a = 1; a<1000; a++) 

I want to make it so the it states a+b but i dont think thats possible

The following code is famous as Fibonacci, in which the Nth output is the sum of (N- 2)th and (N-1)th values. Write the for-expression to do the same task.

int a=1, b=1; 
while (a < 10000 ){ 
 System.out.print(a+" "+b+" "); 
 b+=a+=b; 
} 

Answer 1

Converting the while loop into a for loop, it would be:

for (int a=1, int b=1; a < 10000; b+=a+=b ){ 
   System.out.print(a+" "+b+" "); 
} 

Answer 2

You can use recursion to do this:

public int fibonacci(int n)  {
    if(n == 0) {
        return 0;
    } else if(n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Answer 3

If you want to use a loop, you could do the following (borrowed from this answer):

public int fibonacci(int n)  {
    if (n == 0)
        return 1;
    if (n == 1)
        return 3;
    int grandparent = 1;
    int parent = 3;
    int curr = 0;
    for(int i=2; i <= n; i++){
        curr = 3 * parent - grandparent;
        grandparent = parent;
        parent = curr;
    }
    return curr;
}

Answer 4

Try:

int a=1, b=1; 
for (b=1; b < 10000; b+=a ){ 
 System.out.print(a+" "+b+" "); 
 a+=b;
}

Answer 5

Here's how you would do it without recursion.

    package fib;

    public class fib {

            public static void main(String[] args) {
                    int first  = 1;
                    int second = 1;
                    int thrid  = 2;
                    System.out.format("0, %d, %d, %d", first, second, thrid);
                    while ( thrid < 1000 ) {
                            first  = second;
                            second = thrid;
                            thrid  = first + second;
                            System.out.format(", %d", thrid);
                    }
            }
    }

Output:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

Answer 6

See algorithm 3 for how to do this, you can do so without recursion using Binet's formula, copied below:

import java.lang.Math;
import java.math.BigInteger;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
class f3c {
// This program calculates the nth fibonacci number
// using alrogirhtm 3C: Binet's formula with rounding
//
// compiled: javac f3c.java
// executed: java f3c n
//

  // Method f3c.isqrt(n) finds the inverse root of n using the following
  // recurrent equation: y(n+1) = 0.5*y(n)*[3 - x*y(n)^2]
  // It is faster than typical Newton-Raphson square root finding because
  // it does not use division.
  // Funny how Java implemented exponentiation by repeated squaring
  // for BigDecimals, but did not implement any sort of square root.
 private static BigDecimal isqrt(BigDecimal x, MathContext mc) {
     BigDecimal guess = new BigDecimal(1/Math.sqrt(x.doubleValue()));
     BigDecimal three = new BigDecimal(3);
     BigDecimal half = new BigDecimal(0.5);
     BigDecimal oldguess;
     do{ oldguess = guess;
         guess = half.multiply(guess.multiply(
                   three.subtract(x.multiply(guess.pow(2)))), mc);
     } while (oldguess.compareTo(guess) != 0);

     return guess;
 }

 // method f3c.fib(n) calculates the nth fibonacci number
 // as floor( phi^n/sqrt(5) + 1/2), where phi = (1+sqrt(5.0))/2;
 private static BigInteger fib(int n) {
    MathContext mc = new MathContext(n/2, RoundingMode.HALF_DOWN);
    BigDecimal is5 = isqrt(new BigDecimal("5"), mc);
    BigDecimal one = BigDecimal.ONE;
    BigDecimal half = new BigDecimal(0.5);
    BigDecimal phi = half.multiply(one.add(one.divide(is5, mc)));
    return phi.pow(n, mc).multiply(is5).toBigInteger();
 }

 // Method f3c.f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
 private static BigInteger f(int n) {
    if(n<0)
       return (n%2==0) ? fib(-n).negate() : fib(-n);
    else
       return fib(n);
 }

 // Method f3c.f_print(n) prints the nth Fibonacci number
 private static void fib_print(int n) {
  System.out.println(n + "th Fibonacci number is " + f(n));
 }
 // Method f3c.main is the program entry point
 // It makes sure the program is called with one commandline argument
 // converts it to integer and executse fib_print
 // If the conversion fails or if the number of arguments is wrong,
 // usage information is printed
 public static void main(String argv[]) {
  try {
      if(argv.length == 1) {
          fib_print(Integer.parseInt(argv[0]));
          System.exit(0);
      }
  } catch (NumberFormatException e) { }
  System.out.println("Usage: java f3c <n>");
  System.exit(1);
 }
}

However, if you'd like to merely convert your while loop to a for loop, the general principal is, for code like so:

int var = 0;
while (var != n) {
    ...
    var++;
}

... becomes the following for loop:

for (int var = 0; i != n; i++) {
     ...
}

Answer 7

Just to be silly here how you could do it in shell:

red@cricket:~$ ./fib.sh 
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
red@cricket:~$ cat fib.sh 
#!/bin/sh

first=0
second=1
echo -n "$first, $second, "
thrid=`expr $first + $second`
echo -n $thrid 
while [ $thrid -lt 100 ]
do
        first=$second
        second=$thrid
        thrid=`expr $first + $second`
        echo -n ", $thrid"
done
echo ""

LOL! Some needs to add a python answer! Or a recursive bash solution.