Determine Fibonacci Number from User Input using R

问题:

• From my homework, I need to have the user enter a number in numeric form, and convert it to the simultaneous fibonacci number from the sequence, while using recursion.

• My question is how can I make the sequence through an array but not store it, so the array can be the size of the number the user entered... Here's some starting code I have:

  import java.util.Scanner;
  
  public class ReverseUserInput1 {
      //a recursive method to reverse the order of user input
      public static void main(String[] args) {
          Scanner in = new Scanner(System.in);   
          ReverseUserInput1 reverseIt = new ReverseUserInput1();    //creates new object
  
          System.out.print("Program to convert a number to a fibonacci number,");
          System.out.print("  - press Enter after each number.  ");
          System.out.println("- type \'0 or 1\' to finish the program.");
          System.out.print(" --Enter a number: ");
          int aNum = in.nextInt();
  
          reverseIt.reverseInput(aNum); //invokes reverseInput() method
      }
  
      public static int reverseInput() {
          if(aNum == 0) {
              return aNum;
          }
          else if(aNum == 1) {
              return aNum;
          }     
          else {
              reverseInput();
          }
  
          System.out.println(aNum);       
      }
  }
  

回答1:

Here is one method, note that this also includes the negafibonacci sequence;

private static Map<Integer, BigInteger> fibCache = 
    new HashMap<Integer, BigInteger>();

public static BigInteger fib(int n) {
    // Uses the following identities, fib(0) = 0, fib(1) = 1 and fib(2) = 1
    // All other values are calculated through recursion.
    if (n > 0) {
        // fib(1) and fib(2)
        if (n == 1 || n == 2) {
            return BigInteger.ONE;
        }
        synchronized (fibCache) {
            if (fibCache.containsKey(n)) {
                return fibCache.get(n);
            }
            BigInteger ret = fib(n - 2).add(fib(n - 1));
            fibCache.put(n, ret);
            return ret;
        }
    } else if (n == 0) {
        // fib(0)
        return BigInteger.ZERO;
    }
    if (n % 2 == 0) {
        return fib(-n).multiply(BigInteger.ZERO.subtract(BigInteger.ONE));
    }
    return fib(-n);
}

public static void main(String[] args) throws Exception {
    for (int x = -8; x <= 8; x++) {
        System.out.println(fib(x));
    }
}

Outputs

-21
13
-8
5
-3
2
-1
1
0
1
1
2
3
5
8
13
21

回答2:

I was not going to post the actual algorithm (see my comment to his question earlier), but then I saw an unnecessarily complex version being posted. In contrast, I'll post the concise implementation. Note this one returns the sequence starting with 1,1,2. Another variant starts with 0,1,1,2 but is otherwise equivalent. The function assumes an input value of 1 or higher.

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

That's all.