#include<iostream> using namespace std; int gcd(int x,int y); int main() { int n,k; cout<<"请输入数组的维数"<<endl; cin>>n; int *p=new int[n]; for(int i=0;i<n;i++) { p[i]=i; } cout<<"请输入移动的位数"<<endl; cin>>k; k=k%n; int num=gcd(n,k); if(num==1) { int j=0; int temp=p[j]; for(int i=0;i<n;i++) { j=(j+k)%n; temp=temp+p[j]; p[j]=temp-p[j]; temp=temp-p[j]; } } else { for(int i=0;i<num;i++) { int j=i; int temp =p[i]; for(int ii=0;ii<n/num;ii++) { j=(j+k)%n; temp=temp+p[j]; p[j]=temp-p[j]; temp=temp-p[j]; } } } for(i=0;i<n;i++) { cout<<p[i]<<" "; } cout<<endl; return 0; } int gcd(int x,int y) //欧几里得辗转相除法求两数的最大的公约数 { if(x<y) return gcd(y,x); if(x%y!=0) return gcd(y,x%y); else return y; }3、时间复杂度最小,总共只移动n+1次,具体思路如下:首先将一个元素放入辅助节点,由于要移动k位,肯定有一个元素会移动到刚才的节点,以此类推,最后肯定会空余一个节点,然后将辅助节点的元素放入即可。具体程序实现如下:
#include<iostream> using namespace std; int gcd(int x,int y); int main() { int n,k; cout<<"请输入数组的维数"<<endl; cin>>n; int *p=new int[n]; for(int i=0;i<n;i++) { p[i]=i; } cout<<"请输入移动的位数"<<endl; cin>>k; k=k%n; int num=gcd(n,k); if(num==1) { int j=0; int temp=p[0]; for(int i=0;i<n-1;i++) { p[j]=p[(j+n-k)%n]; j=(j+n-k)%n; } p[(n-1)*(n-k)%n]=temp; } else { for(int i=0;i<num;i++) { int j=i; int temp =p[j]; for(int ii=0;ii<n/num-1;ii++) { p[j]=p[(j-k+n)%n]; j=(j-k+n)%n; } p[((n/num-1)*(n-k)+i)%n]=temp; } } for(i=0;i<n;i++) { cout<<p[i]<<" "; } cout<<endl; return 0; } int gcd(int x,int y) //欧几里得辗转相除法求两数的最大的公约数 { if(x<y) return gcd(y,x); if(x%y!=0) return gcd(y,x%y); else return y; }
原文:http://blog.csdn.net/tengweitw/article/details/24925075