java TestDome：我的解决方案有效，但我只得到了 %50 而不是 %100？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32933200/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
TestDome: my solution works but I am only getting %50 right and not %100?
提问by Haris
This is the scenario question:
这是场景问题：
A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.
青蛙只能向前移动，但它可以一步步移动 1 英寸长或跳跃 2 英寸长。青蛙可以使用不同的步数和跳跃组合来覆盖相同的距离。
Write a function that calculates the number of different combinations a frog can use to cover a given distance.
编写一个函数来计算青蛙可以用来覆盖给定距离的不同组合的数量。
For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.
例如，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));
}
}
This solution only gives me %50 right not sure why its not %100 right, I tested it with other values and returns the right results.
这个解决方案只给了我 %50 right 不知道为什么它不是 %100 right，我用其他值测试了它并返回正确的结果。
回答by Pawe? Chor??yk
I think recursion is a nice way to solve problems like that
我认为递归是解决此类问题的好方法
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
}
}
回答by sve
Let f[n]be the number of combinations of steps and jumps such that you travel ninches. You can immediately see that f[n] = f[n-1] + f[n-2], that is first you can travel n-1inches in some way and then use 1 step or you can travel n-2inches in some way and then use 1 jump. Since f[1] = 1and f[2] = 2you can see that f[n] = fib(n+1), the n+1-th Fibonacci number. You can calculate it in linear timeif it suits the purpose or, more efficiently, you can calculate it in log ntime - reference
让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数。如果符合目的，您可以在线性时间内计算它，或者更有效地，您可以及时计算log n-参考
回答by James Culshaw
The problem is a modified version of the Fibonacci series. I get 100% for the following (sorry it's C# but is very similar):
问题是斐波那契数列的修改版本。我得到 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));
}
}
回答by Sajid
Think overlapping subproblem / dynamic programming. You need to memorize the repetitive calls to the sub-problem which will save you all the time.
考虑重叠子问题/动态规划。您需要记住对子问题的重复调用，这将始终为您节省时间。
回答by Obaid Altaf
I believe this should cover your all scenarios.
我相信这应该涵盖您的所有场景。
public static string numberOfCombinations(int distance)
{
if (distance == 1) {
return "Step";//1
} else if (distance == 2) {
return "Jump";//2
} else{
return numberOfCombinations(1) + numberOfCombinations(distance - 1);
}
}
