草庐IT

java - 寻找最少的移动次数

coder 2024-03-17 原文

我有以下问题陈述:

Given a number n (1 < n < 10^9), what is the least number of mathematical operations from the set (divide n by 2, divide n by 3, subtract 1 from n) that can be used to transform the number n to 1?

到目前为止，我已经编写了以下代码来尝试解决该问题:

while(n!=1){

    if(n%3==0 || n%2==0){
        if(n%3==0){
            n=n/3;
            c=c+1;
        }
        if(n%2==0){
        n=n/2;
        c=c+1;
        }
    }
    else{
        n=n-1;
        c=c+1;
    }
}
System.out.println(c);

但是我没有得到想要的输出。有人可以帮我吗。

最佳答案

我认为 Tristan 是对的——您无法预先知道哪种操作最终会产生最短路径，因此您必须尝试所有操作才能获得正确答案。

通常，像这样的蛮力解决方案意味着计算将花费指数时间。您从 n 开始，然后使用您的 3 个运算计算最多 3 个新数字。然后对于这 3 个数字中的每一个你得到另外 3 个，总计 9。然后对于这 9 个中的每一个你得到另外 3 个，总计 27；等等。您可以看到您将如何快速以大量荒谬的可能性结束。

但是，您在这里的搜索空间有限。由于您的所有操作都会导致该值减少，因此您只会遇到从 1 到 n 的数字，包括在内。这意味着最多需要 n 次操作才能达到 1 的目标。每个数字只有一条最短路径，因此一旦找到该路径，就无需考虑任何您发现的其他通往相同数字的路径。如果您保留一组以前见过的数字，您应该能够消除很大一部分搜索空间，因为您可以丢弃重复的结果。 (这是 Memoization 的一种形式。)

下面是我如何解决这个问题:

  1. 创建 Set<Integer>包含以前看到的值。
  2. 创建 Map<Integer, Integer>保持您的活跃值(value)观。每个 key → value 条目的键都是从 n 到 1 的路径中的一个数字。 ，该值将是达到该数字所需的操作次数。
  3. 将初始条目n → 0在您的 Activity map 中。
  4. 虽然您的 Activity map 不包含值为 1 的键(你的目标):
    1. 创建一个空映射来保存您的新 Activity 值。
    2. 对于 active x → i 中的每个条目:
      1. 如果 x 可以被 3 整除并且 x/3 不在 seen 集合中，则添加 x/3 到 seen 并将 x/3 → i+1 放入您的新 Activity map 。
      2. 对 x/2 和 x-1 做类似的事情。
    3. 用新的 Activity map 替换您当前的 Activity map 。
  5. 返回条目的值i 1 → 我 在您的 Activity map 中。

您可以做一些事情来加快速度(例如，当您找到 1 时立即跳出循环)，或者减少内存占用(例如，如果哨兵存在，您可以丢弃它们'比您的任何 Activity 条目都大，或者使用列表而不是 map ，因为迭代的所有 i 值都相同)，但这应该足以满足您的需要。

我已将我的解决方案移植到 Java 并将其发布在此处:

http://ideone.com/qWt0LE

输出包含一些时间。请注意，此处链接的解决方案对已见 使用 map ，对 Activity 使用列表。我将链中的前一个数字存储为 seen 中每个 map 条目的值，这使我能够在最后重建链。在输出中，3 表示除以 3，2 表示除以 2，1 表示减去 1。

关于java - 寻找最少的移动次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22427257/

java寻找strongemcodealgorithmmathdynamic-programming

有关java - 寻找最少的移动次数的更多相关文章

  1. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  2. 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/

  3. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  4. ruby-on-rails - 如何重命名或移动 Rails 的 README_FOR_APP - 2

    当我在我的Rails应用程序根目录中运行rakedoc:app时，API文档是使用/doc/README_FOR_APP作为主页生成的。我想向该文件添加.rdoc扩展名，以便它在GitHub上正确呈现。更好的是，我想将它移动到应用程序根目录(/README.rdoc)。有没有办法通过修改包含的rake/rdoctask任务在我的Rakefile中执行此操作？是否有某个地方可以查找可以修改的主页文件的名称？还是我必须编写一个新的Rake任务？额外的问题:Rails应用程序的两个单独文件/README和/doc/README_FOR_APP背后的逻辑是什么？为什么不只有一个？

  5. 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

  6. 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)我

  7. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  8. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  9. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  10. ruby-on-rails - rbenv:从 RVM 移动到 rbenv 后，在 Jenkins 执行 shell 中找不到命令 - 2

    我从Ubuntu服务器上的RVM转移到rbenv。当我使用RVM时，使用bundle没有问题。转移到rbenv后，我在Jenkins的执行shell中收到“找不到命令”错误。我内爆并删除了RVM，并从~/.bashrc'中删除了所有与RVM相关的行。使用后我仍然收到此错误:rvmimploderm~/.rvm-rfrm~/.rvmrcgeminstallbundlerecho'exportPATH="$HOME/.rbenv/bin:$PATH"'>>~/.bashrcecho'eval"$(rbenvinit-)"'>>~/.bashrc.~/.bashrcrbenvversions

随机推荐