Tag: 算法

一组超过2个整数的最大公约数: Stack Overflow上有几个问题讨论如何找到两个值的最大公约数。一个好的答案显示了一个简洁的递归函数来做到这一点。但是如何找到一组超过2个整数的GCD？我似乎无法找到这样的例子。任何人都可以建议最有效的代码来实现这个function吗？ static int GCD(int[] IntegerSet) { // what goes here? }

在C＃中，在算法中使用递归函数是一种好习惯吗？: 在许多使用递归的函数语言中被认为是一种很好的实践。我认为这很好，因为编译器优化了函数式语言的代码。但是在创建算法时，在C＃中使用递归是一种好习惯吗？就C＃而言，是否正确，递归算法将导致您的堆栈增长非常显着（如果调用量非常大）并且这根本不会快，并且可能导致堆栈溢出。或者还有一些优化可以使递归函数高效？如果您在使用函数语言中的递归和C＃的算法之间进行一些比较（速度，内存，可读性），我将不胜感激。

算法：里程表/蛮力: 我想用C＃风格的语言编写类似里程表的方法，但不仅仅是使用0-9表示字符，而是使用任何字符集。它或多或少会像蛮力的应用程序。如果我传入一个从0到J的字符数组，并将长度设置为5，我想要的结果如00000,00001,00002 …… HJJJJ，IJJJJJ，JJJJJ 。这是基地，请帮我扩展： protected void Main() { char[] chars = new char[] { ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’, ‘I’, ‘J’ }; BruteForce(chars, 5); } private void BruteForce(char[] chars, int length) { // for-loop (?) console-writing all possible combinations […]

冒泡排序最坏的例子是O（n * n），怎么样？: 我正在尝试冒泡排序。有5个元素，数组未排序。泡沫排序的最坏情况是O（n ^ 2）。作为我正在使用的例子 A = {5,4,3,2,1} 在这种情况下，比较应该是5 ^ 2 = 25.使用手动validation和代码，我得到比较计数为20.以下是冒泡排序实现代码 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SortingAlgo { class Program { public static int[] bubbleSort(int[] A) { bool sorted = false; int temp; int count = 0; int j = 0; while (!sorted) { j++; sorted = true; […]

今日热门，本周，本月 – 设计模式: 我有一个系统显示按三个字段之一排序的条目，最受欢迎的今天，本周和本月。每次查看条目时，分数增加1，从而改变顺序。因此，如果条目1是新的并且今天被观看10次，其分数将是： Today: 10 Week: 10 Month: 10 当前的解决方案目前我只有3个与每个条目相关联的字段，一个用于本周的另一个用于本周，另一个用于本月。每次查看条目时，所有三个分数都会增加1。在一天结束时，将日分数重置为0.在当前周结束时，将周分数设置为0，并且在当前日历月结束时，将月分数设置为0。问题虽然这种方法有用并占用空间很小，但由于两个原因，它并不理想： 1）在当前时段（日，周，月）结束时，该值一次性重置为0，这意味着每天00:00:00排名全部重置，所有每日分数都设置为0，在本周末和月末也是如此。在每个月1日的00:00:00，所有分数被设置为0，从而丢失所有现有的排名数据。 2）因为月末通常在一周内（周一至周日），所以每周的分数在一周内被重置，导致每周分数高于每月分数。可能解决方案我可以使用每小时每小时的滚动小时计数器，用于根据当前小时指数计算当前日，周，月的分数。 Array size = 31 * 24 = 744 int16 values 所以在1日凌晨4点，视图将在几个小时内放置[4] hours[4]++ 然后，统计计算器将使用今天作为最后24个值的总和，并且本周分数将是最后（24 * 7）值的总和。最后，本月将是最后（24 * 31）值的总和。解决问题解决方案1的主要问题是磁盘/内存要求。我已经从当前解决方案中的3个32位值变为使用744个32位值。即使我将它们改为in16，我仍然会在每个条目中使用更多的内存 Memory per Entry = 3 * 4 bytes = 12 bytes (Existing) Memory […]

关系的数据结构: 我正在将VB6转换为C＃，我希望使我的数据结构更有效地保持值和关系。在VB中，我有一组值和另一组关系，这些值与这些关系的优先级相关。我还有一个算法，当一组值传递给它时，返回将这些值连接在一起所需的所有关系。例如，假设值集合包含1-10并且关系集合包含 1,2 3,2 5,2 2,8 8,10 9,10 如果输入是1,9,10，则返回的关系将是 – 1,2 2,8 8,10 9,10 由于可能存在多条路径，因此会返回最少量的关系，但需要注意关系优先级。如果关系具有更高的优先级，则将添加该关系，并且将从那里添加其余关系。我正在考虑使用Disjoint-set数据结构，但我不确定。有任何想法吗？更多信息 – 值的数量通常小于100且关系小于500.集合是静态的，并且将一次又一次地使用算法来查找路径。另外，我没有问这个问题，但是Disjoint-set数据结构中的算法是否最有效？

用于确定语句/文本的正面或负面的算法: 我需要实施情绪分析。有人能指出我的示例/参考实现吗？

生成具有一定最大值的均匀随机整数: 我想生成满足0 <= result <= maxValue统一整数。我已经有一个生成器，它在内置的无符号整数类型的整个范围内返回统一值。让我们调用这个byte Byte()的方法byte Byte() ， ushort UInt16() ， uint UInt32()和ulong UInt64() 。假设这些方法的结果是完全一致的。我想要的方法的签名是uint UniformUInt(uint maxValue)和ulong UniformUInt(ulong maxValue) 。我在找什么：正确性我更喜欢在给定的时间间隔内分配返回值。但如果显着提高性能，则可以接受非常小的偏差。我的意思是指一个订单的偏差，允许区分符的概率为2/3给定2 ^ 64个值。它必须适用于任何maxValue 。性能该方法应该很快。效率该方法确实消耗很少的原始随机性，因为取决于底层生成器，生成原始字节可能是昂贵的。浪费几个比特很好，但消耗128比特来生成一个数字可能是过多的。在某些成员变量中，还可以缓存前一次调用中的一些遗留随机性。小心int溢出和包装行为。我已经有了一个解决方案（我会将其作为答案发布），但这对我的口味来说有点难看。所以我想获得更好的解决方案的想法。关于如何使用大型maxValue进行unit testing的建议也不错，因为我无法生成具有2 ^ 64个桶和2 ^ 74个随机值的直方图。另一个复杂因素是，对于某些错误，只有一些maxValue发行版有很多偏见，而其他发行版只有很小的偏差。

比较两个谱图以找到它们匹配算法的偏移量: 我每天从互联网上录制2分钟的电台广播。始终有相同的开始和结束的叮当声。由于无线电广播的准确时间可能差不多6分钟，我必须录制大约15分钟的收音机。我想确定这些歌曲在15分钟录音中的确切时间，所以我可以提取我想要的音频部分。我已经启动了一个C＃应用程序，我将MP3解码为PCM数据并将PCM数据转换为基于http://www.codeproject.com/KB/audio-video/SoundCatcher.aspx的频谱图我尝试在PCM数据上使用交叉相关算法，但算法在6分钟左右非常慢，步长为10毫秒，有时无法找到叮当开始时间。任何比较两个谱图匹配算法的想法？或者更好的方法来找到叮当开始时间？谢谢，更新，抱歉延误首先，感谢所有的主人，他们大多数都是相关的或有趣的想法。我试图实现fonzo提出的Shazam算法。但未能检测到频谱图中的峰值。这是来自三个不同记录的起始叮当的三个频谱图。我尝试使用blobfilterAForge.NET（但它无法识别峰值），模糊图像并检查高度差异，拉普拉斯卷积，斜率分析，检测一系列垂直条纹（但是有太多错误正）… 同时，我尝试了Dave Aaron Smith提出的Hough算法。我在哪里计算每列的RMS。是的是每列，它是O（N * M）但是M << N（注意一列是大约8k的样本）。所以整体而言并不是那么糟糕，算法大约需要3分钟，但绝不会失败。我可以选择那个解决方案，但如果可能的话，我更喜欢Shazam因为它是O（N）并且可能更快（也更冷）。因此，你们中的任何一个人都知道一种算法可以始终检测这些光谱图中的相同点（不一定是峰值），这要归功于添加注释。新的更新最后，我使用上面解释的算法，我尝试实现Shazam算法，但未能在频谱图中找到适当的峰值，从一个声音文件到另一个声音文件不一致的识别点。从理论上讲，Shazam算法是解决这类问题的方法。 Dave Aaron Smith提出的Hough算法更稳定有效。我分割了大约400个文件，其中只有20个未能正确分割。磁盘空间从8GB到1GB。谢谢你的帮助。

BSP地牢生成的简单例子: 我原本试图按照这个算法在C＃中创建一个简单的roguelike地牢。但我想我太傻了，因为我的结果总是出现乱七八糟的垃圾。然后我切换到我自己的算法，这会产生不太好但半可识别的地牢结果。有没有人有任何以BSP方式进行此操作的示例，如链接文章中所述？如果它不受一堆游戏细节/图书馆电话的阻碍，那将是最好的，因为（再次）我是愚蠢的。（如果你特别自虐并希望我发布我的代码，我可以，但我认为这对于一个SO问题太过分了。）