《编程原本 》一2.2 轨道

简介: 本节书摘来自华章出版社《编程原本 》一书中的第2章,第2.2节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.2 轨道

要理解一个变换的全局行为,可以考察其轨道(orbit)的结构.所谓变换的轨道,就是从一个开始元素出发,通过反复应用这一变换能到达的所有元素.如果对某个n.0有y=fn(x),就说y是从x出发在变换f下可达的(reachable).如果有某个n.1使x=fn(x),就说x在f下是环路的(cyclic).如果x不在f的定义空间里,称x在f下是终止点(terminal).x在变换f下的轨道(orbit)就是x

在f 下可达的所有元素的集合.
引理2.2 一条轨道不会同时包含环路元素和终止元素.
引理2.3 一条轨道至多包含一个终止元素.
如果元素y为从x在f下可达,从x到y的距离(distance)定义为从x得到y的最小的变换步数.显然,距离并不总有定义.
给定变换类型F,类型DistanceType(F)是一个足够大的整数类型,足以表示任何变换f∈ F从T=Domain(F)的一个元素到另一元素的最大变换步数.如果类型T用k个二进制位表示,它就有2k 个值,而不同值之间只有2k.1个变换步.这样,如果T是固定大小的类型,同样大小的整数类型就能作为表示T上任意变换的距离的合法类型.(可以不用距离类型,而是在powerunary里用任意整数类型,因为这种额外推广不会在这里造成问题.)一种常见情况是同一定义域上的变换都具有同样的距离类型.这时类型函数DistanceType就对这一定义域类型有定义,定义了与相关变换类型对应的类型函数.
如果类型函数DistanceType存在,就可以写出下面过程:
template
requires(Transformation(F)) DistanceType(F) distance(Domain(F) x, Domain(F) y, F f) {
//前条件:y在f下从x可达
typedef DistanceType(F) N;
N n(0);
while (x != y) {
x = f(x);
n = n + N(1);
}
return n;
}
轨道有不同的形状.x在某变换下的轨道可以是
image

无穷的 若它既不是终止的也没有环路
终止的 若它有一个终止元素
环路的 若x 是环路的
ρ 形的 若x本身不是环路的,但它的轨道包含环路元素

如果x的轨道不是无穷的,它就是有穷的.图2.1给出了轨道的各种情况.
轨道环(cycleoforbit)是轨道的一集元素,规定轨道为无穷或终止时其环为空.轨道柄(handleoforbit)是轨道里除去环之外的部分,环路轨道的柄为空.连接点(connectionpointoforbit)是轨道上的第一个环路元素,对环路轨道取其第一个元素,对ρ形轨道是轨道柄之后的第一个元素.轨道规模(sizeoforbit)o是轨道中不同元素的个数;轨道的柄规模(handlesize)h是轨道柄中元素的个数;环规模(circlesize)c是轨道环中元素的个数.
引理2.4 o = h + c
引理2.5 从轨道中任意一点到该轨道的环路中任意一点的距离都有定义.
引理2.6若x和y是规模为c的环里的两个不同点,那么
c=distance(x,y,f)+distance(y,x,f)
引理2.7若x和y是规模为c的环的两个不同点,x到y的距离满足
0.distance(x,y,f)

相关文章
|
13天前
|
存储 安全 编译器
C++学习过程中的一些值得注意的小点(1)
C++学习过程中的一些值得注意的小点(1)
|
13天前
|
算法 图形学 UED
Unity Hololens2开发|(八)MRTK3空间操作 BoundsControl(边界控制)
Unity Hololens2开发|(八)MRTK3空间操作 BoundsControl(边界控制)
|
13天前
|
存储 算法 Serverless
连线消除游戏的原理和实现
连线消除游戏的原理和实现
47 0
HMI-33-【运动模式】补上油量表和水温表
上一篇,以为是做了一个收尾,写了灯光控制面板和底部的信息栏,但是,有位眼见的小伙伴`江山壹角`,直接不给我面子,说我的水温表和油量表不会动。截图位置,我记仇哈。
|
7月前
|
前端开发 芯片
【芯片前端】保持代码手感——不重叠序列检测
【芯片前端】保持代码手感——不重叠序列检测
|
8月前
行走小动画案例扩展
行走小动画案例扩展
|
机器学习/深度学习 人工智能 程序员
点线面的工作学习方式
  本文主要介绍我个人的一种工作学习方式:点线面的工作学习方式。希望对大家以后的工作和职业发展有所启发和帮助。   7月份的时候,我去京东外面的世界转了转,聊了聊。切身体会到:别人其实并不关心你之前做的具体工作,关心的是你从中得到了什么。当然,如果你是一直深耕一个业务领域的专家,除外,例如一直从事金融风控领域的技术开发。   面试中,我之前在啥啥公司做了啥啥项目,这个项目业务怎么怎么的复杂,功能怎么怎么的牛批,一顿业务功能的输出。   so ?然后呢 ?
132 0
|
API C#
用C#实现屏幕吸色功能,附逻辑思维讲解图,功能代码不超过50行即可实现
此程序是我上学的时候写的,好几年前的事了,前几天整理硬盘文件时发现自已其实还写过很多东西,当时还没有在园子里面混,故没怎么分享,现在有时间那就给需要的朋友分享分享,我的主要实现思路是: 一、创建一个画布(即为Form),大小和当前屏幕大小一样 二、在这快画布上建立一个绘图对象,截取复制当前屏幕内...
1220 0
|
编解码 算法 异构计算
小视频开发过程中最关注的两点关键
小视频凭借它独有的特征在互联网领域获得了属于自己的一席之地,斩获搞笑、游戏、美食等行业后,在教育、财经等方面还拥有更加可观的发展前景。那么,在小视频开发过程中应该怎样结合它的能力实现业务上的突破呢?