本文共 2170 字，大约阅读时间需要 7 分钟。

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 21 2 3 4 5 6

输出样例:

5 6 1 2 3 4

代码一 

#include
   
    int main() {	int m, n, a[110];	scanf("%d%d", &n, &m);	m %= n;	for(int i = 0; i < n; i++) {		if (i + m < n) scanf("%d", &a[i + m]);		else scanf("%d", &a[i + m - n]);	}	for(int i = 0; i < n; i++) {		printf("%d", a[i]);		if(i < n - 1) printf(" ");	}	return 0;}
   

代码二 

#include
   
    int main() {	int m, n, a[110];	scanf("%d%d", &n, &m);	m %= n; // m > n	for(int i = 0; i < n; i++) {		scanf("%d", &a[i]);	}	bool hashTable[110]{false}; // 记录填过数的位置 	for(int i = 0; i < m; i++) { // 位移m个位置需要m轮位移 		int p1 = (m + i) % n, p2 = p1; // p1为空位置下标 		int temp = a[p1];		while(true){			if(p2 >= m) p2 = p2 - m; // p2为应位移到p1的数的下标 			else p2 = n - m + p2;			if(p2 == (m + i) % n){ // 如果待移的数和暂存的数相同 				a[p1] = temp;				hashTable[p1] = true; // 标记已位移好的位置 				break;			}			if(hashTable[p1]) break; // 位移前检查该位置是否位移好了，位移好则结束本轮循环 			a[p1] = a[p2];			hashTable[p1] = true;			p1 = p2; // p2的位置空出 		}	}	for(int i = 0; i < n; i++) {		printf("%d", a[i]);		if(i < n - 1) printf(" ");	}	return 0;}
   

 若数组大小为n，则需n次移动

代码三 

#include
   
    void reverse(int a[], int start, int end) {	for(int i = start; i <= (start + end) / 2; i++) {		int temp = a[i];		a[i] = a[start + end - i];		a[start + end - i] = temp;	}} int main() {	int n, m;	scanf("%d %d", &n, &m);	m %= n;	int a[n];	for(int i = 0; i < n; i++) {		scanf("%d", &a[i]);	}	reverse(a, 0, n-m-1);	reverse(a, n-m, n-1);	reverse(a, 0, n-1);	printf("%d", a[0]);	for(int i=1; i < n; i++) {		printf(" %d", a[i]);	}	printf("\n");	return 0;}
   

注解

（法一），不移动元素，改变printf的输出元素顺序即可。是偷懒的做法。

先反转前面部分，再反转后面部分，最后再对整体进行反转。三步走策略。

此外，此题有一个坑点，M有可能大于等于N。