栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

实施互联网的希尔伯特地图

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

实施互联网的希尔伯特地图

这很容易,因为希尔伯特曲线是分形的,也就是说,它是递归的。它的工作原理是将每个正方形水平和垂直平分,将其分成四部分。因此,您一次从左开始一次获取IP地址的两位,并用它们确定象限,然后继续使用接下来的两位,用该象限而不是整个正方形,依此类推,直到得到用尽地址中的所有位。

每个正方形中曲线的基本形状类似于马蹄形:

 0 3 1 2

其中的数字对应于高两位,因此确定遍历顺序。在xkcd映射中,此正方形是最高级别的遍历顺序。可能旋转和/或反射后,此形状出现在每个2x2正方形处。

如何在“马蹄”在每个子方格的取向确定是通过一个规则决定的:

0
在角落
0
广场中规模较大的广场一角。因此,
0
必须按照以下顺序遍历与上面相对应的子正方形

 0 1 3 2

然后,查看整个前一个正方形并显示四个位,对于正方形的下一个划分,我们得到以下形状:

 00 01 32 33 03 02 31 30 10 13 20 23 11 12 21 22

这就是正方形总是在下一级被分割的方式。现在,继续,仅关注后两个钻头,根据这些钻头的马蹄形状如何定向此更详细的形状,然后继续进行类似的划分。

为了确定实际坐标,每两位确定实数坐标中的二进制精度一位。因此,在第一层上,坐标中二进制点之后的第一位(假定

[0,1]
范围内的
x
坐标)是
0
地址的前两位是否具有值
0
or
1
1
否则为。同样,
y
坐标中
0
的第一位是前两位是否具有值
1
2
。要确定是在坐标上添加a
0
还是
1
位,您需要在该级别上检查马蹄铁的方向。

编辑:我开始研究算法,结果证明毕竟并不难,所以这里有一些伪C语言。这是伪的,因为我

b
为二进制常数使用了后缀,并将整数视为位数组,但是将其更改为适当的C并不难。

在代码中,

pos
方向的3位整数。前两位是
0
正方形的x和y坐标,第三位表示是否
1
具有与相同的x坐标
0
。的初始值为
pos
is
011b
,表示
0
are
(0, 1)
和的坐标
1
与相同
0
ad
是地址,被视为
n
2位整数的-
element数组,并且从最高有效位开始。

double x = 0.0, y = 0.0;double xinc, yinc;pos = 011b;for (int i = 0; i < n; i++) {    switch (ad[i]) {        case 0: xinc = pos[0]; yinc = pos[1]; pos[2] = ~pos[2]; break;        case 1: xinc = pos[0] ^ ~pos[2]; yinc = pos[1] ^ pos[2]; break;        case 2: xinc = ~pos[0]; yinc = ~pos[1]; break;        case 3: xinc = pos[0] ^ pos[2]; yinc = pos[1] ^ ~pos[2]; pos = ~pos; break;    }    x += xinc / (1 << (i+1)); y += yinc / (1 << (i+1));}

我用几个8位前缀对其进行了测试,并根据xkcd映射正确放置了它们,因此我对代码的正确性有些信心。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/616934.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号