PAT-B-1008 数组元素循环右移问题

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

输入格式:

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

输出格式:

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

输入样例:

1 2	6 2 1 2 3 4 5 6

输出样例:

1	5 6 1 2 3 4

数组平移问题分析

数组左移k位
1. 将前k位反转，后k位反转
2. 将整个数组反转
数组右移k位
1. 将整个数组反转
2. 将前k位反转，后k位反转

Code

#include <iostream>
#include <algorithm>

using namespace std;

int main(){

    int n,m;
    scanf("%d%d",&n,&m);

	//m可能比n大，因此对m先做一个优化，方便后面计算
    m=m%n;
    int* arr = new int[n];
    int i,temp;
    for(i=0;i<n;i++){
        scanf("%d",&temp);
        arr[i]=temp;
    }
    //右移，先反转全部
    reverse(arr,arr+n);
    reverse(arr,arr+m);
    reverse(arr+m,arr+n);

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

移动次数最少

//为了避免有些数组在一轮移动之后就已经是最终数组而继续做无用的循环，如长度为8，右移3位。只需要轮迭代就已经完成全部元素的平移
//这里引出一个关键的知识点——最大公约数d
//整个循环的次数是从n-m号位开始枚举起始位直到到n-m+d-1位结束。
#include <iostream>
using namespace std;

int gcd(int n,int m){
	//当余数为0，返回n
	if(m==0)return n;
	return gcd(m,n%m);
}
int main(){

    int n,m;
    scanf("%d%d",&n,&m);
	int arr[110];
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	
	int temp,pos;
	//还是先修正m，因为m可能比n大
    m=m%n;
    //当有平移需求才平移，否则输出原数组
   	if(m!=0){
   		int d=gcd(n,m);
   		for(int i=n-m;i<=n-m+d-1;i++){
   			temp=arr[i];
   			pos=i;
   			do{
   				//计算当前位置前m位的索引
   				int next = (pos-m+n)%n;
   				//若计算的next为i，说明走到最后一步了，否则平移数组
   				if(next!=i)
   					arr[pos]=arr[next];
   				else
   					arr[pos]=temp;
   				pos=next;
   			}while(pos!=i)//若pos=i则说明已经迭代一轮了
   		}
   	}
    
    //最后输出结果数组
    for(i=0;i<n;i++){
        printf("%d",arr[i]);
        if(i!=n-1)
            printf(" ");
    }
	return 0;
}