试设计一个算法,将数组R中R[0]至R[N-1]循环右移P位,并要求只用一个单位大小的附加存储,数组中元素移动或交换次数为O(n).要求用C++表述算法

Question

试设计一个算法,将数组R中R[0]至R[N-1]循环右移P位,并要求只用一个单位大小的附加存储,数组中元素移动或交换次数为O(n).
要求用C++表述算法

Answer 1

这是《编程珠玑》里的一个例子
分三步：
第一步：把整个数组首尾颠倒（即第一个和最后一个换位,第二个和倒数第二个换等等）
第二步：再把调换后的数组前n-p个数首尾颠倒
第三部：最后把数组末p个数首尾颠倒
可以验证经过上述操作的结果就等于数组循环右移p位,而且每次两个数组元素对调只需要一单位附加存储,共需要调换n次