java - 使用递归根据用户输入确定斐波那契数

Question

• 根据我的作业，我需要让用户以数字形式输入一个数字，并使用递归将其转换为序列中的同时斐波那契数。

• 我的问题是如何通过数组制作序列但不存储它，因此数组可以是用户输入的数字的大小......这是我的一些起始代码:

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

Answer 1

这里提供一种方法，注意this还包括 negafibonacci 序列；

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

输出

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