PAT-B 1008. 数组元素循环右移问题 (20)

2019-11-10 17:10:20

字体：大中小

来源：转载

供稿：网友

题目链接在此。

虽然这个题目在题干中有非常多的限制，“不允许有额外数组”、“移动次数最少”等等，但是PAT是一个黑盒测试，只需要结果正确，能过通过所有测试点即可。所以不需要被这些限制所限制，这里只写出两种方法，一种是我自己的想法，用了“简单模拟”的思想，即题目说“数组右移”，那么我就数组右移，故这种方法的关键就在如何右移数组；另外一种方法是《算法笔记》中的，这种方法更加直接，直接按照一定的规律输出，甚是巧妙。

下面是我的代码：

#include<stdio.h>int main(){ int N,M; int a[105]; scanf("%d %d",&N, &M); M = M % N; //题目并没有保证M<N for( int i = 0 ; i < N; i++){ scanf("%d",a+i); } if(M == 0){ for(int i = 0 ; i < N; i++){ if( i == N-1){ PRintf("%d/n",a[i]); }else{ printf("%d ",a[i]); } } } else{ //数组元素右移 for(int j = 0 ; j < M; j++){ for(int i = N-1 ; i > 0; i--){ int temp = a[i]; a[i] = a[i-1]; a[i-1] = temp; } } for(int i = 0 ; i < N; i++){ if( i == N-1){ printf("%d/n",a[i]); }else{ printf("%d ",a[i]); } } } return 0;} 本方法的关键就在数组元素右移那两个for循环处，第一个for循环控制移动次数（该题就是M次），第二个for循环用来完成数组中所有元素的循环右移操作。（M==0时可以不特判）还有个地方需要注意，题目并没有保证M<N,所以需要拿到N,M之后，需要做M=M%N操作，以方便后续算法。

下面是《算法笔记》的代码：

#include<stdio.h>int main(){ int N,M; int a[105]; scanf("%d %d",&N,&M); M = M % N; for(int i = 0 ; i < N; i++){ scanf("%d",a+i); } int count = 0; //用来计数，为"最后一个元素不输出空格服务" for(int i = N-M; i < N; i++){ count++; printf("%d",a[i]); if(count < N){ printf(" "); } } for(int i = 0 ; i < N-M; i++){ count++; printf("%d",a[i]); if(count < N){ printf(" "); } } return 0;}这个方法就是找到了元素输出的规律，然后代码实现之。

《算法笔记》购买地址。

上一篇：HDOJ(HDU).1045 Fire Net (DFS)

下一篇：NYOJ 773 开方数