# 《编程原本 》一2.3 碰撞点

### 2.3 碰撞点

template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == Domain(P))
Domain(F) collision point(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
if (!p(x)) return x;
Domain(F) slow = x; //slow=f0(x)
1.Knuth[1997,7页]将这一算法归功于RobertW.Floyd.
Domain(F) fast = f(x); //fast=f1(x)
// n ← 0(完成迭代)
while (fast != slow) { //slow=fn(x)∧fast=f2n+1(x)
slow = f(slow); //slow=fn+1(x)∧fast=f2n+1(x)
if (!p(fast)) return fast;
fast = f(fast); //slow=fn+1(x)∧fast=f2n+2(x)
if (!p(fast)) return fast;
fast = f(fast); //slow=fn+1(x)∧fast=f2n+3(x)
// nn + 1
←
}
return fast; //slow=fn(x)∧fast=f2n+1(x)
//后条件:返回终止点或碰撞点的值
}


template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == Domain(P)) bool terminating(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
return !p(collision point(x, f, p));
}


template<typename F>
requires(Transformation(F)) Domain(F) collision point nonterminating orbit(const Domain(F)& x, F f)
{
Domain(F) slow = x; //slow=f0(x)Domain(F) fast = f(x); //fast=f1(x)
// n ← 0(完成迭代)
while (fast != slow) { //slow=fn(x)∧fast=f2n+1(x)slow = f(slow); //slow=fn+1(x)∧fast=f2n+1(x)fast = f(fast); //slow=fn+1(x)∧fast=f2n+2(x)fast = f(fast); //slow=fn+1(x)∧fast=f2n+3(x)
// nn + 1
←
}
return fast; //slow=fn(x)∧fast=f2n+1(x)
//后条件:返回碰撞点的值
}


qc=h+d+1用下式表示h对c取模:h=mc+r其中0.r也就是
d=(q.m)c.r.10.d所以
d=c.r.1而且需要r+1步去完成整个环.这样,从碰撞点到连接点的距离就是e=r+1对环路轨道有h=0且r=0,从碰撞点到轨道开始点的距离是e=1由此可知,环路性质可以用下面过程检查:

template<typename F> requires(Transformation(F)) bool circular nonterminating orbit(const Domain(F)& x, F f)
{
return x == f(collision point nonterminating orbit(x, f));
}
template<typename F, typename P> requires(Transformation(F) && UnaryPredicate(P) && Domain(F) == Domain(P)) bool circular(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
Domain(F) y = collision point(x, f, p);return p(y) && x == f(y);
}


fh+d(x)=fh+c.r.1(x)=fmc+r+c.r.1(x)=f(m+1)c.1(x)

template<typename F> requires(Transformation(F)) Domain(F) convergent point(Domain(F) x0, Domain(F) x1, F f)
{
// 前条件: (.n ∈ DistanceType(F))n.0∧fn(x0)=fn(x1)
while (x0 != x1) {

x0 = f(x0);x1 = f(x1);
}
return x0;
}
template<typename F>
requires(Transformation(F)) Domain(F) connection point nonterminating orbit(const Domain(F)& x, F f)
{
return convergent point(x,f(collision point nonterminating orbit(x, f)),f);
}
template<typename F, typename P> requires(Transformation(F) && UnaryPredicate(P) && Domain(F) == Domain(P)) Domain(F) connection point(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
Domain(F) y = collision point(x, f, p);if (!p(y)) return y;return convergent point(x, f(y), f);
}


|
9月前
|
PHP 开发者

76 1
|

105 0
|

162 0
|

【自然框架】重新整理后的自然框架源码！
整理后的自然框架源码，有九个项目，可以看下面的脑图，带“对号”的表示是一个独立的项目。后面的是主要内容。   　　欢迎下载http://www.naturefw.com/Down/kind38/List1.aspx ，但是请保留源码里的版权信息，以及dll里的版权信息。
757 0
|

1834 0
《编程原本 》一2.6 总结

764 0
《编程原本 》一1.8 总结

883 0
|

《编程原本 》一3.3 程序变换

1161 0
|

《编程原本 》一导读

1023 0