6

我被困在这段代码中：

问题：一个孩子可以一次以 1,2 或 3 级的步数跳 n 级楼梯。给定 n 的值，打印出他可以爬楼梯的所有排列。

这是我的代码：

    public class HoppingLad
    {
        int count;
        void hop(int n,int present)
        {
            if(n==present)
            {
                count++;
                System.out.println("\nFinished type "+count+" climbing.\n");
            }
            else
            {
                if((n-present)>=1)
                {
                    System.out.print("\nClimbed 1 step.\nReached "+(present+1)+"   ");
                    hop(n,present+1);
                }
                if((n-present)>=2)
                {
                    System.out.print("\nClimbed 2 step. \nReached "+(present+2)+"   ");
                    hop(n,present+2);
                }
                if((n-present)>=3)
                {
                    System.out.print("\nClimbed 3 step. \nReached "+(present+3)+"   ");
                    hop(n,present+3);
                }


            }

        }

        public static void main(String [] args)
        {
            HoppingLad hl=new HoppingLad();
            hl.hop(3, 0);
            System.out.println("There are "+hl.count+" ways to climb.");
        }
    }

输出是：

 Climbed 1 step.  
 Reached 1  
 Climbed 1 step.  
 Reached 2  
 Climbed 1 step.  
 Reached 3   
 Finished type 1 climbing.


 Climbed 2 step. 
 Reached 3   
 Finished type 2 climbing.


 Climbed 2 step. 
 Reached 2   
 Climbed 1 step.
 Reached 3   
 Finished type 3 climbing.


 Climbed 3 step. 
 Reached 3   
 Finished type 4 climbing.

 There are 4 ways to climb.

我得到的输出部分正确，部分不完整。爬楼梯的方法数量是正确的，但正如你所注意到的，

爬过 2
达到 3

部分输出即将到来

攀爬 1
到达 1

部分在它之前。我已经绘制了递归树，该树甚至表明输出中不存在第一部分。

然而，用户必须从地面得到指导。我尝试了很多东西，但无济于事。谁能帮我解决这个问题？

4

4 回答 4

1

您正在将解决方案打印为部分结果，因此当您获得基于该部分解决方案的新解决方案时，它们不会重复。

换句话说，你这样做（对于 n = 3）

        --> state 0
hop(1)  --> state 1 --> print "1"
hop(1)  --> state 2 --> print "1"
hop(1)  --> state 3 --> print "1" --> print "solution";

然后你回到状态 2（没有进一步的解决方案）并回到状态 1，然后你

hop(2) --> state 3 --> print "2" --> print "solution"

不打印允许您进入状态 1 的“1”

解决方案将传递到达实际状态所需的步骤列表，并在达到解决方案时打印所有列表。当然，由于您将为此使用数组或列表，因此当您返回之前的状态时，您需要删除这些步骤。

更新：另一种选择（基于更改输出）可以根据所需的步骤数将答案制成表格。即，输出将是这样的（对于与上述相同的解决方案）：

Climbed 1
          -> Climbed 1
                       -> Climbed 1. Solution Found!
          -> Climbed 2. Solution Found!

这将允许用户自行重建路径。再说一次，您需要一个新参数来了解当前的步数。

如果您想要数组/列表版本但不想删除项目，您可以克隆列表并将副本传递给下一个函数调用，但这将是低效的。

于 2012-07-03T21:48:30.717 回答
1

I have implemented this solution. I will email you only if you have completed your homework.

What you can do is maintain a String and keep concating the current step taken and when the condition is reached, print the entire String, do not print individual steps. That way, you will reduce the overhead of checking at every recursive step how close you are to the solution. You will be sure the path will be printed only if the current step leads to a solution.

For example (suppose n=3)

3,0,"" -> 3,1,"1" -> 3,2,"11" -> 3,3,"111" (one solution over, print "111")

In these kind of problems (generally), where you need to make a series of steps to reach a threshold value, the most efficient solution (generally) is to store the list of steps and then print the entire solution rather than printing individual steps. That whay you know you can be sure you gets all solutions covered, and you are not printing when the current step does not lead to a solution.

于 2012-07-11T10:35:12.333 回答
0

您的问题 - 如果我正确理解了这个问题 - 例如，当您考虑从第 0 步爬到第 1 步的可能性时，您只需打印一次“从 0 爬到 1”然后显示从第 1 步开始的所有可能性。（其中，通常会有很多。）

相反，您需要安排在进行递归时跟踪完整的路线，然后在到达楼梯顶部时打印出整个路线。

例如，您可以通过为HoppingLad类提供一个数组来执行此操作，该数组在调用 开始时hop(n,k)描述小伙子如何进入k。然后，在这种n==present情况下，您可以查看该数组以输出关于小伙子如何从 0 变为 的完整描述n。

有几种不同的方法来组织这个，而且这个问题看起来更像是家庭作业，所以我不想填写太多细节。尽管如此，我希望以上内容对您有所帮助。

于 2012-07-03T21:46:32.100 回答
0

所以这是我的解决方案，虽然它使用 javascript，但它使用 ES6（对于数组上的扩展操作，默认参数，这将在当前版本的 Firefox 中运行良好，我在 Firefox 50 中这样做了）：

function getHopPathsCnt(totalsteps, maxhopability, curstep = 0, taken = [], total={count:0}) {
  if (totalsteps === curstep) {
    total.count++;
    console.log('A possible hop path:', taken.join(' '));
  } else {
    for (let hopped = 1; hopped <= maxhopability; hopped++) {
      if (totalsteps - curstep >= hopped)
        getHopPathsCnt(totalsteps, maxhopability, curstep + hopped, [...taken, hopped], total);
    }
  }
  if (curstep === 0) {
    console.error('Total ways to climb', totalsteps, 'steps with up to', maxhopability, 'hops at a time:', total.count);
    return total.count;
  }
}

要使用它：

getHopPathsCnt(3, 3);

输出：

可能的跳跃路径：1 1 1

可能的跳跃路径：1 2

可能的跳跃路径：2 1

可能的跳跃路径：3

一次最多 3 次跳跃 3 级攀登的总方法：4

4

与上面的 Gareth 不同，我提供完整解决方案的原因

这个问题看起来确实像家庭作业，因此我想分享它。家庭作业旨在开拓新视野。所以有时，当我没有解决方案时，我会一直用我的“当前技能/心态”来强迫它，这可能永远不会让我到任何地方。最终，当我看到解决方案并反过来工作时，它只是为我的“技能/心态”增加了一个新方面。这就是为什么我讨厌看到解决方案说“我不会填写太多细节，因为这似乎是家庭作业”。因为这导致了唯一的学习方法——把问题弄错了，然后我们愚蠢的评分系统给了我们一个不好的分数，然后“从我们的错误中学习”。如果可以避免，我讨厌从错误中学习。我也宁愿不被归入“错误”/“F”的等级，特别是如果我努力的话。

于 2016-12-10T22:52:49.103 回答