gpt4 book ai didi

c++ - 计算半径 R 和维度 D 的球体内的整数点

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:22:16 25 4
gpt4 key购买 nike

我正在尝试编写一种有效的算法来计算半径 R 和维度 D 的球体内的点数。球体始终位于原点。假设我们有一个半径为 5 的 2 维球体(圆)。

我的策略是在第一象限内生成所有可能的点,因此对于上面的示例,我们知道 (1,2) 在圆中,因此必须是该点的所有 +/- 组合,这只是维度的平方。因此,对于在 n 维球体的单个象限中找到的每个点,我们将 2 ^ 维度添加到总计数。

我不确定是否有更有效的解决方案来解决这个问题,但这是我目前在实现方面的解决方案。

int count_lattice_points(const double radius, const int dimension) {
int R = static_cast<int>(radius);

int count = 0;

std::vector<int> points;
std::vector<int> point;

for(int i = 0; i <= R; i++)
points.push_back(i);

do {
for(int i = 0; i < dimension - 1; i++)
point.push_back(points.at(i));

if(isPointWithinSphere(point, radius)) count += std::pow(2,dimension);
point.clear();

}while(std::next_permutation(points.begin(), points.end()));

return count + 3;
}

在这种情况下我可以解决或改进什么?

最佳答案

对于 2D 情况,这是 Gauss's circle problem.一种可能的公式:

N(r) = 1 + 4 * r + 4 * Sum[i=1..r]{Floor(Sqrt(r^2-i^2))}

(中心点+四个象限,4*r为轴上点,其他为象限内区域)。

请注意,二维情况下没有已知的简单闭合数学表达式。

总的来说,您对象限、八分圆等的想法是正确的,但检查所有点的成本太高。

人们可能会找到从 1..D 组成从 0 到 r^2 的所有正方形的方法的数量整数平方((4)公式的扩展)

请注意,组合学有助于加快计算速度。例如,找到方法的数量就足够了从 D 个自然方 block 中生成 X^2,并乘以 2^D(不同的符号组合);从D-1个自然方 block 求出X^2的方法数,乘以D*2^(D-1)(不同的符号组合+零加数的D位)等

D=2,R=3 的例子

addends: 0,1,4,9
possible sum compositions number of variants
0 0+0 1
1 0+1,1+0 2*2=4
2 1+1 4
4 0+4,4+0 2*2=4
5 1+4,4+1 2*4=8
8 4+4 4
9 0+9,9+0 2*2=4
-------------------------------------
29

关于c++ - 计算半径 R 和维度 D 的球体内的整数点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37403017/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com