分形之城:递归超典型例题,还没明白?手把手画给你看!
2023-03-07 09:50:16 时间
本文转载自微信公众号「Piper蛋窝」,作者Piper蛋。转载本文请联系Piper蛋窝公众号。
题目
城市的规划在城市建设中是个大问题。
不幸的是,很多城市在开始建设的时候并没有很好的规划,城市规模扩大之后规划不合理的问题就开始显现。
而这座名为 Fractal 的城市设想了这样的一个规划方案,如下图所示:
当城区规模扩大之后,Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围,提升城市的等级。
对于任意等级的城市,我们把正方形街区从左上角开始按照道路标号。
虽然这个方案很烂,Fractal 规划部门的人员还是想知道,如果城市发展到了等级 ,编号为 和 的两个街区的直线距离是多少。
街区的距离指的是街区的中心点之间的距离,每个街区都是边长为 米的正方形。
输入格式
第一行输入正整数n ,表示测试数据的数目。
以下 n行,输入 n组测试数据,每组一行。
每组数据包括三个整数 N,A, B,表示城市等级以及两个街区的编号,整数之间用空格隔开。
输出格式
一共输出 行数据,每行对应一组测试数据的输出结果,结果四舍五入到整数。
数据范围
输入样例:
- 3
- 1 1 2
- 2 16 1
- 3 4 33
输出样例:
- 10
- 30
- 50
题解
这有啥不明白的,手把手画出来!
首先明确,为啥能用递归:
- 我们想计算 n 等级的坐标,知道 n-1 等级的坐标就行
然后思考怎么递归?
咱们首先规定,每个等级的坐标系原点是独特的,如下图。
然后我们从特殊到一般,归纳推规律:
- 等级1这个块块,如果放到等级2里,有四种情况要讨论
- 等级1放到等级2的左上象限,则相当于顺时针旋转了 90° ,并且还要沿 y 轴翻转(为什么要沿 y 轴翻转呢?因为你注意每个编号的位置,不翻转,形状虽然对上了,但是编号顺序没对上)
- 等级1放到等级2的右上象限,则不用转
- 等级1放到等级2的右下象限,则不用转
- 等级1放到等级2的左下象限,则相当于逆时针旋转了 90° ,并且还要沿 y 轴翻转
转完了,因为我们现在从等级1到等级2了,因此坐标系原点也移动了,所以要在等级1的原有坐标基础上进行平移。
好了,我给你画个图,你就懂了。
然后你再去看代码。
这里补充一点数学知识:
- 对于点 (x, y) ,沿原点顺时针旋转 90° ,将变为 (y, -x)
- 对于点 (x, y) ,沿原点逆时针旋转 90° ,将变为 (-y, x)
- 对于点 (x, y) ,以 y 轴为对称轴翻转将变为 (-x, y)
代码
- #include <iostream>
- #include <cstring>
- #include <cmath> // sqrt
- #include <algorithm>
- using namespace std;
- typedef long long LL;
- typedef pair<LL, LL> PLL;
- PLL calc(LL n, LL m)
- {
- /*
- * n: 等级
- * m: 坐标,从0开始计数
- */
- if (n == 0) return {0, 0};
- LL len = 1ll << (n - 1); // 2^{n-1} 本等级内象限的边长/2
- LL cnt = 1ll << (2 * n - 2); // 4^{n-1} 本等级内象限容量
- PLL pos = calc(n - 1, m % cnt); // 上一等级的坐标信息
- LL x = pos.first, y = pos.second;
- int z = m / cnt; // 处于哪个象限
- // 左上象限顺转90°(y,-x)沿y对称(-y,-x)更换原点(-y-len,-x+len)
- if (z == 0)
- return { - y - len, - x + len };
- // 右上象限更换原点(x+len,y+len)
- else if (z == 1)
- return { x + len, y + len };
- // 右下象限更换原点(x+len,y-len)
- else if (z == 2)
- return { x + len, y - len };
- // 左下象限逆转90°(-y,x)沿y对称(y,x)更换原点(y-len,x-len)
- return { y - len, x - len };
- }
- int main()
- {
- int N;
- cin >> N;
- while (N --)
- {
- LL n, m1, m2;
- cin >> n >> m1 >> m2;
- PLL pos1 = calc(n, m1 - 1);
- PLL pos2 = calc(n, m2 - 1);
- double delta_x = (double) (pos1.first - pos2.first);
- double delta_y = (double) (pos1.second - pos2.second);
- // 等级1中 len 是单位长度,且表示象限的一半长即为 10 / 2 = 5
- printf("%.0lf\n", sqrt(delta_x * delta_x + delta_y * delta_y) * 5);
- }
- }
参考资料
[1]Acwing: https://www.acwing.com
[2]98. 分形之城: https://www.acwing.com/problem/content/100/
相关文章
- 数据孤岛是业务效率的无声杀手
- 2023展望:新的一年将给大数据分析领域带来什么?
- 阿里云ADB基于Hudi构建Lakehouse的实践
- 大数据在医疗保健领域的使用案例
- 微软增加说明:KB5021751 更新扫描已经 / 即将过时 Office 过程中不会触碰用户隐私
- 2022 Gartner全球云数据库管理系统魔力象限发布 腾讯云数据库入选
- 场景化、重实操,分享一个实时数仓实践案例
- Arctic的湖仓一体践行之路
- 分布式计算MapReduce究竟是怎么一回事?
- 淘系数据模型治理优秀实践
- 大数据分析对医疗保健的影响
- 当我们说大数据Hadoop,究竟在说什么?
- 2022年及以后大数据的五个发展趋势
- 网易严选离线数仓治理实践
- 2023 年数据治理趋势
- 一份“靠谱”的年度经营计划,你学会了吗?
- 漫谈对大数据的思考
- 测试一下,读懂数据的能力,你有吗?
- 用艺术的眼光探索数据之美
- 聊聊数据分析成果如何落地