实验案例2-2：数组元素循环右移问题

　　　　　　　　　　1008 数组元素循环右移问题 (20分)

一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由（A​0​​A​1​​⋯A​N−1​​）变换为（A​N−M​​⋯A​N−1​​A​0​​A​1​​⋯A​N−M−1​​）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式:

每个输入包含一个测试用例，第1行输入N（1≤N≤100）和M（≥0）；第2行输入N个整数，之间用空格分隔。

输出格式:

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例:

6 2
1 2 3 4 5 6

输出样例:

5 6 1 2 3 4

1.C++方法，利用rotate函数

rotate(beg, mid, end),该函数接受三个迭代器， 将迭代器所在的容器的元素循环移动，使得mid元素成为首元素，随后是mid + 1到end之前的元素，
再接着是beg到mid 之间的元素，返回一个迭代器，指向原来在beg位置的元素
rotate_copy(beg, mid, end, dest),即将变换过后的元素保存在目的容器的dest位置

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int N, M, i;
    vector<int> vec;
    cin >> N >> M;
    int mount = N;
    while (mount--)
    {
        cin >> i;
        vec.push_back(i);

    }
    rotate(vec.begin(),  vec.end() - (M % N), vec.end());        //循环右移
    //rotate(vec.begin(), vec.begin() + (M % N), vec.end());    //循环左移
    vector<int>::const_iterator iter;
    for (iter = vec.begin(); iter != vec.end() - 1; ++iter)
        cout << *iter << " ";
    cout << *iter << endl;
    return 0;
}

2.C的一般方法：

先写一个循环右移一位的函数，然后调用该函数M次， 即可使数组循环右移M位

#include <stdio.h>
#define MAXN 100

void CircleMove(int *array, int N);

int main()
{
    int Number[MAXN], N, M;
    int i;
    scanf_s("%d %d", &N, &M);
    for (i = 0; i < N; i++)
    {
        scanf_s("%d", &Number[i]);
    }
    M %= N;            //当M大于等于N时转化成等价的小于N的数
    for (i = 0; i < M; i++)            //调用移位函数M次
        CircleMove(Number, N);
    for (i = 0; i < N -1; i++)
        printf("%d ", Number[i]);
    printf("%d", Number[i]);
    return 0;
}

void CircleMove(int *array, int N)
{
    int i, ArrayEnd;
    ArrayEnd = array[N - 1];        //先最后一个元素记录下来，因为待会会被覆盖掉
    for (i = N -1; i > 0; i--)
        array[i] = array[i - 1];
    array[0] = ArrayEnd;
}

 

3.C的简单解法

先用宏定义define 定义一个两个数相交换的的函数，该函数利用了三次异或运算符      

异或运算符有一个性质，假如 a ^ b = c;那么 a ^ c = b; b ^ c = a;

#define Swap(a, b) a^ = b, b ^= a, a ^= b;　　　　//交换两个数的宏定义函数，

对这个函数的解读：

 a ^= b 就是  a = a ^ b,此时a 等于上面说的C

b ^= a,就是 b = b ^ a,注意，这里的a 已经变成C了，所以相当于 b = b ^ C ---> b = a;

同理，a ^= b,就是  a = a ^ b,需要注意的是，等式右边的a在第一步变换中变成了C，b 在第二步变换中变成了a, 所以这个等式就相当于a = C ^ a ------> a = b;

所以就完成了交换。

接下来程序中利用三次逆转，实现了循环右移M位，（这种方法很神奇）

第一次：逆转整个数组

第二次：在第一步的基础上逆转数组前M个元素

第三次: 逆转数组后N- M个元素

 （Swap()函数可以直接按使用algorithm 中已经有的swap()函数，效果是一样的。）

#include <stdio.h>
#define MAXN 100
#define Swap(a, b) a^= b, b^= a, a ^= b;    //通过连续三次以后运算符交换a与b

void RightShift(int array[], int N, int M);

int main()
{
    int Number[MAXN], N, M;
    int i;
    scanf_s("%d %d", &N, &M);
    for (i = 0; i < N; i++)
        scanf_s("%d", &Number[i]);
    M %= N;
    RightShift(Number, N);
    for (i = 0; i < N - 1; i++)
        printf("%d", Number[i]);
    printf("%d", Number[N - 1]);
    return 0;
}

void RightShift(int array[], int N, int M)
{
    int i, j;
    if (M > 0 && M < N)
    {
        for (i = 0, j < N - 1; i < j; i++, j--)        //逆转N个数据
            Swap(array[i], array[j]);                
        for (i = 0, j < M - 1; i < j; i++, j--)        //逆转前M个数据
            Swap(array[i], array[j]);
        for (i = M, j = N - 1; i < j; i++, j--)        //逆转后N - M个数据
            Swap(array[i], array[j]);
    }
}

逆转函数可以使用头文件 algorithm 中的 reverse()函数，这个函数可以将给定数组区间或迭代器区间的内容反转，使用方法是：reverse(a, a + 4); 加上a是数组，所以上面方法三的代码可以进一步得到简化：（使用这个头文件必须包含using namespace std这个命名空间）

#include <stdio.h>
#include <algorithm>
using namespace std;

int arr[110] = { 0 };

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    m %= n;            // 修正m的值
    reverse(arr, arr + n);            // 反转 0 - n之间的数字
    reverse(arr, arr + m);            // 反转 0 - (m-1)之间的数字
    reverse(arr + m, arr + n);        // 反转 m - (n-1)之间的数字

    for (int i = 0; i < n; i++){
        if (i > 0)
            printf(" ");
        printf("%d", arr[i]);
    }
    return 0;
}

4 . 利用n和m的最大公约数(这个方法还不是很理解）

从N - M为开始移动，一直到(n - m + d), d 是 m 和 n 的最大公约数。每次将当前元素存储在一个临时变量上，然后将（i - M）位的元素移动到当前位置，直到（i- M) == (i + M) % N,此时将临时变量上的元素放置到该位置上，进入下次循环

int ans[110];

int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}

int main()
{
    // 读取输入
    freopen("in.txt", "r", stdin);
    int n, m;
    int temp, pos, next;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++){
        scanf("%d", &ans[i]);
    }

    m %= n;        // 修正m

    // 如果m == 0，则不用移动,m != 0才需移动
    if (m != 0){
        int d = gcd(m, n);
        for (int i = n - m; i < n - m + d; i++){
            // 每次将当前元素存储在一个临时变量上
            temp = ans[i];

            // 然后将（i - M）位的元素移动到当前位置, 直到（i- M) == (i + M) % N
            pos = i;
            do{
                // 计算下一个要处理的位置
                next = (pos - m + n) % n;
                // 如果下一个位置不是初始点
                // 则把下一个位置的元素赋值给当前处理位置
                if (next != i)
                    ans[pos] = ans[next];
                else
                    ans[pos] = temp;
                pos = next;
            } while (pos != i);
        }
    }

    // 输出数组
    for (int i = 0; i < n; i++){
        printf("%d", ans[i]);
        if (i < n- 1)
            printf(" ");
    }

    fclose(stdin);
    return 0;
}