TestDome：我的解決方案有效，但我只能獲得％50，而不是％100？

這是場景問題：TestDome：我的解決方案有效，但我只能獲得％50，而不是％100？

青蛙只能向前移動，但它可以步進1英寸長或跳躍2英寸長。青蛙可以使用不同的步驟和跳躍組合覆蓋相同的距離。

編寫一個函數來計算青蛙可用於覆蓋給定距離的不同組合的數量。

例如，3英寸的距離可以通過三種方式進行覆蓋：步進步進，跳步和跳步。

public class Frog{ 
public static int numberOfWays(int input) { 

    int counter = 2; 

    int x = 0; 

    for (int i = 1 ; i< input -1; i++){ 

     x = i + counter; 
     counter = x; 
    } 
    if (input <3){ 
     x = input; 

    } 
    return x; 

    } 

public static void main(String[] args) { 
    System.out.println(numberOfWays(10)); 
} 
}

該解決方案只給我50％權不知道爲什麼它不是100％正確的，我與其他值進行了測試，並返回正確的結果。

來源

2015-10-04 Haris

我認爲遞歸是爲了解決這樣的

public int numberOfCombinations(int distance) { 
    if (distance == 1) { 
     return 1; //step 
    } else if (distance == 2) { 
     return 2; // (step + step) or jump 
    } else { 
     return numberOfCombinations(distance - 1) + numberOfCombinations(distance - 2); 
     // we jumped or stepped into the current field 
    } 
}

來源

2015-10-04 12:05:23

爲哦不對感謝，但是這是要帶我的時間來了解這個過程是如何工作的。你能建議關於這個話題的任何材料嗎？ – Haris

那麼你可以谷歌任何關於「遞歸」，這基本上是從它自己的身體調用函數。我不確定我可以爲你推薦一個關於該主題的好資源。另外值得一提的是，您指定的問題的解決方案與計算第n個斐波納契數字的方法完全相同，因此您也可以搜索該問題。 –

哦，哈哈我沒有意識到我認爲這是模式，但我錯了。我想我必須更詳細地研究遞歸;不是我最喜歡的話題，但我別無選擇。 – Haris

令問題f[n]有步驟的組合的數量的好辦法和跳躍，使得您的旅行n英寸。您可以立即看到f[n] = f[n-1] + f[n-2]，即您首先可以以某種方式行駛n-1英寸，然後使用1步，或者您可以以某種方式行駛n-2英寸，然後使用1次跳躍。由於f[1] = 1和f[2] = 2可以看到，f[n] = fib(n+1),n+1-Fibonacci number。如果它適合的目的，你可以在linear time計算的話，或者更有效，你可以在log n時間計算的話 - reference

來源

2015-10-04 13:14:06 svs

想想重疊的子問題/動態規劃。你需要記住重複呼叫子問題，這將節省你所有的時間。

來源

2016-02-09 00:11:57 Sajid

問題是斐波那契數列的修改版本。我得到100％以下（抱歉，這是C＃，但很相似）：

using System; 

public class Frog 
{ 
    public static int NumberOfWays(int n) 
    { 

     int firstnumber = 0, secondnumber = 1, result = 0; 

      if (n == 1) return 1; 
      if (n == 2) return 2; 


      for (int i = 2; i <= n + 1; i++) 
      { 
       result = firstnumber + secondnumber; 
       firstnumber = secondnumber; 
       secondnumber = result; 
      } 

      return result; 

    } 

    public static void Main(String[] args) 
    { 
     Console.WriteLine(NumberOfWays(3)); 
     Console.WriteLine(NumberOfWays(4)); 
     Console.WriteLine(NumberOfWays(5)); 
     Console.WriteLine(NumberOfWays(6)); 
     Console.WriteLine(NumberOfWays(7)); 
     Console.WriteLine(NumberOfWays(8)); 
    } 
}

來源

2016-07-06 19:41:02

TestDome：我的解決方案有效，但我只能獲得％50，而不是％100？

回答

相關問題