Tag: 算法
找到平均值的更好算法
我正在编写一本关于C的编程书A Book 。 练习建议找到一组数字的平均值，算法： avg += (x – avg) / i; 比以下更好： sum += x; avg = sum / i; ‘x’是用于存储输入数字的变量。 它还建议除了防止溢出之外，第一个算法确实比第二个algorthim有其他一些好处，任何人都可以帮助我吗？ 谢谢！
这个数组比较问题的最佳算法是什么？
解决以下问题的速度算法最有效的是什么？ 给定6个arrays，D1，D2，D3，D4，D5和D6，每个包含6个数字，如： D1[0] = number D2[0] = number …… D6[0] = number D1[1] = another number D2[1] = another number …. ….. …. …… …. D1[5] = yet another number …. …… …. 给定第二个数组ST1，包含1个数字： ST1[0] = 6 给定第三个数组ans，包含6个数字： ans[0] = 3, ans[1] = 4, ans[2] = 5, ……ans[5] = 8 使用数组D1，D2，D3，D4，D5和D6的索引，从0到存储在ST1 [0]中的数字减1，在本例6中，从0到6-1，将ans数组与每个D数组进行比较。 如果在相同索引处的任何D中找不到一个或多个ans数，则结果应为0，如果在相同索引处的某个D中找到所有ans数，则结果应为1。 也就是说，如果某些ans [i]不等于任何D […]
排序数组的最快搜索方法是什么？
回答另一个问题 ，我编写了下面的程序来比较排序数组中的不同搜索方法。 基本上我比较了插值搜索和二分搜索的两种实现。 我通过计算不同变体所花费的周期（使用相同的数据集）来比较性能。 但是我确信有一些方法可以优化这些function，使它们更快。 有没有人对如何更快地使这个搜索function有任何想法？ 使用C或C ++的解决方案是可以接受的，但我需要它来处理具有100000个元素的数组。 #include #include #include #include #include static __inline__ unsigned long long rdtsc(void) { unsigned long long int x; __asm__ volatile (“.byte 0x0f, 0x31” : “=A” (x)); return x; } int interpolationSearch(int sortedArray[], int toFind, int len) { // Returns index of toFind in sortedArray, or -1 if not […]
随机置换单链表的N个第一个元素
我必须随机地置换长度为n的单链表的N个第一个元素。 每个元素定义为： typedef struct E_s { struct E_s *next; }E_t; 我有一个根元素，我可以遍历整个大小为n的链表。 什么是最有效的技术来随机置换N个第一个元素（从根开始）？ 因此，给定a-> b-> c-> d-> e-> f – > … x-> y-> z我需要制作smth。 像f-> a-> e-> c-> b – > … x-> y-> z 我的具体案例： nN相对于n约为20％ 我有限的RAM资源，最好的算法应该使它到位 我必须在循环中进行多次迭代，因此速度很重要 理想的随机性（均匀分布）不是必需的，如果它“几乎”是随机的，那就没关系 在进行排列之前，我已经遍历了N个元素（用于其他需求），所以也许我可以将它用于排列 更新：我发现了这篇论文 。 它声明它提出了一个O（log n）堆栈空间和预期的O（n log n）时间的算法。
对某些Graph操作的最简单算法的建议
这个项目的截止日期很快就会结束，我没有太多时间来处理剩下的事情。 因此，我正在寻找最简单的算法来实现Graph结构上的一些操作，而不是寻找最好的（可能更复杂/耗时）算法。 我需要做的操作如下： 在给定距离X的情况下列出图形网络中的所有用户 给定距离X和关系类型，列出图形网络中的所有用户 在给定一种关系的情况下，计算图形网络上2个用户之间的最短路径 计算图形网络上2个用户之间的最大距离 计算图形网络上最远的连接用户 关于我的Graph实现的一些注意事项： 边节点有2个属性，一个是char类型，另一个是int 。 它们分别代表关系和体重的类型。 图表使用链接列表实现，包括顶点和边。 我的意思是，每个顶点指向下一个顶点，每个顶点也指向不同链表的头部，即该特定顶点的边。 我知道我需要做什么： 我不知道这是否是最简单的，如上所述，但对于2个用户之间的最短路径，我相信Dijkstra算法是人们似乎经常推荐的，所以我想我会接受它。 我一直在搜索和搜索，我发现很难实现这个算法，有没有人知道任何教程或易于理解的东西，所以我可以自己实现这个算法？ 如果可能的话，使用C源代码示例，它会有很大帮助。 我看到许多带有数学符号的例子，但这让我更加困惑。 如果我将图形“转换”为邻接矩阵来表示链接权重和关系类型，您认为这会有所帮助吗？ 是否更容易执行该算法而不是链接列表？ 我可以轻松地实现一个函数来在需要时进行转换。 我这样说是因为我觉得在阅读了几页关于这个主题之后会更容易，但我可能是错的。 我对其他4个操作，建议没有任何想法？
建议网站练习C / C ++算法/谜题
我想在C / C ++中练习解决问题。 但我想避免从头开始编写整个程序。 是否有任何网站，他们给我拼图和代码骨架以及它，并期望我只填写一个或两个函数来解决手头的问题？ 这将节省大量时间，我只能专注于解决问题的部分。 谢谢。
用C / C ++绘制填充椭圆的简单算法
在SO上，找到了以下用于绘制实心圆的简单算法： for(int y=-radius; y<=radius; y++) for(int x=-radius; x<=radius; x++) if(x*x+y*y <= radius*radius) setpixel(origin.x+x, origin.y+y); 绘制填充椭圆是否有同样简单的算法？
有关如何根据给定条件找到标记给定数组的所有元素的最小步数的任何提示？
给出了两个整数N<=10^5和K<=N ，其中N是数组A[]的大小， K是我们在过程中可以选择的连续子序列的长度。 A[i]<=10^9元素A[i]<=10^9 。 现在假设最初所有数组元素都没有标记。 在每个步骤中，我们将选择长度为K任何子序列，如果此子序列具有未标记的元素，那么我们将标记所有未标记的元素，这些元素在后序中是最小的。 现在如何计算标记所有元素的最小步数？ 为了更好地理解问题，请参阅此示例 – N=5 K=3 A[]=40 30 40 30 40 步骤1-选择区间[1,3]并标记A [1]和A [3] 步骤2 – 选择区间[0,2]并标记A [0]和A [2] 步骤3-选择区间[2,4]并标记A [4] 因此，此处的最小步骤数为3。 我的方法（速度不够快） – 我从数组的第一个元素开始，并在距离<=K处标记所有未标记的元素，并将steps递增1。
C中Quick Union实现中的分段错误（核心转储）
#include #include int *id,N; main() { FILE* file=fopen(“a.txt”,”r”); int i,p,q,c; fscanf(file,”%d”,&N); id=(int *)malloc(N*sizeof(int)); for(i=0;i<N;i++) *(id+i)=i; while(!feof(file)) { fscanf(file,"%d %d",&p,&q); if(!connected(p,q)) unn(p,q); } fclose(file); c=1; while(c==1) { scanf("%d %d",&p,&q); printf("%d\nYes(1) or No(0) ",connected(p,q)); scanf("%d",&c); } } connected(int p,int q) { return((root(p))==(root(q))); } unn(int p,int q) { int j=root(q); int i=root(p); *(id+j)=i; } root(int i) { while(i!=(*(id+i))) […]
Boyer-Moore良好后缀启发式
我理解不良角色启发式的工作方式。 当您找到不匹配的字母x ，只需移动图案，使图案中最右侧的x与字符串中的x对齐。 并且它很容易在代码中实现。 我想我也理解良好后缀的启发式方法是如何工作的。 当我们找到一个好的后缀s ，在模式中的不同位置找到相同的后缀并移动它，使模式中的s与字符串中的s对齐。 但我不明白如何在代码中这样做。 我们如何找到模式中另一个地方是否存在相同的后缀？ 我们如何知道它的立场？ 代码： void bmPreprocess1() { int i=m, j=m+1; f[i]=j; while (i>0) { while (j<=m && p[i-1]!=p[j-1]) { if (s[j]==0) s[j]=ji; j=f[j]; } i–; j–; f[i]=j; } } 来自http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/bmen.htm对我没有意义……有人可以为此任务编写尽可能简单的伪代码吗？ 或者以某种方式解释？
