使用遞歸確定用戶輸入的斐波那契數

從我的作業中，我需要讓用戶輸入一個數字形式的數字，並在使用遞歸時將其轉換爲序列中的同步斐波那契數。

我的問題是如何使序列通過數組，但不能存儲，所以該陣列可以是用戶輸入的數字的大小...... 下面是一些開始的代碼，我：使用遞歸確定用戶輸入的斐波那契數

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

來源

2014-02-25 user3353364

我認爲你應該爲你的家庭作業做的是創建一個遞歸方法'int fibonacci（int n）'，它返回斐波那契數列中的第n個數字。你必須從用戶輸入中讀取參數'n'。請看看斐波那契數列是什麼，查看遞歸的註釋，並給它一個提示。目前，您的reverseInput（）不起作用。確定任何斐波納契數是前2的總和，除了前兩個數字是1或者只是Google的遞歸斐波那契數，但是因爲這是你的作業有點便宜。 –

快速谷歌搜索將返回足夠多的點擊量 - 包括在這個自己的網站上的問題 – fge

爲什麼不使用Binet公式？溝渠遞歸在這裏。：d –

下面是一種方法，注意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)); 
    } 
}

輸出

來源

2014-02-26 19:50:46

我沒有要發佈的實際算法（見我早期他的問題的評論），但後來我看到張貼的不必要的複雜的版本。相比之下，我將發佈簡潔的實現。注意這個返回從1,1,2開始的序列。另一個變體從0,1,1,2開始，但在其他方面是等同的。該函數假定輸入值爲1或更高。

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

就是這樣。

來源

2014-02-26 20:06:17

使用遞歸確定用戶輸入的斐波那契數

回答

相關問題