Tag: algorithm

这是一个“足够好”的随机algorithm; 为什么不使用，如果它更快？

我做了一个叫做QuickRandom的类，它的工作就是快速生成随机数。 这非常简单：只取旧的值，乘以一个double ，取小数部分。 这是我的QuickRandom类的完整： public class QuickRandom { private double prevNum; private double magicNumber; public QuickRandom(double seed1, double seed2) { if (seed1 >= 1 || seed1 < 0) throw new IllegalArgumentException("Seed 1 must be >= 0 and < 1, not " + seed1); prevNum = seed1; if (seed2 <= 1 || seed2 > 10) throw […]

这个游戏背后的math/计算原理是什么？

我的孩子们有这个有趣的游戏叫Spot It！ 游戏的限制（我可以描述的最好的）是： 这是一副55张牌 在每张卡上有8张独特的照片（即一张卡不能有2张相同的照片） 鉴于从甲板上select的任何2张卡，有1个，只有1个匹配的图片 。 匹配的图片可能在不同的卡片上有不同的缩放比例，但这只是为了让游戏变得更加困难（即小树仍然匹配更大的树） 游戏的原理是：翻转2张牌，谁先挑选匹配的图片得到一个点。 这是澄清的图片： （例如：从上面两张卡片可以看出，匹配的图片是绿色的恐龙，在右下angular和中间的图片之间，这是一个小丑的头）。 我想了解以下内容： 满足这些标准所需的不同图片的最小数量是多less？您如何确定？ 使用伪代码（或Ruby），你将如何从N张图片（其中N是问题1中的最小数字）中生成55张游戏卡？ 更新： 每张卡片的确出现两次以上（与一些猜测相反）。 看到这张3张卡片，每个都有一个闪电：

就地基数sorting

这是一个长文本。 请多多包涵。 下来，问题是： 是否有一个可行的就地基数sortingalgorithm ？ 初步 我有很多小的固定长度的string，只使用我想分类的字母“A”，“C”，“G”和“T”（是的，你猜对了）。 目前，我使用std::sort ，它在STL的所有常见实现中使用introsort 。 这工作得很好。 不过，我确信基数sorting完全适合我的问题，在实践中应该更好。 细节 我已经用非常幼稚的实现来testing这个假设，对于相对较小的input（大约为10,000），这是真实的（至less是两倍以上）。 但是，当问题规模变大（ N > 5,000,000）时，运行时间会严重恶化。 原因很明显：基数sorting需要复制整个数据（实际上我的幼稚实现不止一次）。 这意味着我已经将〜4 GiB放入了我的主内存，这显然会导致性能下降。 即使没有，我也不能使用这么多的记忆，因为问题的规模实际上变得更大了。 用例 理想的情况下，这个algorithm应该适用于DNA和DNA5（它允许一个额外的通配符“N”），甚至是带有IUPAC 模糊代码的 DNA（导致16个不同的值）。 但是，我意识到所有这些情况都不能被覆盖，所以我对任何速度的改善感到满意。 代码可以dynamic地决定分派给哪个algorithm。 研究 不幸的是， 关于基数sorting的维基百科文章是无用的。 关于就地变体的部分是完整的垃圾。 基数sorting的NIST-DADS部分几乎不存在。 有一种看起来很有前途的论文，称为高效自适应就地基sorting ，它描述了“MSL”algorithm。 不幸的是，这篇论文也令人失望。 具体来说，有以下几点。 首先，该algorithm包含几个错误，并留下很多原因。 特别是，它没有详细说明recursion调用（我简单地假设它递增或减less一些指针来计算当前的移位和掩码值）。 而且，它使用函数dest_group和dest_address而不给定义。 我没有看到如何有效地实现这些（即在O（1）;至lessdest_address是不平凡的）。 最后但并非最不重要的是，该algorithm通过将数组索引与input数组内的元素交换来实现就地性。 这显然只适用于数值数组。 我需要在string上使用它。 当然，我可以拧紧打字，然后继续前进，假设内存将容忍我存储一个不属于它的索引。 但是，只要我能把我的string压缩到32位内存（假设是32位整数），这个工作就行得通。 那只有16个字符（让我们暂且忽略16> log（5,000,000））。 其中一位作者的另一篇论文根本没有给出准确的描述，但是它使得MSL的运行时呈现出平坦的错误。 回顾一下 ：有没有希望find一个工作的参考实现，或至less有一个良好的伪代码/描述工作在地方基数sorting的DNAstring？

是否有可能获得一个函数的所有参数作为该函数内的单个对象？

在PHP中有func_num_args和func_get_args ，有没有类似的JavaScript？

什么是循环不变式？

我正在阅读“algorithm简介”CLRS。 作者在第2章（插入sorting）中讨论了循环不variables。 我不知道这意味着什么。

什么时候可以使用DFS vs BFS？

我了解DFS（深度优先search）和BFS（广度优先search）之间的差异，但是我有兴趣知道什么时候使用它们更实用？ 任何人都可以举例说明DFS如何超越BFS，反之亦然？

把最胖的人从一架超载的飞机上抛下。

假设你有一架飞机，而且燃油很低。 除非飞机降低了3000磅的乘客重量，否则将无法到达下一个机场。 为了节省最多的生命，我们首先要把最重的人从飞机上抛下。 噢，飞机上有数百万人，我们希望有一个最佳的algorithm来find最重的乘客，而不必对整个列表进行sorting。 这是我试图用C ++编码的代理问题。 我想按重量对乘客舱单做一个“partial_sort”，但是我不知道我需要多less元素。 我可以实现我自己的“partial_sort”algorithm（“partial_sort_accumulate_until”），但我想知道是否有更简单的方法来使用标准的STL来做到这一点。

在日历应用程序中为循环事件build模的最佳方式是什么？

我正在构build一个需要支持周期性事件的组日历应用程序，但是我提出的处理这些事件的所有解决scheme看起来都像是黑客攻击。 我可以限制一个人看起来多远，然后一次生成所有事件。 或者我可以将事件存储为重复，并在日历上向前看dynamic显示，但如果有人想要更改事件的特定实例的细节，则必须将其转换为正常事件。 我相信有更好的方法来做到这一点，但我还没有find它。 模拟周期性事件的最佳方式是什么？您可以在哪里更改或删除特定事件实例的详细信息？ （我正在使用Ruby，但是请不要让这个限制你的答案，如果有一个特定于Ruby的库或者其他东西，那么这很好理解）。

最快的方法来sorting10个数字？ （数字是32位）

我正在解决一个问题，它涉及很快sorting10个数字（int32）。 我的应用程序需要尽可能快地sorting10百万次。 我正在抽样数十亿个元素的数据集，每次我需要从中select10个数字（简化）并对它们进行sorting（并从sorting后的10个元素列表中作出结论）。 目前我正在使用插入sorting，但我想我可以实现一个非常快速的自定义sortingalgorithm为我的具体问题的10个数字将击败插入sorting。 有没有人有任何想法如何解决这个问题？

给定一个数字，find与原始数字具有完全相同的一组数字的下一个更高的数字

我只是轰炸了面试，在面试问题上几乎没有什么进展。 任何人都可以让我知道如何做到这一点？ 我尝试在网上search，但找不到任何东西： 给定一个数字，find与原始数字具有完全相同的一组数字的下一个更高的数字。 例如：给出38276回报38627 我想从find第一个数字（从右边）的索引开始，这个索引小于那个数字。 然后，我将旋转子集中的最后一个数字，使得它是由相同数字组成的下一个最大数字，但是卡住了。 面试官还build议一次换一个数字，但是我不知道algorithm，只是盯着屏幕20-30分钟。 不用说，我想我将不得不继续寻找工作。 编辑：为了什么值得，我被邀请参加下一轮采访