Tag: 算法

编辑距离矩阵

我正在尝试构建一个程序,它需要两个字符串并填充它们的编辑距离矩阵。 绊倒我的是,对于第二个字符串输入,它正在跳过第二个输入。 我尝试用getch()清除缓冲区,但它没有用。 我也尝试过切换到scanf(),但这也导致了一些崩溃。 请帮忙! 码: #include #include int min(int a, int b, int c){ if(a > b && a > c) return a; else if(b > a && b > c) return b; else return c; } int main(){ // allocate size for strings int i, j; char *input1 = (char*)malloc(sizeof(char)*100); char *input2 = […]

大数阶因数模数大素数

我需要计算一个大数的阶乘(<= 1.000.000),我需要结果模1000000007.我写了以下内容,但它在运行时生成错误(test.exe已停止工作)。 它仅适用于小数字。 long long unsigned modulo(long long unsigned nr){ return nr % 1000000007; } long long unsigned fact(long long unsigned nr){ if(nr)return modulo(nr * fact(nr – 1)); else return 1; } 更新1: long long unsigned fact(long long unsigned nr){ long long unsigned r = nr; while(–nr){ r = modulo(r * nr); } return r; […]

我们怎样才能找到数组中最重要的元素?

使用数据结构自平衡二叉搜索树查找数组中第n个最小/最大元素的算法 阅读post: 以最佳方式在二叉搜索树中查找第k个最小元素 。 但正确的答案并不清楚,因为我无法弄清楚正确答案,我拿了一个例子……请多说明一点……

什么是C的质量图库?

我正在写一些C,我需要将一个非常大的图存储为邻接矩阵。 我打算破解一个快速的图形实现,但是想先问一下人们喜欢的C(不是c ++)是否有任何好的图形库。 我将以某种标准格式导入图形(可能是GML,但这不是成败要求),将其存储为邻接矩阵,然后进行一些计算。 有什么想法吗? 谢谢! 编辑:作为一个FYI,我根本没兴趣绘制图表

计算未排序数据中唯一对的数量和非唯一对的实例

我有以下forms的数据: ID ATTR 3 10 1 20 1 20 4 30 … … 其中ID和Attr未排序且可能包含重复项。 ID的范围是1-20,000左右,ATTR是unsigned int。 我需要在一次处理100,000到500,000对之间的任何地方。 我在寻找: 唯一对的数量。 弹出非唯一对的次数。 所以在上面的数据中,我想知道(1,20)出现两次,并且有3个独特的对。 我目前正在使用我的天真方法中的哈希表。 我保留一个唯一对的计数器,如果我插入的项目已经存在,则递减计数器。 我还保留了一组非唯一对的ID。 (所有初次见面时) 性能和尺寸大致相同。 考虑到性能和尺寸问题,我实际上可以获得相对较高(假设为0.5%)的误报率。 (我也使用频谱绽放实现了这个) 我不那么聪明,所以我确信那里有更好的解决方案,我想听听你最喜欢的哈希表实现/任何其他想法。 🙂

如果只给出整个数据的CRC32,是否可以找到前缀的CRC32?

我必须在表中进行查找,并且我有一个字符串标识符和字符串的CRC32。 如果有未命中,我必须减小大小并查找标识符的前缀。 因此,我需要计算前缀的校验和,并为每个前缀重复该过程。 我的这个算法的C代码是这样的: find_prefix(char* string, uint16_t size, uint32_t crc, hash_table_t *hash_table){ do{ if(perform_lookup(string, size, crc, hash_table)==HIT){ return size; } size–; crc=calculate_crc(string, size, 0xFFFFFFFF); //Is there a better way? } while(size); } 我的问题是:在给定整个字符串的crc和字符串本身的情况下,我可以避免crc计算并派生前缀的crc吗? 我在这里和这里找到了一些相关的问题,但是我有一个约束:当表格被普遍填充时,标识符的crc是用硬件计算的,所以我不能修改算法,并且这两个链接提供了不同的答案计算校验和的方法(基本上使用所有组件的XOR)。 非常感谢你。

Regula-Falsi算法?

我正在尝试实现Regula-Falsi算法来解决2(x^3)-x-2的等式,但问题是变量c值保持不变并且它没有改变,即使我的代码应该改变它。 #include #include float fonc(float x) { int result; result=2*(pow(x,3))-x-2; return result; } int main(void) { float eps=pow(10,-4); int i=0; float a,b,c; a=1; b=2; do { c=((a*fonc(b))-(b*fonc(a)))/((fonc(b)-fonc(a))); if(fonc(c)*fonc(a)eps); printf(“le nombre d’itération %d”,i); }

算法设计手册,第3章,链表代码片段混淆

我正在阅读算法设计手册,在第3章中,出现以下代码片段。 它与从链表中删除项目有关。 问题与数据结构无关,而是与我认为声明了两个变量的单行代码有关。 为简洁起见,我删除了代码中不相关的部分。 list *search_list(list *l, item_type x) { // This function just searches the list x } list *predecessor_list(list *l, item_type x) { // This function simply returns the predecessor of x or NULL } delete_list(list **l, item_type x) { list *p; /* item pointer */ list *pred; /* predecessor pointer */ list […]

在C中有替代strtoull()函数吗?

我需要将char*转换为unsigned long long int并且在C标准库中有一个名为strtoull()的函数,但它需要很长时间。 我需要在char*和unsigned long long int之间快速转换。 如何编写比标准转换function更快的转换function?

用C / C ++中的周数计算公历日期

我正在使用格里高利历,我想实施IS0 8601周,但我偶然发现了计算任何周数的日期的问题。 例如,ISO日期2010-W01-1应该返回2010 2009-W01-1 1月4日 , 2009-W01-1应该返回2008年12月29日 。 // Get the date for a given year, week and weekday(1-7) time_t *GetDateFromWeekNumber(int year, int week, int dayOfWeek) { // Algorithm here } 编辑:我还没有找到任何在线工作的算法,尝试了很多,但我现在有点卡住了。