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%正确的,我与其他值进行了测试,并返回正确的结果。
答
我认为递归是为了解决这样的
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
}
}
答
令问题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
答
想想重叠的子问题/动态规划。你需要记住重复呼叫子问题,这将节省你所有的时间。
答
问题是斐波那契数列的修改版本。我得到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));
}
}
为哦不对感谢,但是这是要带我的时间来了解这个过程是如何工作的。你能建议关于这个话题的任何材料吗? – Haris
那么你可以谷歌任何关于“递归”,这基本上是从它自己的身体调用函数。我不确定我可以为你推荐一个关于该主题的好资源。另外值得一提的是,您指定的问题的解决方案与计算第n个斐波纳契数字的方法完全相同,因此您也可以搜索该问题。 –
哦,哈哈我没有意识到我认为这是模式,但我错了。我想我必须更详细地研究递归;不是我最喜欢的话题,但我别无选择。 – Haris