普通移位:
若数组想从某一位开始向右移n位,一般是从数组的最后一位开始逐次向右移位。
程序如下:
View Code
#include <iostream> #include <stdlib.h> using namespace std; int s[11]={1,2,3,4,5,6,7,8,9,0}; void main() { for (int i=0;i<11;i++) { cout<<s[i]; } cout<<endl; //移位代码,此地假设向右移移位 for (int j=10;j>0;j--) { s[j]=s[j-1]; } for (int k=0;k<11;k++) { cout<<s[k]; } cout<<endl; }
程序运行结果截图:
循环移位,下面是自己编的一个:
View Code
#include<iostream> #include<stdlib.h> using namespace std; int s[10]={1,2,3,4,5,6,7,8,9,0}; void main() { int temp; //向右循环移位3位 for(int i=1;i<=3;i++) { temp=s[9]; for(int j=9;j>=1;j-- ) { s[j]=s[j-1]; } s[0]=temp; } for(int k=0;k<=9;k++) { cout<<s[k]; } }
其实原理就是通过一个间接的变量,对数组进行移位。假设数组长度为N,需要循环右移K次,则算法的复杂度为O(K*N),当K>N时算法的复杂度甚至大于O(N^2)。
运行结果图:
通过分析可以发现,K>N时所移动的位数和K'=K%N相同,如是衍生出如下算法:
View Code
#include<iostream> #include<stdlib.h> using namespace std; int s[10]={1,2,3,4,5,6,7,8,9,0}; void main() { int temp; int K,KK; K=99; //向右循环移位K位 KK=K%10;//数组长度为10 for(int i=1;i<=K;i++) { temp=s[9]; for(int j=9;j>=1;j-- ) { s[j]=s[j-1]; } s[0]=temp; } for(int k=0;k<=9;k++) { cout<<s[k]; } cout<<endl; }
运行结果略。
在网上找到一种复杂度为:O(N)的方法,原理如下:
假设原序列为:abcd1234
移位4位后为:1234abcd
移位过程可以表示成如下步骤:
逆序排列abcd:dcba1234
逆序排列1234:dcba4321
逆序排列dcba4321:1234abcd
也就是说需要编写一个逆序函数,并进行三次逆序变换。
代码如下:
View Code
1 #include<iostream> 2 #include<stdlib.h> 3 using namespace std; 4 void Reverse(int *arr,int b,int e); 5 int s[10]={1,2,3,4,5,6,7,8,9,0}; 6 void main() 7 { 8 int k,kk,N; 9 N=10; 10 k=99; 11 kk=k%10; 12 //下面为循环移位部分 13 Reverse(s,0,N-kk-1); 14 Reverse(s,N-kk,N-1); 15 Reverse(s,0,N-1); 16 //显示 17 for(int i=0;i<=9;i++) 18 { 19 cout<<s[i]; 20 } 21 cout<<endl; 22 } 23 void Reverse(int *arr,int b,int e) 24 { 25 int temp; 26 for(;b<e;b++,e--) 27 { 28 temp=arr[e]; 29 arr[e]=arr[b]; 30 arr[b]=temp; 31 } 32 }
|
请发表评论