using namespace std;
//数组中有n个元素将其顺序后移k位 01234->23401 k=3
void OrderMove1();
void OrderMove2();
void OrderMove3();
int main ()
{
OrderMove1();
OrderMove2();
OrderMove3();
}
void OrderMove1()
{
int N = 6;
int num[N] = {1, 2, 3, 4, 5, 6};
int k = 3;//元素循环移动k位
int t[N];//必须要开一个辅助数组！！！不可以直接将原数组的元素进行交换
//因为无法确定循环执行次数有可能会出现将已经一定的元素重新交换
for(int i = 0; i < N; i++)
{
t[(i + k) % N] = num[i];//直接将元素放入辅助数组的正确位置
}
for(int i = 0; i < N; i++)
cout << t[i] << " ";
cout << endl;
}
void OrderMove2()//没有开辟新的辅助数组 但是进行多次循环
{
int N = 6;
int num[N] = {1, 2, 3, 4, 5, 6};
int k = 3;//元素循环移动k位
int t;
for(int i = 0; i < k; i++)//移动k次就进行k次循环
{
t = num[N - 1];//实质是将末尾元素保留 然后将前边的元素依次向后拷贝 最终将值赋给第一个元素
for(int j = N - 1; j > 0; j--)
{
num[j] = num[j - 1];
}
num[0] = t;
}
for(int i = 0; i < N; i++)
cout << num[i] << " ";
cout << endl;
}
void OrderMove3()//没有开辅助数组也没有多次循环 利用了最大公约数的性质
{
int N = 6;
int k = 3;
int t = 1;
int num[N] = {1, 2, 3, 4, 5, 6};
for(int i = 2; i <= N && i <= k; i++)//求最大公约数
{
while(N % i == 0 && k % i == 0)
{
t *= i;
N /= i;
k /= i;
}
}
k = 3;//一定要记得对N,k进行复原 因为上一步求最大公约数的过程中两个数的值已经发生了改变
N = 6;
int b0, temp, b1;
for(int j = 0; j < t; j++)
{
b0 = num[j];
temp = j;
for(int i = 0; i < N / t; i++)//用N/t确定了移动的次数 不会出现一个已经在正确位置的元素重复移动的情况
{
temp = (temp + k) % N;//计算好正确位置的下标 之后利用循环相距一定距离逐次移动
b1 = num[temp];
num[temp] = b0;
b0 = b1;
}
}
for(int i = 0; i < N; i++)
cout << num[i] << " ";
cout << endl;
}