概述
一个数组A中存有N(>0)个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M(≥0)个位置，即将A中的数据由(A0A1⋯AN−1)变换为(AN−M⋯AN−1A0A1⋯AN−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位置
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4
5 using namespace std;
6
7 int main()
8 {
9 int N, M, i;
10 vector<int> vec;
11 cin >> N >> M;
12 int mount = N;
13 while (mount--)
14 {
15 cin >> i;
16 vec.push_back(i);
17
18 }
19 rotate(vec.begin(), vec.end() - (M % N), vec.end()); //循环右移
20 //rotate(vec.begin(), vec.begin() + (M % N), vec.end()); //循环左移
21 vector<int>::const_iterator iter;
22 for (iter = vec.begin(); iter != vec.end() - 1; ++iter)
23 cout << *iter << " ";
24 cout << *iter << endl;
25 return 0;
26 }
2.C的一般方法：
先写一个循环右移一位的函数，然后调用该函数M次， 即可使数组循环右移M位
1 #include <stdio.h>
2 #define MAXN 100
3
4 void CircleMove(int *array, int N);
5
6 int main()
7 {
8 int Number[MAXN], N, M;
9 int i;
10 scanf_s("%d %d", &N, &M);
11 for (i = 0; i < N; i++)
12 {
13 scanf_s("%d", &Number[i]);
14 }
15 M %= N; //当M大于等于N时转化成等价的小于N的数
16 for (i = 0; i < M; i++) //调用移位函数M次
17 CircleMove(Number, N);
18 for (i = 0; i < N -1; i++)
19 printf("%d ", Number[i]);
20 printf("%d", Number[i]);
21 return 0;
22 }
23
24 void CircleMove(int *array, int N)
25 {
26 int i, ArrayEnd;
27 ArrayEnd = array[N - 1]; //先最后一个元素记录下来，因为待会会被覆盖掉
28 for (i = N -1; i > 0; i--)
29 array[i] = array[i - 1];
30 array[0] = ArrayEnd;
31 }
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()函数，效果是一样的。)
1 #include <stdio.h>
2 #define MAXN 100
3 #define Swap(a, b) a^= b, b^= a, a ^= b; //通过连续三次以后运算符交换a与b
4
5 void RightShift(int array[], int N, int M);
6
7 int main()
8 {
9 int Number[MAXN], N, M;
10 int i;
11 scanf_s("%d %d", &N, &M);
12 for (i = 0; i < N; i++)
13 scanf_s("%d", &Number[i]);
14 M %= N;
15 RightShift(Number, N);
16 for (i = 0; i < N - 1; i++)
17 printf("%d", Number[i]);
18 printf("%d", Number[N - 1]);
19 return 0;
20 }
21
22 void RightShift(int array[], int N, int M)
23 {
24 int i, j;
25 if (M > 0 && M < N)
26 {
27 for (i = 0, j < N - 1; i < j; i++, j--) //逆转N个数据
28 Swap(array[i], array[j]);
29 for (i = 0, j < M - 1; i < j; i++, j--) //逆转前M个数据
30 Swap(array[i], array[j]);
31 for (i = M, j = N - 1; i < j; i++, j--) //逆转后N - M个数据
32 Swap(array[i], array[j]);
33 }
34 }
逆转函数可以使用头文件 algorithm 中的 reverse()函数，这个函数可以将给定数组区间或迭代器区间的内容反转，使用方法是：reverse(a, a + 4); 加上a是数组，所以上面方法三的代码可以进一步得到简化：(使用这个头文件必须包含using namespace std这个命名空间)
1 #include <stdio.h>
2 #include <algorithm>
3 using namespace std;
4
5 int arr[110] = { 0 };
6
7 int main()
8 {
9 int n, m;
10 scanf("%d %d", &n, &m);
11 for (int i = 0; i < n; i++){
12 scanf("%d", &arr[i]);
13 }
14 m %= n; // 修正m的值
15 reverse(arr, arr + n); // 反转 0 - n之间的数字
16 reverse(arr, arr + m); // 反转 0 - (m-1)之间的数字
17 reverse(arr + m, arr + n); // 反转 m - (n-1)之间的数字
18
19 for (int i = 0; i < n; i++){
20 if (i > 0)
21 printf(" ");
22 printf("%d", arr[i]);
23 }
24 return 0;
25 }
4 . 利用n和m的最大公约数(这个方法还不是很理解)
从N - M为开始移动，一直到(n - m + d), d 是 m 和 n 的最大公约数。每次将当前元素存储在一个临时变量上，然后将(i - M)位的元素移动到当前位置，直到(i- M) == (i + M) % N,此时将临时变量上的元素放置到该位置上，进入下次循环
1 int ans[110];
2
3 int gcd(int a, int b){
4 return !b ? a : gcd(b, a % b);
5 }
6
7 int main()
8 {
9 // 读取输入
10 freopen("in.txt", "r", stdin);
11 int n, m;
12 int temp, pos, next;
13 scanf("%d %d", &n, &m);
14 for (int i = 0; i < n; i++){
15 scanf("%d", &ans[i]);
16 }
17
18 m %= n; // 修正m
19
20 // 如果m == 0，则不用移动,m != 0才需移动
21 if (m != 0){
22 int d = gcd(m, n);
23 for (int i = n - m; i < n - m + d; i++){
24 // 每次将当前元素存储在一个临时变量上
25 temp = ans[i];
26
27 // 然后将(i - M)位的元素移动到当前位置, 直到(i- M) == (i + M) % N
28 pos = i;
29 do{
30 // 计算下一个要处理的位置
31 next = (pos - m + n) % n;
32 // 如果下一个位置不是初始点
33 // 则把下一个位置的元素赋值给当前处理位置
34 if (next != i)
35 ans[pos] = ans[next];
36 else
37 ans[pos] = temp;
38 pos = next;
39 } while (pos != i);
40 }
41 }
42
43 // 输出数组
44 for (int i = 0; i < n; i++){
45 printf("%d", ans[i]);
46 if (i < n- 1)
47 printf(" ");
48 }
50
51 fclose(stdin);
52 return 0;
53 }
最后
以上就是爱笑绿草为你收集整理的实验案例2-2：数组元素循环右移问题的全部内容，希望文章能够帮你解决实验案例2-2：数组元素循环右移问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复