Tag: 算法

生成反向位查找表（8位）背后的算法

我在这里找到了查找表。 该表生成为8位的反向位表。 我无法弄清楚它为何起作用。 请解释它背后的理论。 谢谢 static const unsigned char BitReverseTable256[256] = { # define R2(n) n, n + 2*64, n + 1*64, n + 3*64 # define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) # define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 ) R6(0), […]

如何仅使用Push，Pop，Top，IsEmpty，IsFull对堆栈进行排序？

给定堆栈S，需要仅使用Push ， Pop ， Top ， IsEmpty ， IsFull对堆栈进行排序。 寻找最简单的解决方案。 编辑：删除到位条件。 无法使用其他堆栈或队列。

如何在c或c ++中创建异构链接列表

一个可以保存浮点数，整数，字符等数据和算法的链接列表应该很好而且不是很复杂 我想到了创建一个带有void指针的结构，它将指向后续节点。 但问题是我不能使用带结构的模板。 下到c，我必须测试用户输入的每个字符，以测试它是否是整数，浮点数或字符。然后我们可以进一步 请建议一个有效的算法/代码

在C中随机化一个字符串

我试图在C中生成一个80个字符的固定字符串的随机排列。令我沮丧的是，我正在研究的系统缺乏strfry（）。 对我来说，生成此字符串的随机排列的最佳方法是什么？ 因为这将循环约。 100,000次，性能是一个问题。

找到时间为O（n）且空间为O（1）的有符号整数

（这是一个概括： 在O（n）时间和O（1）空间中查找重复项 ） 问题：分别编写具有O（n）和O（1）的时间和空间复杂度的C ++或C函数，它们在给定数组中找到重复整数而不改变它。 示例：给定{1,0，-2,4,4,1,3,1，-2}函数必须打印1，-2和4一次（按任意顺序）。 编辑：以下解决方案需要在数组的最小值到最大值范围内的每个整数的二进制位（表示0,1和2）。 必要字节数（不管数组大小）永远不会超过(INT_MAX – INT_MIN)/4 + 1 。 #include void set_min_max(int a[], long long unsigned size,\ int* min_addr, int* max_addr) { long long unsigned i; if(!size) return; *min_addr = *max_addr = a[0]; for(i = 1; i < size; ++i) { if(a[i] *max_addr) *max_addr = a[i]; } } void print_repeats(int a[], […]

把while循环变成数学方程式？

我在我的程序中有两个简单的while循环，我觉得应该是数学方程，但我很难转换它们： float a = someValue; int b = someOtherValue; int c = 0; while (a = b / 2) { c++; a -= b; } 这段代码按原样运行，但我觉得它可以简化为数学方程式。 这里的想法是这个代码采用偏移量（someValue）并调整坐标（c）以最小化距瓷砖中心的距离（大小为someOtherValue）。 任何帮助，将不胜感激。

如何在动态图中避免“堆指针意大利面”？

一般问题 假设您正在编写一个由图形组成的系统，以及可以根据相邻节点的配置激活的图形重写规则。 也就是说，您有一个在运行时期间无法预测地增长/缩小的动态图形。 如果你天真地使用malloc ，新的节点将被分配在内存中的随机位置; 经过足够的时间，你的堆将成为指针意大利面，给你可怕的缓存效率。 是否有任何轻量级的增量技术可以使连接在一起的节点在内存中保持紧密联系 ？ 我尝试了什么 我唯一能想到的是将节点嵌入笛卡尔空间，并使用一些物理弹性模拟来排斥/吸引节点。 那将有线节点保持在一起，但看起来很傻，我想模拟的开销会比缓存效率加速更大。 坚实的例子 这是我正在尝试实施的系统。 这是我试图在C中优化的代码的简短片段。 这个 repo是JS中的原型，工作实现，具有可怕的缓存效率（以及语言本身）。 该video以图形方式显示系统的运行情况。

通过已知索引重新调整，聚集，分散对数组进行缓存友好复制

假设我们有一个数据数组和另一个带索引的数组。 data = [1, 2, 3, 4, 5, 7] index = [5, 1, 4, 0, 2, 3] 我们想要从index位置的data元素创建一个新数组。 结果应该是 [4, 2, 5, 7, 3, 1] 朴素算法适用于O（N），但它执行随机存储器访问。 你能建议具有相同复杂性的CPU缓存友好算法吗？ PS在我的特定情况下，数据数组中的所有元素都是整数。 PPSarrays可能包含数百万个元素。 PPPS我可以使用SSE / AVX或任何其他x64特定的优化

如何在C或C ++中编写简单的正则表达式模式匹配函数？

这是我今天的论文测试中的一个问题，函数签名是 int is_match(char* pattern,char* string) 该模式仅限于ASCII字符和量化*和? ，所以它相对简单。 如果匹配则is_match应返回1，否则返回0。 我该怎么做呢？

设置协调算法的实现

我正在寻找集合协调算法的实现。 问题在于：有两个集合，其中元素由位于不同机器上的一些相对紧凑的值（例如UUID或MD5 / SHA1 /任何散列）标识。 这些集合在相对较少的元素中有所不同，我希望在传输最少量的数据时同步这些集合。 大多数谷歌搜索引领这里 。 这是GPL实施的似乎是最先进的任务方法。 问题是我不能在我的应用程序中使用GPL代码。 我很可能必须使用像nzmath这样的东西重新实现它，但也许还有其他实现（最好是Python或C / C ++），或者还有其他更好的算法？