Tag: 算法

数百万UINT64 RGBZ图形像素的最快排序算法: 我正在使用来自.RAW文件的RGB数据对1000多万uint64_t排序，并且在qsort花费了79％的C程序时间。我正在寻找这种特定数据类型的更快排序。作为RAW图形数据，这些数字非常随机，大约80％是唯一的。不需要对排序数据进行部分排序或运行。 uint64_t内的4 uint16_t s是R，G，B和零（可能是一个小的计数<= ~20）。我有最简单的比较函数，我可以想到使用unsigned long long （你不能只减去它们）： qsort(hpidx, num_pix, sizeof(uint64_t), comp_uint64); … int comp_uint64(const void *a, const void *b) { if(*((uint64_t *)a) > *((uint64_t *)b)) return(+1); if(*((uint64_t *)a) < *((uint64_t *)b)) return(-1); return(0); } // End Comp_uint64(). StackExchange上有一个非常有趣的“Programming Puzzles＆Code Golf”，但是他们使用了float 。然后有QSort，RecQuick，堆，stooge，树，基数…… swenson / sort看起来很有趣，但对我的数据类型uint64_t没有（明显的）支持。而“快速排序”时间是最好的。有些消息称，系统qsort可以是任何东西，不一定是“快速排序”。 C ++排序绕过了void指针的通用转换，并实现了对C的性能的极大改进。必须有一种优化的方法，以经线速度通过64位处理器猛击U8。系统/编译器信息： […]

如何简化分数: 我想在我的应用程序中简化一小部分。分数类似于x / y，其中x和y是整数。我想将分数简化为最简单的forms。任何人都可以给我提示如何做到这一点。提前致谢。

c栈中的递归: 这里是在merge merge中进行分区的代码。我无法理解recusrion究竟是如何工作的！ MERGE SORT PARTITION void partition(int arr[], int low, int high){ int mid; if(low < high){ mid = (low + high)/2; partition(arr, low, mid); partition(arr, mid + 1, high); mergeSort(arr, low, mid, high); } } 实际上我在很多递归问题中搞砸了，我无法理解系统堆栈如何在递归中工作……我是一个初学者..

将正方形打包成矩形: 我有一个矩形宽x高，和N个相同未知大小的方块。我必须确定这些方块的最大尺寸以及完全适合的行数和列数（UPD。我的意思是不填充所有空间，而是填充尽可能多的空间）到矩形中。我想，从数学上看，它看起来像这样： x * size <= width //x – number of columns y * size <= height //y – number of rows x * y max //size – size of squares 最终结果可能如下所示： 1 1 1 1 1 1 1 1 1 1 0 0 其中1 = squares ， 0 =空的空间`。实际上我看到了类似的问题，但预定义的正方形大小。另外，我写了一些笨拙的算法，但结果却非常不理想。编辑：我当前的算法：我尝试了很多变化，但我不能让它完美地适用于所有情况。 […]

枚举具有N个元素的1d数组的所有k分区？: 这似乎是一个简单的请求，但谷歌不是我的朋友，因为“分区”在数据库和文件系统空间中得分很多。我需要将N个值（N是常数）的数组的所有分区枚举成k个子数组。子数组就是 – 起始索引和结束索引。将保留原始数组的整体顺序。例如，N = 4且k = 2： [ | abcd ] (0, 4) [ a | bcd ] (1, 3) [ ab | cd ] (2, 2) [ abc | d ] (3, 1) [ abcd | ] (4, 0) 并且k = 3： [ | | abcd ] (0, 0, 4) […]

C中任何更快的RMS值计算？: 我正在用C编写一个小型8位微控制器的软件。部分代码是读取电流互感器（ZCT）的ADC值，然后计算RMS值。流过ZCT的电流是正弦曲线但可能会失真。我的代码如下： float adc_value, inst_current; float acc_load_current; // accumulator = (I1*I1 + I2*I2 + … + In*In) double rms_current; // Calculate the real instantanous value from the ADC reading inst_current = (adc_value/1024)*2.5; // 10bit ADC, Voltage ref. 2.5V, so formula is: x=(adc/1024)*2.5V // Update the RMS value with the new instananous value: // Substract […]

查找最大和的连续子数组: 我正在编写一个代码来查找C中的最大和连续子数组。根据我的说法，逻辑似乎很好，但输出仍然不正确。请查看代码。该算法将较大的arrays分成2个子arrays。然后通过检查左数组，右数组以及包含中点的数组来检查最大和子数组（它将检查中点的左右两边，然后返回包含中点的最大和子数组）。 int* cross_max(int arr[], int low, int mid, int high) { int left_max, left_sum = -2000; int sum = 0; int i; for(i=mid; i>=low;i–) { sum = sum + arr[i]; if(sum > left_sum) { left_sum = sum; left_max = i; } } int right_max, right_sum = -2000; for(i=mid+1; i right_sum) { right_sum […]

拆分整数乘法: 我需要一个使用两个32位整数作为参数的算法，并将这些参数的乘法分成两个其他32位整数：32位最高位部分和32位最低位部分。我会尝试： uint32_t p1, p2; // globals to hold the result void mult(uint32_t x, uint32_t y){ uint64_t r = (x * y); p1 = r >> 32; p2 = r & 0xFFFFFFFF; } 尽管它工作1 ，但它不能保证机器中存在64位整数，编译器也不能使用它们。那么，解决它的最佳方法是什么？注1 ：实际上，它不起作用，因为我的编译器不支持64位整数。 Obs ：请避免使用boost 。

计算函数sin（）: 对于我的学习，我必须使用此函数编写一个算法来计算sin() ：但是，在我的算法中，我必须将X的值保持在0和Pi / 2之间。所以，我编写了算法但所有结果都是错误的。这是我的代码： double sinX(double x){ double resultat = 0; int i; if(x M_PI_2) x = fmod(x,M_PI_2); for(i = 1;i<=30;i++){ resultat += -1 * ((x*x)/(2*i*(2*i+1)))*(pow(-1,i-1))*((pow(x,2*i-1))/(factorielle(2*i-1))); } return resultat; } 我找不到原因。你能帮助我吗？这里是X的几个值和fmod的结果 1 / 1 2 / 0.429204 3 / 1.4292 4 / 0.858407 5 / 0.287611 6 / 1.28761 7 […]

在将其转换为排序数组时查找堆化数组，交换总数最大可能: 受到这篇文章的启发，我搜索了最糟糕的heapsort案例并在cs.stackexchange.com上找到了这个问题，但唯一的答案并没有真正回答这个问题，所以我决定自己去挖掘它。经过数小时的推理和编码，我已经解决了。我认为这个问题在SO中更好，所以我在这里发布。问题是找到包含从1到n的不同数字的堆化数组，这样当将其转换为有序数组时，所有筛选操作中的交换总数最大可能。