Tag: 数学

减少整数分数算法

（这源于最近完成的编程竞赛） 您将获得两个10 ^ 5整数的数组，范围为1..10 ^ 7，包括： int N[100000] = { … } int D[100000] = { … } 想象一下，有理数X是将N的所有元素相乘并除以D的所有元素的结果。 修改两个数组而不更改X的值（并且不指定任何元素超出范围），使得N的乘积和D的乘积没有公因子。 一个天真的解决方案（我认为）会起作用…… for (int i = 0; i < 100000; i++) for (int j = 0; j < 100000; j++) { int k = gcd(N[i], D[j]); // euclids algorithm N[i] /= k; D[j] /= k; } […]

四元数“lookAt”function

我正在努力解决以下问题。 我正在使用骨骼动画，我希望（即）玩家的头部跟随太空中的另一个物体。 我的上轴是+ Z我的前轴是+ Y，四元数的大小是W.我试图使用gluLookAt的mesa代码并使用3×3矩阵转换为四元数但它不能按预期工作所以我走向另一个方向…… 到目前为止，我得到了以下代码“几乎”工作，至少玩家的头部正在旋转（但是X角度似乎影响Y旋转轴）在良好的方向上，但它直视向上而不是跟随一个物体约65度的地板： qt LookRotation( v3 lookAt, v3 upDirection ) { qt t; v3 forward = lookAt; v3 up = upDirection; OrthoNormalize( &forward, &up ); v3 right = v3_cross( up, forward ); mat3 m = mat3_make( right.x, up.x, forward.x, right.y, up.y, forward.y, right.z, up.z, forward.z ); tw = sqrtf( 1.0f + mr[ […]

整数立方根

我正在寻找64位（无符号）立方根的快速代码。 （我正在使用C并使用gcc进行编译，但我想大多数所需的工作都是语言和编译器无关的。）我将通过ulong表示一个64位的unisgned整数。 给定输入n我需要（整数）返回值r r * r * r <= n && n < (r + 1) * (r + 1) * (r + 1) 也就是说，我想要n的立方根，向下舍入。 基本代码如 return (ulong)pow(n, 1.0/3); 因为向范围的末端舍入而不正确。 简单的代码就像 ulong cuberoot(ulong n) { ulong ret = pow(n + 0.5, 1.0/3); if (n = 18446724184312856125ULL) return 2642245ULL; if (ret * ret * ret > […]

（rho / theta）参数化中定义的两条线的交点

已经创建了Hough变换的c ++实现来检测图像中的线条。 找到的线条用rho，theta表示，如维基百科所述： “参数r表示直线与原点之间的距离，而θ是从原点到该最近点的矢量角度” 如何在使用r，θ描述的两条线的x，y空间中找到交点？ 这里参考我目前用于转换进出霍夫空间的函数： //get ‘r’ (length of a line from pole (corner, 0,0, distance from center) perpendicular to a line intersecting point x,y at a given angle) given the point and the angle (in radians) inline float point2Hough(int x, int y, float theta) { return((((float)x)*cosf(theta))+((float)y)*sinf(theta)); } //get point y for a line […]

找到时间为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）。 任何帮助，将不胜感激。

随机置换单链表的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）时间的算法。

优化我！ （C，表现） – 跟随苦涩的问题

感谢bit Twiddling的一些非常有用的stackOverflow用户：设置了哪个位？ ，我已经构建了我的函数（在问题的最后发布）。 任何建议 – 即使是小建议 – 将不胜感激。 希望它能使我的代码变得更好，但至少它应该教会我一些东西。 🙂 概观 此function将被调用至少10 13次，并且可能经常被调用10 15次 。 也就是说，此代码很可能会运行数月 ，因此任何性能提示都会有所帮助。 此function占计划时间的72-77％，基于分析和不同配置中的大约十二次运行（优化此处不相关的某些参数）。 此function目前平均运行50个时钟。 我不确定这可以改进多少，但我很高兴看到它在30岁时运行。 重点观察 如果在计算的某个时刻你可以告诉你将返回的值很小（准确值可协商 – 比如说，低于一百万） 你可以提前中止 。 我只对大价值感兴趣。 这就是我希望节省大部分时间的方式，而不是通过进一步的微观优化（尽管这些当然也是受欢迎的！）。 绩效信息 smallprimes是一个位数组（64位）; 平均大约8位将被设置，但它可以少至0或多达12。 q通常是非零的。 （请注意，如果q和smallprimes为零，则函数会提前退出。） r和s通常为0.如果q为零，r和s也将为0; 如果r为零，则s也是如此。 正如最后的评论所说，nu到底通常是1，所以我有一个有效的特殊情况。 特殊情况下的计算可能会出现溢出风险，但通过适当的建模我已经certificate，对于我的输入，这不会发生 – 所以不要担心这种情况。 此处未定义的function（ugcd，minuu，star等）已经过优化; 无需花很长时间才能运行。 pr是一个小数组（全部在L1中）。 此外，这里调用的所有函数都是纯函数 。 但是如果你真的在乎… ugcd是gcd ，minuu是最小值，vals是尾随二进制0的数量，__ builtin_ffs是最左边的二进制1的位置，star是（n-1）>> vals（n- 1），pr是从2到313的素数数组。 目前正在Phenom II 920 x4上进行计算，尽管对i7或Woodcrest的优化仍然很有意义（如果我在其他节点上获得计算时间）。 我很乐意回答您对该function或其成员的任何问题。 […]

BMI计算器C代码

我正在尝试编写一个简单的BMI计算器，但由于某些原因，当我尝试175为高度（公式为1.75）和70为质量时，它应该给22.8，这是在健康的范围，但它让我体重不足。 我知道这可能是一个简单的错误，但我看不到它。 float main(void) { float height; printf(“Enter your height in cm:\n”); scanf(“%f”,&height); float weight; printf(“Enter your weight in kg:\n”); scanf(“%f”,&weight); float bmi; bmi = (weight/(height/100)*(height/100)); if (bmi <= 16) { printf("Severely Underweight\n"); } else if (16 < bmi <= 18.5) { printf("Underweight\n"); } else if (18.5 < bmi <= 25) { printf("Healthy\n"); } else […]

重新排列等式

我的C代码中有以下等式 k * dl * (1.0 + pHold / centre + (pHold * pHold) / (2.0 * centre * centre) – square / (2.0 * centre)) 我知道浮点除法比乘法要贵得多，而且我已经和它搏斗了一段时间。 有没有办法重新排列这个来划分一个师？ 谢谢