作业帮 > 综合 > 作业

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

来源:学生作业帮 编辑:神马作文网作业帮 分类:综合作业 时间:2024/11/11 00:35:02
试设计一个算法,将数组R中R[0]至R[N-1]循环右移P位,并要求只用一个单位大小的附加存储,数组中元素移动或交换次数为O(n).
要求用C++表述算法
试设计一个算法,将数组R中R[0]至R[N-1]循环右移P位,并要求只用一个单位大小的附加存储,数组中元素移动或交换次数
这是《编程珠玑》里的一个例子
分三步:
第一步:把整个数组首尾颠倒(即第一个和最后一个换位,第二个和倒数第二个换等等)
第二步:再把调换后的数组前n-p个数首尾颠倒
第三部:最后把数组末p个数首尾颠倒
可以验证经过上述操作的结果就等于数组循环右移p位,而且每次两个数组元素对调只需要一单位附加存储,共需要调换n次