设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0﹤P﹤n)个位置，即将R中的数据由(X0 X1 ……Xn-1)变换为(Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1)要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度
分析：题目本身不是很难，但是要设计出最高效的算法还不那么容易。直观感觉，时间复杂度为O(n),空间复杂度为O(1),想了好久，想出了这种方法，但是不知道怎么证明，高手赐教！
（1）当n%p==0时，可以做p*(n/p)次搬运，具体的说就是每一趟搬运的是等价类，做p次。
（2）当n%p!=0时，做n次a[(j+p)%n]=a[j];但是，我不知道怎么证明？
代码如下：
void move_p_steps(int a[],int n,int p){
int i,j,temp,temp1;
if(n%p==0){
for(i=0;i<p;i++){
temp=a[n-1-i];
for(j=n-1-i-p;0<=j;j-=p)
a[j+p]=a[j];
a[(n-1-i+p)%n]=temp;
}
}
else{
j=0;
temp=a[0];
for(i=0;i<n;i++){
temp1=a[(j+p)%n];
a[(j+p)%n]=temp;
temp=temp1;
j=(j+p)%n;
}
}
}
EE直播间
更多
-
无线前沿新技术与测试技术峰会-线上直播 直播时间： 12月05日 09:30 -
首场直播发布： Keysight AP5000 系列新型高性价比模拟信号源 直播时间： 12月06日 10:00 -
全面掌握功率表应用及校准 直播时间： 12月10日 10:00 -
提升毫米波信号测试精度 直播时间： 12月18日 14:00
关闭
站长推荐
/2 
/2
文章评论（0条评论）
登录后参与讨论