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？

回答

相关问题