题库 信息学奥赛题库 题目列表 (序列重排)全局数组变量 a 定义如下:&nb...
问答题

(序列重排)全局数组变量 a 定义如下: 

const int SIZE = 100;

int a[SIZE], n;

它记录着一个长度为 n 的序列 a[1], a[2], …, a[n]。


现在需要一个函数,以整数 p (1 ≤ p ≤ n)为参数,实现如下功能:将序列 a 的前 p 个数与后 n – p 个数对调,且不改变这 p 个数(或 n – p 个数)之间的相对位置。例如,长度为 5 的序列 1, 2, 3, 4, 5,当 p = 2 时重排结果为 3, 4, 5, 1, 2。


有一种朴素的算法可以实现这一需求,其时间复杂度为 O(n)、空间复杂度为 O(n):

void swap1(int p)
{
    int i, j, b[SIZE];
    for (i = 1; i <= p; i++)
        b[    (1)    ] = a[i];
    for (i = p + 1; i <= n; i++) 
        b[i - p] =    (2)    ;     
    for (i = 1; i <=    (3)    ; i++)    
        a[i] = b[i];    
}

我们也可以用时间换空间,使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法:

void swap2(int p)
{
int i, j, temp;    
for (i = p + 1; i <= n; i++) {    
    temp = a[i];      
    for (j = i; j >=    (4)    ; j--)    
        a[j] = a[j - 1];    
        (5)    = temp;    
    }    
}
题目信息
完善程序 2013年 初赛
-
正确率
0
评论
208
点击