2. 考研
  3. 设将n(n，1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0＜P＜n)个位置，即将R中的数据由(X1，X2，…，Xn)变换为(XP，XP+1，…，XN，X1，XP-1)，要求： (1)给出算

设将n(n，1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0＜P＜n)个位置，即将R中的数据由(X1，X2，…，Xn)变换为(XP，XP+1，…，XN，X1，XP-1)，要求： (1)给出算

admin2014-07-18  61
问题 设将n(n，1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0＜P＜n)个位置，即将R中的数据由(X1，X2，…，Xn)变换为(XP，XP+1，…，XN，X1，XP-1)，要求：
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。
    (3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案(1)基本设计思想： 将数组{a1，a2，a3，…， ap，ap+1，…，an}先进行全部逆转，然后分别对{ap，…，an-1，an} {a1，a2，a3，…，ap}进行再次逆转。 (2)算法描述： void sift_left(int a[]，int n，int p){ Reverse(a，0，n-1)；／／移动了3n／2次数据； Reverse(a，0，n-p-1)；／／移动了3(n-p)／2次数据； Reverse(a，n-p，n-1)；}／／移动了3p／2次数据； void Reverse(int A[]，int left，int．right){ int n=right-left+1；／／设置一个辅助空间； if(n<=1)return 0；／／数组为空； for(int i=0；i
解析
转载请注明原文地址:https://kaotiyun.com/show/y4xi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)