l****n
发帖数: 18 | 1 数轴上n个点。1,2,3...n。i点和i+1点距离为1。每个点i上有个点电荷Qi。
求：n各点每个受到的电场合力。电场力计算公式为 F（i， j）=Qi ×Qj / (i-j)^
也就是求对于指定的i，SUM (F（i，j）) in which i !=j。
这道题在O（n×n）时间当然简单。要求用O（nlogn）时间解。 | e*n
发帖数: 1511 | 2 同问。
【在 l****n 的大作中提到】
: 数轴上n个点。1,2,3...n。i点和i+1点距离为1。每个点i上有个点电荷Qi。
: 求：n各点每个受到的电场合力。电场力计算公式为 F（i， j）=Qi ×Qj / (i-j)^
: 也就是求对于指定的i，SUM (F（i，j）) in which i !=j。
: 这道题在O（n×n）时间当然简单。要求用O（nlogn）时间解。
| s***e
发帖数: 122 | 3 上网查了一下n-body问题，看来问题比较复杂，用等价电荷的方法必须是对距离比较远的电荷组才可以近似。所以，这种方法是不能得到准确结果的。我也还是另等高明吧。
============================================================================
我写了些伪码，大致是用二分法，将电荷组不断分成两半，每分一次，算出每一半的中
心和另一半的每一个电荷的相互作用力，以更新结果数组。
// 电荷
struct e {
double q; // 电量
double loc; // 位置
}
// 电荷数组
e a[n];
int main() {
// 初始化电荷数组
// ...
// 电荷受力数组
double f[n];
for (i = 1~n) f[i] = 0;
center(a, f, 0, n-1);
// 打印电荷受力数组
// ...
}
// 计算电荷组的等价电荷
e center(e a[], double f[], int
【在 l****n 的大作中提到】
: 数轴上n个点。1,2,3...n。i点和i+1点距离为1。每个点i上有个点电荷Qi。
: 求：n各点每个受到的电场合力。电场力计算公式为 F（i， j）=Qi ×Qj / (i-j)^
: 也就是求对于指定的i，SUM (F（i，j）) in which i !=j。
: 这道题在O（n×n）时间当然简单。要求用O（nlogn）时间解。
| f**********e
发帖数: 1994 | 4 barnes-hut 算法。关键是建 Tree, n log n. | c*******3
发帖数: 21 | 5 I think barnes-hut may not work as one cannot use the clustering
approximation here so one still end up
transversing all the tree elements.
How about solving a Poisson equation for the potential using FFT which will
be O(nlogn), and then do a
finite difference of the potential to get the force.
【在 f**********e 的大作中提到】
: barnes-hut 算法。关键是建 Tree, n log n.
|
|
