将一个n元一维向量向左循环移位i个位置。简单的代码使用一个n元的中间向量在n步内完成该工作。你能够仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转？
　　可以通过如下方式解决该问题：首先将x的前i个元素复制到一个临时数组中，然后将余下的n-i个元素向左移动i个位置，最后将最初i个元素从临时数组中复制到x中余下的位置。但是，这种办法使用的i个额外位置产生了过大的存储空间消耗。另一种方法是定义一个函数将x向左旋转一个位置（其时间正比于n）然后调用该函数i次。但该方法又产生了过多的运行时间消耗。

（杂技移位）移动x[0]到临时变量t，然后移动x[i]至x[0]，x[2i]至x[i]，以此类推，直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。如果该过程没有移动全部元素，就从x[1]开始再次进行移动，直到所有的元素都已经移动为止。

　　下面的代码以杂技移位的方式将x[n]向左旋转rotdist个位置

for i = [0, gcd(rotdist, n))
　　  /* move i-th value of blocks */
　　  t = x[i]
　　  j = i
　　  loop
　　    k = j + rotdist
　　    if k >= n
　　      k -= n
　　    if k == i
　　      break
　　    x[j] = x[k]
　　    j =k
　　  x[j] = t

　　从代码中可以看出：（1）rotdist和n的最大公约数是外层循环循环的次数，也就是一次完整的“杂技”操作重复的次数；（2）上述代码中存在问题，虽然当rotdist > n时外层循环的次数并没有变化，但进入内层循环后如果 k >= 2n会导致数组下标越界，在开始处添加rotdist = rotdist%n可以避免这个问题。（作者在书的前言中表示，书中的代码很少或没有错误检测，是为了有助于表达算法的核心思想，所以可能是作者有意忽略。）

　　（递归方法）从另外一面考察这个问题，可以得到一个不同的算法：旋转向量x其实就是交换向量ab的两段，得到向量ba。这里a代表x中的前i个元素。假设a比b短，将b分为bl和br，使得br具有与a相同的长度。交换a和br，也就将ablbr转换为brbla。序列a此时已处于其最终的位置，因此现在的问题就集中到交换b的两部分。由于新问题与原来的问题具有相同的形式，我们可以递归地解决之。

下面的代码来自Gries的Science of programming一书的18.1节，它假设函数swap(a, b,m)的功能是交换x[a..a+m-1]和x[b..b+m-1]。

　　if rotdist == 0 || rotdist == n
　　  return
　　i = p = rotdist
　　j = n-p
　　while i != j
　　  /* invariant
　　    x[0..p-i] in final position
　　    x[p-i..p-1] = a (to be swapped with b)
　　    x[p..p+j-1] = b (to be swapped with a)
　　    x[p+j..n-1] in final position
　　  */
　　  if i > j
　　    swap (p-i, p, j)
　　    i -= j
　　  else
　　    swap (p-i, p+j-i, i)
　　    j -= i
　　swap (p-i, p, i)

　　上述代码中，当while循环结束时，i = j = gcd(i, j)。另外，还是要注意应在代码最开始添加 rotdist = rotdist%n。

该代码跟下面这段（虽然慢但是正确）计算i和j的最大公约数的欧几里得算法是同构的（代码假设输入都不为0）

int gcd(int i, int j)
　　  while i != j
　　    if i > j
　　      i -= j
　　    else
　　      j -= i
　　  return i

　　（求逆，或称翻转方法）我们将问题看做是把数组ab转换成ba，同时假定我们拥有一个函数可以将数组中特定部分的元素求逆。从ab开始，首先对a求逆，得到arb，然后对b求逆，得到arbr。最后整体求逆，得到（arbr）r。此时就正好是ba。于是，我们用如下旋转代码。
　　

　　reverse(0, i-1)
　　reverse(i, n-1)
　　reverse(0,n-1)

　　翻转代码在时间上和空间上都很高效，而且代码非常短，很难出错。

　　作者在线的C代码如下：

　　/* Alg 1: Rotate by reversal */
　　
　　void reverse(int i, int j)
　　{
　　    int t;
　　    while (i < j) {
　　      t = x[i]; x[i] = x[j]; x[j] = t;
　　      i++;
　　      j--;
　　    }
　　}
　　
　　void revrot(int rotdist, int n)
　　{
　　    reverse(0, rotdist-1);
　　    reverse(rotdist, n-1);
　　    reverse(0, n-1);
　　}

　　需要说明的是，这里依然假定rotdist < n，而没有在代码中检测这个错误。