在 C# 中以数学方式导航大型 2D 数字网格
题
我试图在一个非常大的虚拟网格中找到某些感兴趣的坐标。该网格实际上并不存在于内存中,因为尺寸很大。为了回答这个问题,我们假设这些尺寸是 (Width x Height) = (Int32.MaxValue x Int32.MaxValue)
.
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20
3 6 9 12 15 18 21 24 27 30
4 8 12 16 20 24 28 32 36 40
5 10 15 20 25 30 35 40 45 50
6 12 18 24 30 36 42 48 54 60
7 14 21 28 35 42 49 56 63 70
8 16 24 32 40 48 56 64 72 80
9 18 27 36 45 54 63 72 81 90
10 20 30 40 50 60 70 80 90 100
有关网格的已知数据:
- 网格尺寸=
(Int32.MaxValue x Int32.MaxValue)
. - 任何给定值
(x, y)
坐标 = X 和 Y 的乘积 =(x * y)
.
给定上述一大组有限数,我需要计算一组坐标,其值 (x * y)
是一个幂 e
. 。比方说 e
在本例中为 2。
由于循环遍历网格不是一个选项,所以我考虑循环遍历:
int n = 0;
long r = 0;
List<long> powers = new List<long>();
while (r < (Int32.MaxValue * Int32.MaxValue))
{
r = Math.Pow(e, n++);
powers.Add(r);
}
这赋予我们一套独特的权力。我现在需要找出每种力量存在的坐标。让我们来 2^3=8
. 。如上面的网格所示,8存在于4个坐标中: (8,1), (4,2), (2,4) & (1, 8)
.
显然,这里的问题是找到数字 8 的多个因数,但对于更大的数字来说这将变得不切实际。还有其他方法可以实现这一目标吗?我错过了什么吗?
- 使用集合不起作用,因为这些因素不存在于内存中。
- 是否有一种创造性的方法来分解知道所讨论的数字始终是 的幂
e
?
解决方案
另一种解决方案,不像 Commodore63 的想法那么复杂,但因此可能更简单一些(不需要进行素因数分解并计算所有真子集):
const int MaxX = 50;
const int MaxY = 50;
const int b = 6;
var maxExponent = (int)Math.Log((long)MaxX * MaxY, b);
var result = new List<Tuple<int, int>>[maxExponent + 1];
for (var i = 0; i < result.Length; ++i)
result[i] = new List<Tuple<int, int>>();
// Add the trivial case
result[0].Add(Tuple.Create(1, 1));
// Add all (x,y) with x*y = b
for (var factor = 1; factor <= (int)Math.Sqrt(b); ++factor)
if (b % factor == 0)
result[1].Add(Tuple.Create(factor, b / factor));
// Now handle the rest, meaning x > b, y <= x, x != 1, y != 1
for (var x = b; x <= MaxX; ++x) {
if (x % b != 0)
continue;
// Get the max exponent for b in x and the remaining factor
int exp = 1;
int lastFactor = x / b;
while (lastFactor >= b && lastFactor % b == 0) {
++exp;
lastFactor = lastFactor / b;
}
if (lastFactor > 1) {
// Find 1 < y < b with x*y yielding a power of b
for (var y = 2; y < b; ++y)
if (lastFactor * y == b)
result[exp + 1].Add(Tuple.Create(x, y));
} else {
// lastFactor == 1 meaning that x is a power of b
// that means that y has to be a power of b (with y <= x)
for (var k = 1; k <= exp; ++k)
result[exp + k].Add(Tuple.Create(x, (int)Math.Pow(b, k)));
}
}
// Output the result
for (var i = 0; i < result.Length; ++i) {
Console.WriteLine("Exponent {0} - Power {1}:", i, Math.Pow(b, i));
foreach (var pair in result[i]) {
Console.WriteLine(" {0}", pair);
//if (pair.Item1 != pair.Item2)
// Console.WriteLine(" ({0}, {1})", pair.Item2, pair.Item1);
}
}
其他提示
最好的方法是将 e 分解为素数分量。可以说它们如下:{a^m,b^p,c^q}。然后为 e 的每个幂构建集合,例如如果 m=2、p=1、q=3,
e^1 = {a, a, b, c, c, c}
e^2 = (a, a, a, a, b, b, c, c, c, c, c, c}
ETC。最多 e^K > Int32.MaxValue * Int32.MaxValue
然后,对于每个集合,您需要迭代这些集合的每个唯一子集以形成一个坐标。另一个坐标是剩下的。对于 e 中的每个唯一素数,您将需要一个嵌套循环。例如:
假设 e^2
M=m*m;
P=p*p;
Q=q*q;
c1 = 1 ;
for (i=0 ; i<=M ; i++)
{
t1 = c1 ;
for (j=0 ; j<=P ; j++)
{
t2 = c1 ;
for (k=0 ; k<=Q ; k++)
{
// c1 holds first coordinate
c2 = e*e/c1 ;
// store c1, c2
c1 *= c ;
}
c1 = t2*b ;
}
c1 = t1*a ;
}
应该有 (M+1)(P+1)(Q+1) 个唯一坐标。
不隶属于 StackOverflow