PAT乙级 1008 数组元素循环右移问题 (20分)（C语言 + 详细注释 + 两种方法实现）

一个数组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

//法一：一个一个的挪，每次记录最后一个元素，然后把前面n - 1个元素一次后挪一位，再把开始记录的最后一个数放到第一个位置，重复m次上述过程即可。虽然也能AC，但是移动次数有点多。

#include<stdio.h>
#define MAX 105

int main(){
    int m, n, temp, i;
    int v[MAX];
    scanf("%d %d", &n, &m);     /* n个数向右移动m个位置 */
    for(i = 0; i < n; i++)
        scanf("%d", &v[i]);
    m %= n;          //优化下，令m < n,因为以n的倍数移动的话结果不变，去掉那些没必要的操作
    for(i = 1; i <= m; i++){
        temp = v[n - 1];    /* 记录最后一个元素 */
        for(int k = n - 2; k >= 0; k--)
            v[k + 1] = v[k];    /* 从倒数第二个元素开始，依次往后挪 */
        v[0] = temp;        /* 把最后一个元素放到开头 */
    }
    for(i = 0; i < n; i++)
        printf("%d%s", v[i], (i < n - 1) ? " " : "");             //每两个数之间有空格，行尾不能有多余空格时可以用三元运算符

    return 0;
}

//法二：（优化处理）在读入数组中的元素时进行处理，如果不考虑循环移位的话（即总体直接向后移，可以假设数组够大），那么原本下标为i的元素，移动m次后，下标变为i + m，再考虑循环移位，那么下标就变成（i + m）% n,至于正确性证明，大家可以用特殊法，即令m等于0，一次都不移动，那么下标是不变的，符和题意。

#include<stdio.h>
#define MAX 105

int main() {
    int m, n, x, i;
    int v[MAX];
    scanf("%d %d", &n, &m);
    m %= n;   
    for (i = 0; i < n; i++) {
        scanf("%d", &x);
        v[(i + m) % n] = x;
    }
    for (i = 0; i < n; i++)
        printf("%d%s", v[i], (i < n - 1) ? " " : "");
 
    return 0;
}

最后

以上就是苗条枕头最近收集整理的关于PAT乙级 1008 数组元素循环右移问题 (20分)（C语言 + 详细注释 + 两种方法实现）的全部内容，更多相关PAT乙级内容请搜索靠谱客的其他文章。