使用递归用户输入确定Fibonacci数 [英] Determine Fibonacci Number from User Input using Recursion

问题描述

• 从我的功课，我需要让用户输入数字形式的数字，它从序列转换为同时斐波纳契数，而使用递归。



• 我的问题是我怎样才能使该序列通过数组，但不能存储，所以阵列可以是用户输入的数字的大小...
  下面是一些出发code我有：

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

推荐答案

下面是一种方法，注意这还包括的 negafibonacci 的序列;

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

输出

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

这篇关于使用递归用户输入确定Fibonacci数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！