一个数组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
书上提供了一种"投机取巧"的思路,哈哈
所以直接照着书上敲的
#include<cstdio>
int main()
{
int a[110];
int n,m,count=0; //记录已输出的个数
scanf("%d%d",&n,&m);
m=m%n;//修正m
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=n-m;i<n;i++){ //输出n-m号到n-1号
printf("%d",a[i]);
count++;//已输出数的个数加1
if(count<n)printf(" "); //如果已经输出数的个数小于n,则输出空格
}
for(int i=0;i<n-m;i++){ //输出0号到n-m-1号
printf("%d",a[i]);
count++;
if(count<n)printf(" ");
}
return 0;
}
不过也提到了在后面的章节提供了一种的符合题意的(?)
emm 先敲一遍...看到那一章再回过头来做这题好了..
#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=m%n;//修正m
if(m!=0){//如果m==0,直接输出数组即可,不需要执行这部分
int d=gcd(m,n);//d为m和n的最大公约数
for(int i=n-m;i<n-m+d;i++){//枚举一个最大公约数的范围
temp=a[i];//把当前位置元素先拿走
pos=i;//记录当前要处理的位置
do{
//计算下一个要处理的位置
next=(pos-m+n)%n;
//如果下一个要处理的位置不是初始点
//则把下一个个位置的元素赋值给当前处理的位置
if(next!=i)a[pos]=a[next];
else a[pos]=temp;//把一开始拿走的元素赋值给最后这个空位
pos=next;//传递位置
} while(pos!=i);//循环直到当前处理位置回到初始位置结束
}
}
for(int i=0;i<n;i++){//输出数组
printf("%d",a[i]);
if(i<n-1) printf(" ");
}
return 0;
}