B1008 数组元素循环右移问题 (20分)【C语言】
原题链接
题目中虽然给出很多限制条件,比如不允许使用另外的数组,但是只要求输出最终的结果,因此不论用什么方法移动,只要结果正确即可。
我的移动方法 :先让前N-M个数字倒序,然后让后N个数字倒序,最终将整个数组倒序即可得到最终结果。(需要用到函数)
晴神的移动方法1 :直接按题目要求输出数组的方法,比我的移动次数少了很多,更加简洁符合题目要求。
**晴神的移动方法2:**将序列中一个元素先拿出至临时变量,然后将空出的位置将要移动到这个位置的元素代替,再把新空出的位置用将要移动到这个新空出的位置的元素代替,以此类推,直到所有元素移动完毕
注意!
- M可能等于0,因此要考虑M=0时直接输出整个数组。
- M可能大于N,向右移动N个位置等同于没有移动,因此令M=M%N。
- 最终输出结果不允许最后有空格,可以先输出第一个数字,后面的数字在循环输出时,在数字前面加上空格。
题目描述:
一个数组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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <stdio.h> void Reverse(int A[], int left, int right) { int i, j, t; i = left; j = right; while(i<j){ t = A[i]; A[i] = A[j]; A[j] = t; ++i; --j; } } int main() { int N, M, i; scanf("%d %d", &N, &M); int A[N]; for(i=0; i<N; ++i){ scanf("%d", &A[i]); } M = M % N; if(M>0){ Reverse(A, 0, N-M-1); Reverse(A, N-M, N-1); Reverse(A, 0, N-1); } printf("%d", A[0]); for(i=1; i<N; ++i){ printf(" %d", A[i]); } return 0; }
晴神的实现代码1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#include <stdio.h> int main() { int a[110]; int n, m, i, cnt=0; scanf("%d%d", &n, &m); m = m % n; for(i=0; i<n; ++i){ scanf("%d", &a[i]); } for(i=n-m; i<n; ++i){ printf("%d", a[i]); cnt++; if(cnt<n) printf(" "); } for(i=0; i<n-m; ++i){ printf("%d", a[i]); cnt++; if(cnt<n) printf(" "); } return 0; }
晴神的实现代码2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38#include <cstdio> int gcd(int a, int b){ //a,b的最大公约数 if(b==0) return a; else return gcd(b, a%b); } int main() { int a[110]; int n, m, temp, pos, next; //temp为临时变量,pos存放当前处理的位置,next为下一个要处理的位置 scanf("%d %d", &n, &m); for(int i=0; i<n; ++i){ scanf("%d", &a[i]); } m %= n; if(m!=0){ int d = gcd(n, m); for(int i=n-m; i<n-m+d; ++i){ //按最大公约数确定要遍历移动的数字范围 temp = a[i]; //temp存储开始位置的元素 pos = i; //pos记录当前处理的位置 do{ next = (pos-m+n) % n; //计算除移动后该位置应该放置的元素 if(next!=i) a[pos] = a[next]; //若不是初始位置,则将元素放过来 else a[pos] = temp; //若是初始位置,则将temp中的变量放过来 pos = next; //处理位置移动 }while(pos!=i); //循环直到初始元素找到应该待的位置 } } for(int i=0; i<n; ++i){ printf("%d", a[i]); if(i<n-1) printf(" "); } return 0; }
最后
以上就是欣喜玫瑰最近收集整理的关于B1008 数组元素循环右移问题 (20分)【C语言】的全部内容,更多相关B1008内容请搜索靠谱客的其他文章。
发表评论 取消回复