草庐IT

java - 递归程序

coder 2024-04-04 原文

我被这段代码困住了:

Problem: A child can hop a staircase of steps n in 1,2 or 3 steps at one time. Given a value of n, print all the permutations of the order in which he can climb the staircase.

这是我的代码:

    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.

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

Climbed 2
Reached 3

部分输出原样出现

Climbed 1
Reached 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!

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

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

关于java - 递归程序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11319591/

java递归Climbed34presentrecursion

有关java - 递归程序的更多相关文章

  1. ruby - 在 Ruby 程序执行时阻止 Windows 7 PC 进入休眠状态 - 2

    我需要在客户计算机上运行Ruby应用程序。通常需要几天才能完成(复制大备份文件)。问题是如果启用sleep，它会中断应用程序。否则，计算机将持续运行数周，直到我下次访问为止。有什么方法可以防止执行期间休眠并让Windows在执行后休眠吗？欢迎任何疯狂的想法;-) 最佳答案 Here建议使用SetThreadExecutionStateWinAPI函数，使应用程序能够通知系统它正在使用中，从而防止系统在应用程序运行时进入休眠状态或关闭显示。像这样的东西:require'Win32API'ES_AWAYMODE_REQUIRED=0x0

  2. ruby - 如何指定 Rack 处理程序 - 2

    Rackup通过Rack的默认处理程序成功运行任何Rack应用程序。例如:classRackAppdefcall(environment)['200',{'Content-Type'=>'text/html'},["Helloworld"]]endendrunRackApp.new但是当最后一行更改为使用Rack的内置CGI处理程序时，rackup给出“NoMethodErrorat/undefinedmethod`call'fornil:NilClass”:Rack::Handler::CGI.runRackApp.newRack的其他内置处理程序也提出了同样的反对意见。例如Rack

  3. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  4. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  5. ruby - 无法运行 Rails 2.x 应用程序 - 2

    我尝试运行2.x应用程序。我使用rvm并为此应用程序设置其他版本的ruby​​:$rvmuseree-1.8.7-head我尝试运行服务器，然后出现很多错误:$script/serverNOTE:Gem.source_indexisdeprecated,useSpecification.Itwillberemovedonorafter2011-11-01.Gem.source_indexcalledfrom/Users/serg/rails_projects_terminal/work_proj/spohelp/config/../vendor/rails/railties/lib/r

  6. ruby-on-rails - Rails 应用程序中的 Rails : How are you using application_controller. rb 是新手吗？ - 2

    刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？ 最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr

  7. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  8. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容？ - 2

    我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

  9. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  10. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

随机推荐