分布式算法作业及其答案（Ex8)

//--------------------------------------------------------------------------------------------------------------------

8. 若将环

R

rev

划分为长度为 j（j 为 2 的幂）的连续片段，则所有这

些片段是次序等价的。

//---------------------------------------------------------------------------------------------------------------------

证明：对一个整数P (0 · P · n ¡ 1)，可表示为如下形式：

P =

m

m

P

i

m¡i

设P、Q在同一个片段上，P’、Q’在同一个片段上，且设这两个片段是

相邻的，根据模加法有：

根据表示方法，可以得出：

P

从而存在

r(1 · r · k)，满足a

。否则，jP ¡ Qj¸2

同一个片段上矛盾。

设

可以看出，P与P’的前k位相同，Q与Q’的前k位相同。由

片段都是序等价的。