Tag: 算法

如何在Ruby中测试值是否为素数？ 简单和困难的方式？

我正在尝试创建一个程序来测试一个值是否为素数，但我不知道如何。 这是我的代码： class DetermineIfPrime def initialize (nth_value) @nth_value = nth_value primetest end def primetest if Prime.prime?(@nth_value) puts (“#{@nth_value} is prime”) else puts (“This is not a prime number.”) end rescue Exception puts (“#{$!.class}”) puts (“#{$!}”) end end 每次我跑，它都会返回。 NameError uninitialized constant DetermineIfPrime::Prime 我尝试了其他方法来完成这项工作，但我认为这是我能得到的最接近的方法。 我也试过这个： class DetermineIfPrime def initialize (nth_value) @nth_value = nth_value primetest end def […]

Ruby中字符串字典中的快速模糊/近似搜索

我有一个50K到100K字符串的字典（最多可以有50多个字符），我试图找到给定字符串是否在字典中具有一些“编辑”距离容差。 （例如Levenshtein）。 在进行搜索之前，我很好地预先计​​算任何类型的数据结构。 我的目标是尽可能快地对该字典运行数千个字符串并返回最近的邻居。 我会很好的只是得到一个布尔值，说明一个给定是否在字典中，如果有一个明显更快的算法这样做 为此，我首先尝试计算所有Levenshtein距离并采取最小值，但显然非常慢。 所以我尝试在这篇文章的基础上实现Levenshtein Trie http://stevehanov.ca/blog/index.php?id=114 请参阅我的要点，重现基准： https ： //gist.github.com/nicolasmeunier/7493947 以下是我在机器上的一些基准测试： 编辑距离0（完美匹配） Benchmark.measure { 10.times { dictionary.search(random_word, 0) } } * 编辑距离2，变得慢很多* Benchmark.measure { 10.times { dictionary.search(random_word, 2) } } 它从那里走下坡路，并且编辑距离大于2时变得非常慢。（每个测试字符串的平均值超过1秒）。 我想知道如何/如果我可以显着加快这一点。 如果已经在ruby / gem中实现了现有解决方案，我也不想重新发明轮子…… 编辑1：在我的情况下，我希望我与字典匹配的大多数字符串不在那里。 因此，如果有任何算法可以快速丢弃字符串，那可能会有所帮助。 谢谢，尼古拉斯

解决依赖性约束

我有一个经典的依赖性解决问题。 我以为我朝着正确的方向前进，但现在我遇到了障碍，我不知道该怎么办。 背景 在已知的Universe（所有工件的缓存及其依赖关系）中，每个工件和版本之间都存在1-> n关系，并且每个版本可能包含一组不同的依赖关系。 例如： A 1.0.0 B (>= 0.0.0) 1.0.1 B (~> 0.1) B 0.1.0 1.0.0 给定一组“需求约束”，我想找到最好的解决方案（“最佳”是仍然满足所有约束的最高版本）。 以下是解决方案的“需求约束”示例： solve!(‘A’ => ‘~> 1.0’) #=> {“A” => “1.0.1”, “B” => “0.1.0”} 实际上，有更多的要求： solve!(‘A’ => ‘~> 1.0’, ‘B’ => ‘>= 0.0.0’, ‘C’ => ‘…’, ‘D’ => ‘…’) （版本遵循语义版本标准） 我试过了 当前的解决方案使用回溯并且性能不高。 我做了一些挖掘，发现由于宇宙的大小导致了性能问题。 我决定尝试一种替代方法，并针对一组需求构建“可能性”DAG图： class Graph def initialize […]

解决ruby中的旅行商问题（50多个地点）

我在一家快递公司工作。 我们目前通过“手”解决了50多个地点的路线。 我一直在考虑使用谷歌地图API解决这个问题，但我已经读到有24点的限制。 目前我们在服务器中使用rails，所以我正在考虑使用ruby脚本来获取50多个位置的坐标并输出合理的解决方案。 你会用什么算法来解决这个问题？ Ruby是一种很好的编程语言来解决这类问题吗？ 你知道任何现有的ruby脚本吗？

趋势算法

我正在开发各种微型论坛，由特殊用户发布一个快速（接近推文大小）的主题消息，订阅者可以使用他们自己的大小相同的消息进行响应。 直截了当，没有“挖掘”或任何forms的投票，只是按时间顺序排列每个主题消息的响应。 但预计会有高流量。 我们希望根据他们使用0到10的等级的响应动态来标记主题消息。 谷歌搜索趋势算法和开源社区应用程序示例已有一段时间了，到目前为止已经收集了两个有趣的参考资料，我还没有完全理解： 了解用于衡量趋势的算法，使用基线趋势算法比较维基百科综合浏览量的讨论，此处为SO。 布兰妮斯皮尔斯问题 ，一篇关于如何在处理大量数据流时对搜索术语进行排名的深入文章。 从第一次开始，我理解需要检查活动的斜率，并平衡两个活动规模差异很大的项目之间的权重。 但是，我如何比较许多项目，随着时间的推移迅速增加？ 然后，如何将“嗡嗡声等级”中的项目从0分到10分？ 第二个参考是令人着迷的，但在这一点上我的头脑。 从第一遍开始，我了解到需要保持内存使用的稳定性，同时保留计数器并在必要时存储对项目的引用。 但我还没有为我的具体用例找到合适的算法。 值得注意的是，我来自非计算机科学和非统计学背景。 请耐心等待:)任何帮助和代码示例（特别是在Ruby中）将不胜感激。

使用Ruby，使哈希值通过它们的值找到彼此

我在这个数组中有几个time_tables 。 有四个time_tables通过start_location – end_location和start_date – end_date以线性方式相互关联。 当第一个time_table结束时，另一个time_table开始，依此类推。 我的代码： arr = [ { name: 01, start_date: ‘2014-04-24 22:03:00’, start_location: ‘A’, end_date: ‘2014-04-24 22:10:00’, end_location: ‘B’ }, { name: 05, start_date: ‘2014-04-24 22:10:00’, start_location: ‘C’, end_date: ‘2014-04-24 23:10:00’, end_location: ‘D’ }, { name: 01, start_date: ‘2014-04-24 17:10:00’, start_location: ‘X’, end_date: ‘2014-04-24 20:10:00’, end_location: ‘B’ }, { […]

在不使用ruby中的循环的情况下反转数组

我有一个编码挑战来反转一个包含5个元素的数组。 如果不使用反向方法，我该怎么做？ 码： def reverse(array) array end p reverse([“a”, 1, “apple”, 8, 90])

需要帮助最大化多个相似对象中的3个因素并进行适当排序

我需要用任何语言编写算法，根据3个因素对数组进行排序。 我以度假村为例（如Hipmunk）。 假设我想去度假。 我想要最便宜的地方，最好的评论和最吸引人的地方。 但是，显然我无法在所有3中找到＃1。 示例（假设有20个重要景点）： 度假村 – 答：150美元/晚… 98/100在有利的评论… 20个景点中的18个 度假村B：99美元/晚… 85/100在有利的评论… 20个景点中的12个 度假村C：120美元/晚… 91/100在有利的评论… 20个景点中的16个 度假村B看起来价格最具吸引力，但在其他两个类别中排名第三。 其中，我可以选择度假村C每晚只需21美元，并获得更多的景点和更好的评论。 价格对我来说仍然很重要，但是A度假村拥有出色的评价和众多景点：价值51美元的奢侈品值多少钱吗？ 我希望能够填充一个列表，从“从最好到最差”点亮（我引用bc对消费者来说是主观的）。 我如何最大化每个度假村的价值？ 我应该为每个因素设置一个权重（即：55％的价格，30％的评论，15％的设施）并得到一组数字的结果并按照这种方式订购？ 我是否需要所有酒店的模式，中位数和范围并确定平均价格，并且平均价格附近的酒店是否保持最重？ 如果有点混乱，请访问www.hipmunk.com。 他们有一种飞机排序他们称之为痛苦（和我的问题相似的酒店类型），他们将其作为自己使用。 我以度假村为例让我的问题更有意义。 如何将数学运用于这样的问题？

生成适合Ruby中概率分布的数字数组？

假设我有100条记录，我想模拟created_at日期，以便它适合某些曲线。 有没有图书馆可以做到这一点，或者我可以使用什么公式？ 我认为这是沿着同样的轨道： 用概率分布生成随机数 我不太了解它们是如何归类于数学的，但我看的是： 钟形曲线 对数（典型的生物学/进化）曲线？ … 只是在代码中寻找一些公式，所以我可以这样说： 给出100条记录，1周的时间跨度，以及12 12.hours的间隔 为每条记录设置created_at ，使其大致适合curve 非常感谢！ 更新 我发现这个关于ruby算法的论坛post ，这让我看到了rruby ，一个R / Ruby桥，但这看起来太多了。 更新2 我写了这个小片段试用了gsl库，到了那里…… 在Rails中生成测试数据，其中created_at沿统计分布

编程技巧：如何创建一个简单的纸牌游戏

当我学习Ruby语言时，我越来越接近实际的编程。 我在想创造一个简单的纸牌游戏。 我的问题不是面向Ruby，但我确实想知道如何用真正的OOP方法解决这个问题。 在我的纸牌游戏中，我希望有四个玩家，使用标准牌组，52张牌，没有笑话/通配符。 在游戏中，我不会将ace用作双卡，它始终是最高卡。 所以，我想知道的编程问题如下： 我怎样才能对卡片组进行分类/随机化？ 有四种类型，每种类型有13个值。 最终可能只有唯一值，因此选择随机值可能会生成重复值。 如何实现简单的AI？ 由于有大量的纸牌游戏，有人会想出这部分，所以参考会很棒。 我是一个真正的Ruby nuby，我的目标是学习解决问题，所以伪代码会很棒，只是为了理解如何以编程方式解决问题。 如果不清楚，我为我的语法和写作风格道歉，因为它不是我的母语。 此外，指向解释此类挑战的网站的指针将是一个很好的资源！ 感谢您的意见，解答和反馈！