完善程序:(序列重排)全局数组变量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[①] = a[i];
for ( i = p + 1; i <= n; i++ )
b[i - p] = ②;
for ( i = 1; i <= ③; i++ )
a[i] = b[i];
}
我们也可以用时间换空间,使用时间复杂度为O(n²)、空间复杂度为O(1)的算法:
void swap2(int p)
{
int i, j, temp;
for ( i = p + 1; i <= n; i++ )
{
temp = a[i];
for ( j = i; j >= ④; j-- )
a[j] = a[j - 1];
⑤ = temp;
}
}问题1:
问题2:
问题3:
问题4:
问题5:
*