该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
 
西工大机考《C语言程序设计》网考
 
寻求答案(非免费)找我Q和V:2082851315
 
试卷总分:100 得分:96
 
一、 单选题 (共 35 道试题,共 70 分)
 
1. 若有定义:int a[2][3];，以下选项中对a数组元素正确引用的是( )。
 
A.a[2][!1]
 
B.a[2][3]
 
C.a[0][3]
 
D.a[1>2][!1]
 
2. 以下描述错误的是( )。
 
A.break语句不能用于循环语句和switch语句外的任何其他语句
 
B.在switch语句中使用break语句或continue语句的作用相同
 
C.在循环语句中使用continue语句是为了结束本次循环，而不是终止整个循环
 
D.在循环语句中使用break语句是为了使流程跳出循环体，提前结束循环
 
3. 以下存储类型只有在使用时才为该类型变量分配内存的是( )。
 
A.auto和static
 
B.auto和register
 
C.register和static
 
D.static和extern
 
4. 若变量已正确定义，有以下程序段
 
int a=3,b=5,c=7;
 
if(a>b) a=b; c=a;
 
if(c!=a) c=b;
 
printf("%d,%d,%d\n",a,b,c);
 
其输出结果是( )。
 
A.程序段有语法错
 
B.3,5,3
 
C.3,5,5
 
D.3,5,7
 
5. 函数strlen("1234\0xy")的值为( )。
 
A.7
 
B.8
 
C.4
 
D.9
 
6. 若二维数组a由m列，则在a[i][j]之前的元素个数为( )。
 
A.j*m+i
 
B.i*m+j
 
C.i*m+j-1
 
D.i*m+j+1
 
7. 假定x和y为 double型，则表达式x=2,y=x+3/2的值是( )。
 
A.3.500000
 
B.3
 
C.2.000000
 
D.3.000000
 
8. 设变量已正确定义并赋值,以下正确的表达式是( )。
 
A.x=y*5=x+z
 
B.int(15.8%5)
 
C.x=y+z+5,++y
 
D.x=25%5.0
 
9. 在C语言中，设一表达式中包含有int,long,char和unsigned类型的变量和数据，则这4种类型数据转换的规则是( )。
 
A.int→unsingned→long→char
 
B.char→int→long→unsingned
 
C.char→int→unsigned→long
 
D.int→char→unsigned→long
 
10. 若有说明：int *p,m=5,n;，以下正确的程序段是( )。
 
A.p=&n;scanf("%d",&p);
 
B.p=&n;scanf("%d",*p)
 
C.scanf("%d",&n);*p=n;
 
D.p=&n;*p=m;
 
11. 在C语言中，变量的隐含存储类别是( )。
 
A.auto
 
B.static
 
C.extern
 
D.无存储类别
 
12. 函数的功能是交换变量x和y中的值，且通过正确调用返回交换的结果。能正确执行此功能的函数是( )。
 
A.funa(int *x, int *y)
 
{ int *p;
 
*p=x; *x=*y; *y=*p;
 
}
 
B.funb(int x, int y)
 
{ int t;
 
t=x; x=y; y=t;
 
}
 
C.func(int *x, int *y)
 
{ *x=*y; *y=*x;
 
}
 
D.{fund(int *x, int *y)
 
13. 在C语言中，只有在使用时才占用内存单元的变量，其存储类型是 ( )。
 
A.auto和register
 
B.extern和register
 
C.auto和static
 
D.static和register
 
14. 以下定义语句中正确的是( )。
 
A.int a=b=0;
 
B.char A=65+1,b=′b′;
 
C.float a=1,*b=&a,*c=&b;
 
D.double a=0.0;b=1.1;
 
15. 以下描述中正确的是( )。
 
A.由于do-while循环中循环体语句只能是一条可执行语句，所以循环体内不能使用复合语句
 
B.do-while循环由do开始，用while结束，在while(表达式)后面不能写分号
 
C.在do-while循环体中，是先执行一次循环，再进行判断
 
D.do-while循环中，根据情况可以省略while
 
16. 下面程序的输出结果是( )。
 
main()
 
{
 
int s,k;
 
for(s=1,k=2;k<5;k++) s+=k;
 
printf("%d\n",s);
 
A.1
 
B.9
 
C.0
 
D.15
 
17. 以读写方式打开一个已有的文件file1，下面有关fopen函数正确的调用方式为( )。
 
A.FILE *fp；fp=fopen("file1";"f");
 
B.FILE *fp；fp=fopen("file1","r+")；
 
C.FILE *fp；fp=fopen("file1","rb");
 
D.FILE *fp；fp=fopen("file1","rb+")；
 
18. 设int a=12，则执行完语句a+=a-=a*a后，a的值是( )。
 
A.552
 
B.264
 
C.144
 
D.-264
 
19. 阅读下列程序，则运行结果为( )。
 
#include "stdio.h"
 
fun()
 
{ static int x=5;
 
x++;
 
return x;\
 
A.5
 
B.6
 
C.7
 
D.8
 
20. 运行下面程序：
 
main()
 
{
 
int n1,n2;
 
scanf("%d",&n2);
 
while(n2!=0)
 
\ n1=n2%10;
 
n2=n2/10;
 
}
 
printf("%d",n1);
 
}若从键盘上输入298↙ ，则输出结果为( )。
 
A.2
 
B.29
 
C.8
 
D.0
 
21. C语言规定，在一个源程序中，main函数的位置( )。
 
A.必须在最开始
 
B.必须在系统调用的库函数的后面
 
C.可以任意
 
D.必须在最后
 
22. 已知double *p[6]; 它的含义是( )。
 
A.p是指向double类型变量的指针
 
B.p是double类型数组
 
C.p是指针数组
 
D.p是数组指针
 
23. 以下叙述中错误的是( )。
 
A.在程序中凡是以"#"开始的语句行都是预处理命令行
 
B.预处理命令行的最后不能以分号表示结束
 
C.#define MAX 是合法的宏定义命令行
 
D.C程序对预处理命令行的处理是在程序执行的过程中进行的
 
24. 为了判断两个字符串s1和s2是否相等，应当使用( )。
 
A.if(s1==s2)
 
B.if(s1=s2)
 
C.if(strcpy(s1, s2))
 
D.if(strcmp(s1, s2)==0)
 
25. 在下列结论中，只有一个是正确的，它是( )。
 
A.递归函数中的形式参数是自动变量
 
B.递归函数中的形式参数是外部变量
 
C.递归函数中的形式参数是静态变量
 
D.递归函数中的形式参数可以根据需要自己定义存储类型
 
26. 以下不正确的定义语句是( )。
 
A.double x[5]={2.0,4.0,6.0,8.0,10.0;
 
B.int y[5]={0,1,3,5,7,9;
 
C.char c1[]={′1′,′2′,′3′,′4′,′5′;
 
D.char c2[]={′\x10′, ′xa′, ′\x8′;
 
27. 有以下程序段
 
int n=0,p;
 
do
 
{ scanf("%d",&p);n++;
 
}while(p!=123&&n<10);
 
此处do-while循环的结束条件是( )。
 
A.P的值不等于123或者n的值小于10
 
B.P的值等于123并且n的值大于等于10
 
C.P的值不等于123并且n的值小于10
 
D.P的值等于123或者n的值大于等于10
 
28. 以下叙述中错误的是( )。
 
A.改变函数形参的值，不会改变对应实参的值
 
B.函数可以返回地址值
 
C.可以给指针变量赋一个整数作为地址值
 
D.当在程序的开头包含头文件stdio.h时，可以给指针变量赋NULL
 
29. 当变量c的值不为2、4、6时，值也为"真"的表达式是( )。
 
A.(c==2)︱︱(c==4)︱︱(c==6)
 
B.(c>=2&& c<=6)︱︱(c!=3)︱︱(c!=5)
 
C.(c>=2&&c<=6)&&!(c%2)
 
D.(c>=2&& c<=6)&&(c%2!=1)
 
30. 运行程序:
 
#include
 
main()
 
{
 
int n='c';
 
switch(n++)
 
{ default: printf("error");break;
 
case 'a':case 'A':case 'b':case 'B':printf("good");break;
 
case 'c':case 'C':printf("pass");
 
case 'd':case 'D':printf("warn");
 
}
 
}则输出结果是( )。
 
A.good
 
B.pass
 
C.warn
 
D.passwarn
 
31. 设有 int x=8; 则表达式 (++x*1/3) 的值是( )。
 
A.2
 
B.3
 
C.2.6
 
D.0
 
32. 下面程序的输出结果是( )。
 
main()
 
{ int x=5,y=9,z=1,t;
 
t=(x>y||x>z);
 
printf("%d\n",t);
 
A.1
 
B.0
 
C.5
 
D.3
 
33. 有以下程序
 
#include
 
main()
 
{ int x=1,y=0,a=0,b=0;
 
switch(x)
 
{ case 1:
 
switch(y)
 
{ case 0:a++; break;
 
case 1:b++; break;
 
}
 
case 2:a++; b++; break;
 
case 3:a++; b++;
 
}
 
printf("a=%d,b=%d\n",a,b);
 
}
 
A.a=1,b=0
 
B.a=2,b=2
 
C.a=1,b=1
 
D.a=2,b=1
 
34. 一个C程序的执行是从( )。
 
A.本程序的main函数开始，到main函数结束
 
B.本程序文件的第一个函数开始，到本程序文件的最后一个函数结束
 
C.本程序的main函数开始，到本程序文件的最后一个函数结束
 
D.本程序文件的第一个函数开始，到本程序main函数结束
 
35. 有以下程序
 
main()
 
{ int i,s=1;
 
for (i=1;i<50;i++)
 
if(!(i%5)&&!(i%3)) s+=i;
 
printf("%d\n",s);
 
A.409
 
B.277
 
C.1
 
D.91
 
二、 判断题 (共 15 道试题,共 30 分)
 
1. C语言的编译系统对宏命令的处理是和c程序中的其他语句同时进行编译的。
 
A.错误
 
B.正确
 
2. 设变量 a 为整型，f 是实型，i 是双精度型，则表达式10+'a'+i * f 值的数据类型不能确定为何类型。
 
A.错误
 
B.正确
 
3. (a=3)>(b=5) 是合法的关系表达式。
 
A.错误
 
B.正确
 
4. 预处理指令只能位于C源程序文件的首部。
 
A.错误
 
B.正确
 
5. 在c程序中，语句之间必须要用分号";"来分隔。
 
A.错误
 
B.正确
 
6. for循环是先执行循环体语句，后判断表达式。
 
A.错误
 
B.正确
 
7. 在C语言中char型数据在内存中的存储形式为ASCII码。
 
A.错误
 
B.正确
 
8. 声明语句可放在函数体中的任何位置。
 
A.错误
 
B.正确
 
9. 在C程序中，%是只能用于整数运算的运算符。
 
A.错误
 
B.正确
 
10. 设int a=12;则执行完语句a+=a-=a*a后，a的值为144。
 
A.错误
 
B.正确
 
11. 两个字符串所包含的字符个数相同时才能比较字符串大小。
 
A.错误
 
B.正确
 
12. %x是格式符的一种，它可以适用于任何一种类型的数据。
 
A.错误
 
B.正确
 
13. 若a和b类型相同，在执行了语句a=b后，b中的值将放入a中，b中的值不变。
 
A.错误
 
B.正确
 
14. 用typedef可以定义各种类型名，但不能用来定义变量。
 
A.错误
 
B.正确
 
15. C语言认为变量number和NuMbEr是相同的。
 
A.错误
 
B.正确

#include<stdio.h>
int main()
{
 
   int a[] = { 1,2,3,4,5};
   int *p;
   int i;

   for (i = 0; i < 5; i++)
   {
	   printf("%d\n",a[i]);
   }

   printf("-----------------\n");

   for (i = 0; i < 5; i++)
   {
	   printf("%d\n", *(a+i));
   }

   printf("-----------------\n");

   for (p=a; p < a+5; p++)//注意a++是不可的，因为a本来就代表了数组的首地址，a是不可改变的。
   {
	   printf("%d\n", *p);
   }

   printf("-----------------\n");

   for (p=a,i = 0; i < 5; i++)
   {
	   printf("%d\n",p[i]);//p[i]相当于*(a+1)
   }

   getchar();
   return 0;
}

 
 

  数组元素
 
 
 
 
  
 
   

    数组允许从外部来源（比如"人力资源"表）检索需要在薪资规则中使用的数据。
    要构建数组，请使用"数组定义"组件
    。
   
 
  
 
  
 
   

    • 要定义 FROM 子句，请在"字段映射和关键字"页面的"记录（表）名称"字段中标识包含所需数据
    的表。
   
 
   

    • 要构建 SELECT 子句，请在"字段映射和关键字"页面的"已检索的字段"组框中标识包含所需数据
    的表列（字段）。
   
 
   

    • 要构建 WHERE 子句，请定义数组关键字以及基于数组关键字的值从数据库表中提取数据行时要
    满足的条件。
   
 
  
 
  

   • 定义 SQL 语句之后，必须将数组中的数据库列值映射到"全球薪资"变量。
   这些变量储存列值并使之可用于"全球薪资"规则中。
  
 
  

   
 
  
 
  
 
   

    数组可用于访问不是由系统元素提供的数据库表或视图中的数据。数组不解析为值，但是会调用处
    理。
   
 
   
 
    
 
   
 
  
 
  

   命名数组元素
  
 
  

   访问"数组名称"页面（
   设置 HRMS，产品相关设置，全球薪资和缺勤管理，元素，支持元素，数组
   ）。
  
 
 
 
 

  
 
 
 
 
 
  

   因为数组是仅在处理期间存储结果的临时表，所以在处理之后不必再存储结果。系统取消选中"保存"和"如果为零则保存结果"复选框。
  
 
 
 
 
 
  

   此外，数组没有生效日期，所以此页面没有任何截止日期定义。要更改数组定义，请创建新数组和引用此数组的新生效日期元素。如果重命名数据库表或视图，则创建新数组。
  
 
 
 
 
 
  
 
 
 
 

  
 
 
 

  加载选项
 
 
 

  控制数据库中数组数据的刷新频率:
 
 
 
 
  

   基于员工的查询：选择创建基于受款人的数组。为
   每个受款人检索一次数据。处理此受款人时，数组存储将可用于下一受款人。
  
 
  
 
   

    一次加载（小表）：选择创建不基于受款人的数组。仅
    在处理中第一次引用数组时，检索一次数据。与另外两个"重新加载"选项相比，此选项可以显著改进性能，因为处理仅访问一次数据库就可以加载数据。如上所述，此选项只能用于比较小的表。包含此选项的所有数组的缓冲区只能存放 5000 行。如果表中的数据由处理本身更改（且需要在处理中反映这些更新），则"一次加载"不是一个理想选项。
   
 
  
 
  
 
   

    重新为每次解析加载：选择创建不基于受款人的数组。每次解析数组时才在数据库中检索数据。
   
 
   

    重新为每个段加载：选择创建不基于受款人的数组。不管在每个区段中可能解析数组多少次，对于要处理的每个区段都要从数据库中检索一次数据。
   
 
  
 
 
 
 
 
  
 
 
 
 

  
 
 
 

  处理选项
   选择其中一个值以确定系统何时及如何应用公式。有效值包括：
 
 
 
 
  
 
   
 
    

     按公式，适用所有行：系统选择数组所需的所有行，将第一个公式应
     用于所有行，将第二个公式应用于所有行，并继续应用所有公式。
    
 
    

     按行，适用所有公式：系统从数据库中选择一行数据，并将此页面中
     的每个公式应用于此行。然后，系统选择下一行并将每个公式应用于
     此行，并继续对所有行执行此操作。
    
 
    

     查询：系统从数据库中选择一行数据，将此页面上的每个公式应用于
     此行，选择下一行，并将每个公式应用于此行。解析为值 1 的第一个
     公式将停止此循环。所以，如果要搜索特定值的数据，则系统在找到
     此值时停止查询。
      对于使用查询处理的数组，如果选择"查询"值，但没有在"公式
     名称"字段中指定公式值，则系统使用数组返回的第一行数据。
    
 
   
 
   

    
 
   
 
   
 
    

     错误公式 如果没有找到任何行，则选择系统在错误处理期间要使用的"错误公式
     名称"。
    
 
    
 
     
 
    
 
    
 
     

      处理基于受款人的数组时，系统执行以下步骤：
     
 
     

      1. 在日历运行中第一次相遇时，数组调用数据库。
      符合 WHERE 标准（基于输入的关键字）的所有数据行都被提取到内存中。光标按员工 ID 升序
      排列，按员工记录号码升序排列，并按生效日期降序排列。
     
 
     

      2. 对于每个受款人，光标设置为访问相应的数据行（基于"字段映射和关键字"页面上字段使用的"受
      款人"和"生效日期"字段）。
      基于受款人的数组按基于支付期间结束日期的支付对齐。如果发生分段，而数组位于事件列表中
      ，或正在由要划分时段或区段的收入、扣减或缺勤元素使用，则必须按时段或区段结束日期对齐
      数组。
     
 
     

      3. 基于处理代码，数组处理公式应用于内存中存储的数据（对于上面设置的受款人光标）。
     
 
     

      4. 数据库字段解析为应用处理公式的最后一行数据。
      无论何时访问数组，都要重复执行步骤 2 到 4。仅当受款人已更改或要解析新时段或区段时，才执行
      步骤 1。
     
 
    
 
    

     
 
    
 
    
 
     

      处理不基于受款人的数组时，系统会执行下列步骤：
     
 
     

      1. 在日历运行中第一次相遇时，数组调用数据库。
      符合 WHERE 标准（基于输入的关键字）的所有数据行都提取到内存中，所以大多数生效日期逻
      辑都应符合处理公式逻辑。
     
 
     

      2. 如果表具有生效日期，则查询公式引用表示正确日期（区段、时段、期间）的系统元素。
      如果发生分段，而数组位于事件列表中，或正在由要划分时段或区段的收入、扣减或缺勤元素使
      用，则必须按时段或区段结束日期对齐数组。数组可以返回来自数据库的多个行。处理公式应用
      于行。
     
 
     

      3. 运行数组处理公式。
     
 
     

      4. 数据库字段解析为应用处理公式的最后一行数据。
      无论何时访问数组，都要重复执行步骤 2 到 4。仅当在"字段映射和关键字"页面上选择了"重新为每
      个解析加载"或"重新为每个段加载"值时，才执行步骤 1。
     
 
    
 
    

     
 
    
 
   
 
  
 
 
 
 
 

 
 
 一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0A1……AN-1）变换为（AN-M …… AN-1 A0 A1……AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
 
 
 输入格式：每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。
 
 
 输出格式：在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。
 
 输入样例： 
 
6 2
1 2 3 4 5 6
 
 输出样例： 
 
5 6 1 2 3 4
 
 

  
#include <iostream>
#include   <algorithm>
using namespace std;
int Reverse(int* a, int b, int e)
 {
      for(; b < e; b++, e--)
		  swap(a[e],a[b]);
	  return 0;
 }
int main()
{
	int n,m;
	cin>>n>>m;
	int *a=new int[n]; 
	for(int i=0;i<n;i++)
		cin>>a[i];
	m %= n;
	Reverse(a, 0, n-m-1);
	Reverse(a, n-m,n-1);
	Reverse(a, 0, n-1);
	for(int i=0;i<n-1;i++)
		cout<<a[i]<<" ";
	cout<<a[n-1]<<endl;
	return 0;
}
  
 下面深度剖析这个题目：
 
 
 

  
 
 
 
 
 
  
 
   
 
    
 第一章、左旋转字符串
 
   
 
  
 
  
 
 作者：July，yansha、caopengcs。
 时间：二零一一年四月十四日。
 
 
  
 
 
 
  
  
 题目描述：
 定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部，如把字符串abcdef左旋转2位得到字符串cdefab。
 请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。 
 
 
  
 思路一、暴力移位法
 
 
  
     初看此题，咱们最先想到的笨方法可能就是一位一位移动，故咱们写一个函数叫做 leftshiftone(char *s,int n) 完成左移动一位的功能
 
  
 
   
 void leftshiftone(char *s,int n) {    
     char t = s[0];    //保存第一个字符    
     for (int i = 1; i < n; ++i) {    
         s[i - 1] = s[i];    
     }    
     s[n - 1] = t;    
 }    
 
  
 
  如此，左移m位的话，可以如下实现：
  
 
  
 
 
  
 
   
 void leftshift(char *s,int n,int m) {    
     while (m--) {    
         leftshiftone(s, n);    
     }    
 }    
 
  
 
  
 
 
  
 思路二、指针翻转法
 
  
     咱们先来看个例子，如下：abc defghi，若要让abc移动至最后的过程可以是：abc defghi->def abcghi->def ghiabc
 
  
     如此，我们可定义俩指针，p1指向ch[0]，p2指向ch[m]；
 一下过程循环m次，交换p1和p2所指元素，然后p1++, p2++；。
 
  
 
 
  
第一步，交换abc 和def ，abc defghi->def abcghi
第二步，交换abc 和 ghi，def abcghi->def ghiabc
 
  
 
 
  
     整个过程，看起来，就是abc 一步一步 向后移动
 
 
  
abc defghi
def abcghi
def ghi abc  
 
    //最后的 复杂度是O（m+n）   
  
 
 
  
 图解如下：
 
  
 
 
  
     由上述例子九个元素的序列abcdefghi，您已经看到，m=3时，p2恰好指到了数组最后一个元素，于是，上述思路没有问题。但如果上面例子中i 的后面还有元素列?
 
  
     即，如果是要左旋十个元素的序列：abcdefghij，ok，下面，就举这个例子，对abcdefghij序列进行左旋转操作：
 
  
 如果abcdef ghij要变成defghij abc：
   abcdef ghij
 1. def abc ghij
 2. def ghi abc j      //接下来，j 步步前移
 3. def ghi ab jc
 4. def ghi a j bc
 5. def ghi j abc 
 
  
  下面，再针对上述过程，画个图清晰说明下，如下所示：
 
  
 
 
  
   ok，咱们来好好彻底总结一下此思路二：（就4点，请仔细阅读）：
 
  
 1、首先让p1=ch[0]，p2=ch[m]，即让p1，p2相隔m的距离；
 
  
 2、判断p2+m-1是否越界，如果没有越界转到3，否则转到4（abcdefgh这8个字母的字符串，以4左旋，那么初始时p2指向e，p2+4越界了，但事实上p2至p2+m-1是m个字符，可以再做一个交换）。
 
  
 3、不断交换*p1与*p2，然后p1++，p2++，循环m次，然后转到2。
 
  
 4、此时p2+m-1 已经越界，在此只需处理尾巴。过程如下：
 
  
    4.1 通过n-p2得到p2与尾部之间元素个数r，即我们要前移的元素个数。
 
  
    4.2 以下过程执行r次：
 
  
        ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；
 
  
     所以，之前最初的那个左旋转九个元素abcdefghi的思路在末尾会出现问题的（如果p2后面有元素就不能这么变，例如，如果是处理十个元素，abcdefghij 列?对的，就是这个意思），解决办法有两个：
 
  
 方法一（即如上述思路总结所述）：
 def ghi abc jk
 当p1指向a，p2指向j时，由于p2+m越界，那么此时p1，p2不要变
 这里p1之后（abcjk)就是尾巴，处理尾巴只需将j,k移到abc之前，得到最终序列，代码编写如下：
 
  
 
 
  
 
   
 //copyright@July、颜沙    
 //最终代码，July，updated again，2011.04.17。    
 #include <iostream>    
 #include <string>    
 using namespace std;    
     
 void rotate(string &str, int m)    
 {    
         
     if (str.length() == 0 || m <= 0)    
         return;    
         
     int n = str.length();    
         
     if (m % n <= 0)    
         return;    
         
     int p1 = 0, p2 = m;    
     int k = (n - m) - n % m;    
         
     // 交换p1，p2指向的元素，然后移动p1，p2    
     while (k --)     
     {    
         swap(str[p1], str[p2]);    
         p1++;    
         p2++;    
     }    
         
     // 重点，都在下述几行。    
     // 处理尾部，r为尾部左移次数    
     int r = n - p2;    
     while (r--)    
     {    
         int i = p2;    
         while (i > p1)    
         {    
             swap(str[i], str[i-1]);    
             i--;    
         }    
         p2++;    
         p1++;    
     }    
     //比如一个例子，abcdefghijk    
     //                    p1    p2    
     //当执行到这里时，defghi a b c j k    
     //p2+m出界 了，    
     //r=n-p2=2，所以以下过程，要执行循环俩次。    
         
     //第一次：j 步步前移，abcjk->abjck->ajbck->jabck    
     //然后，p1++，p2++，p1指a，p2指k。    
     //               p1    p2    
     //第二次：defghi j a b c k    
     //同理，此后，k步步前移，abck->abkc->akbc->kabc。    
 }    
     
 int main()       
 {       
     string ch="abcdefghijk";       
     rotate(ch,3);       
     cout<<ch<<endl;       
     return 0;          
 }      
 
  
 
  
 
 
  
 方法二：
 def ghi abc jk
 当p1指向a，p2指向j时，那么交换p1和p2，
 此时为:
 def ghi jbc ak
 
  
 p1++，p2++,p1指向b，p2指向k，继续上面步骤得:
 def ghi jkc ab
 
  
 p1++，p2不动,p1指向c，p2指向b，p1和p2之间（cab)也就是尾巴，
 那么处理尾巴（cab)需要循环左移一定次数（而后的具体操作步骤已在下述程序的注释中已详细给出）。
 
  
     根据方案二，不难写出下述代码（已测试正确）：
 
  
 
 
  
 
   
 #include <iostream>    
 #include <string>    
 using namespace std;    
     
 //颜沙，思路二之方案二，    
 //July、updated，2011.04.16。    
 void rotate(string &str, int m)    
 {    
     if (str.length() == 0 || m < 0)    
         return;    
     
     //初始化p1，p2    
     int p1 = 0, p2 = m;       
     int n = str.length();    
     
     // 处理m大于n    
     if (m % n == 0)    
         return;    
         
     // 循环直至p2到达字符串末尾    
     while(true)    
     {      
         swap(str[p1], str[p2]);    
         p1++;    
         if (p2 < n - 1)    
             p2++;    
         else    
             break;    
     }    
         
     // 处理尾部，r为尾部循环左移次数    
     int r = m - n % m;  // r = 1.    
     while (r--)  //外循环执行一次    
     {    
         int i = p1;    
         char temp = str[p1];    
         while (i < p2)  //内循环执行俩次    
         {    
             str[i] = str[i+1];    
             i++;    
         }       
         str[p2] = temp;    
     }    
     //举一个例子    
     //abcdefghijk    
     //当执行到这里的时候，defghiabcjk    
     //      p1    p2    
     //defghi a b c j k，a 与 j交换，jbcak，然后，p1++，p2++    
     //        p1    p2    
     //       j b c a k，b 与 k交换，jkcab，然后，p1++，p2不动，    
         
     //r = m - n % m= 3-11%3=1，即循环移位1次。    
     //          p1  p2    
     //       j k c a b    
     //p1所指元素c实现保存在temp里，    
     //然后执行此条语句：str[i] = str[i+1]; 即a跑到c的位置处，a_b    
     //i++，再次执行：str[i] = str[i+1]，ab_    
     //最后，保存好的c 填入，为abc，所以，最终序列为defghi jk abc。    
     //July、updated，2011.04.17晚，送走了她。    
 }    
     
 int main()    
 {    
     string ch="abcdefghijk";    
     rotate(ch,3);    
     cout<<ch<<endl;    
     return 0;       
 }    
 
  
 
  
 
 
  
 注意：上文中都是假设m<n，且如果鲁棒点的话令m=m%n，这样m允许大于n。另外，各位要记得处理指针为空的情况。      
 
  
 还可以看下这段代码：
 
  
 
   
 /*  
  * myinvert2.cpp  
  *  
  *  Created on: 2011-5-11  
  *      Author: BigPotato  
  */    
 #include<iostream>    
 #include<string>    
 #define positiveMod(m,n) ((m) % (n) + (n)) % (n)    
     
 /*  
  *左旋字符串str，m为负数时表示右旋abs（m）个字母  
  */    
 void rotate(std::string &str, int m) {    
     if (str.length() == 0)    
         return;    
     int n = str.length();    
     //处理大于str长度及m为负数的情况,positiveMod可以取得m为负数时对n取余得到正数    
     m = positiveMod(m,n);    
     if (m == 0)    
         return;    
     //    if (m % n <= 0)    
     //        return;    
     int p1 = 0, p2 = m;    
     int round;    
     //p2当前所指和之后的m-1个字母共m个字母，就可以和p2前面的m个字母交换。    
     while (p2 + m - 1 < n) {    
         round = m;    
         while (round--) {    
             std::swap(str[p1], str[p2]);    
             p1++;    
             p2++;    
         }    
     }    
     //剩下的不足m个字母逐个交换    
     int r = n - p2;    
     while (r--) {    
         int i = p2;    
         while (i > p1) {    
             std::swap(str[i], str[i - 1]);    
             i--;    
         }    
         p2++;    
         p1++;    
     }    
 }    
     
 //测试    
 int main(int argc, char **argv) {    
     //    std::cout << ((-15) % 7 + 7) % 7 << std::endl;    
     //    std::cout << (-15) % 7 << std::endl;    
     std::string ch = "abcdefg";    
     int len = ch.length();    
     for (int m = -2 * len; m <= len * 2; m++) {    
         //由于传给rotate的是string的引用，所以这里每次调用都用了一个新的字符串    
         std::string s = "abcdefg";    
         rotate(s, m);    
         std::cout << positiveMod(m,len) << ": " << s << std::endl;    
     }    
      
     return 0;    
 }   
 
  
 
  
 思路三、递归转换法
 
  
     本文最初发布时，网友留言bluesmic说：楼主，谢谢你提出的研讨主题，很有学术和实践价值。关于思路二，本人提一个建议：思路二的代码，如果用递归的思想去简化，无论代码还是逻辑都会更加简单明了。
 
  
     就是说，把一个规模为N的问题化解为规模为M(M<N)的问题。
     举例来说，设字符串总长度为L，左侧要旋转的部分长度为s1，那么当从左向右循环交换长度为s1的小段，直到最后，由于剩余的部分长度为s2(s2==L%s1)而不能直接交换。
 
  
     该问题可以递归转化成规模为s1+s2的，方向相反(从右向左)的同一个问题。随着递归的进行，左右反复回荡，直到某一次满足条件L%s1==0而交换结束。
 
  
      举例解释一下：
     设原始问题为：将“123abcdefg”左旋转为“abcdefg123”，即总长度为10，旋转部("123")长度为3的左旋转。按照思路二的运算，演变过程为“123abcdefg”->"abc123defg"->"abcdef123g"。这时，"123"无法和"g"作对调，该问题递归转化为：将“123g”右旋转为"g123"，即总长度为4，旋转部("g")长度为1的右旋转。
 
  
 updated：
 
  
 Ys：
 
  
 Bluesmic的思路没有问题，他的思路以前很少有人提出。思路是通过递归将问题规模变小。当字符串总长度为n，左侧要旋转的部分长度为m，那么当从左向右循环交换长度为m的小段直到剩余部分为m’(n % m)，此时m’ < m，已不能直接交换了。
 
  
 此后，我们换一个思路，把该问题递归转化成规模大小为m’ +m，方向相反的同一问题。随着递归的进行，直到满足结束条件n % m==0。
 
  
  
 
  
   举个具体事例说明，如下：
 
  
 1、对于字符串abc def ghi gk，
 
  
 将abc右移到def ghi gk后面，此时n = 11，m = 3，m’ = n % m = 2;
 
  
 abc def ghi gk -> def ghi abc gk
 
  
 2、问题变成gk左移到abc前面，此时n = m’ + m = 5，m = 2，m’ = n % m 1;
 
  
 abc gk -> a gk bc
 
  
 3、问题变成a右移到gk后面，此时n = m’ + m = 3，m = 1，m’ = n % m = 0;
 
  
 a gk bc-> gk a bc。 由于此刻，n % m = 0，满足结束条件，返回结果。
 
  
  
 
  
     即从左至右，后从右至左，再从左至右，如此反反复复，直到满足条件，返回退出。
 
  
     代码如下，已测试正确（有待优化）：
 
  
 
   
 //递归，    
 //感谢网友Bluesmic提供的思路    
     
 //copyright@ yansha 2011.04.19    
 //July，updated，2011.04.20.    
 #include <iostream>    
 using namespace std;    
     
 void rotate(string &str, int n, int m, int head, int tail, bool flag)    
 {    
     //n 待处理部分的字符串长度，m：待处理部分的旋转长度    
     //head：待处理部分的头指针，tail：待处理部分的尾指针    
     //flag = true进行左旋，flag = false进行右旋    
         
     // 返回条件    
     if (head == tail || m <= 0)    
         return;    
         
     if (flag == true)    
     {    
         int p1 = head;    
         int p2 = head + m;  //初始化p1，p2    
             
         //1、左旋：对于字符串abc def ghi gk，    
         //将abc右移到def ghi gk后面，此时n = 11，m = 3，m’ = n % m = 2;    
         //abc def ghi gk -> def ghi abc gk    
         //（相信，经过上文中那么多繁杂的叙述，此类的转换过程，你应该是了如指掌了。）    
             
         int k = (n - m) - n % m;   //p1，p2移动距离，向右移六步    
     
         /*---------------------  
         解释下上面的k = (n - m) - n % m的由来：  
         yansha：  
         以p2为移动的参照系：  
         n-m 是开始时p2到末尾的长度，n%m是尾巴长度  
         (n-m)-n%m就是p2移动的距离  
         比如 abc def efg hi  
         开始时p2->d,那么n-m 为def efg hi的长度8，  
         n%m 为尾巴hi的长度2，  
         因为我知道abc要移动到hi的前面，所以移动长度是  
         (n-m)-n%m = 8-2 = 6。  
         */    
             
         for (int i = 0; i < k; i++, p1++, p2++)    
             swap(str[p1], str[p2]);    
             
         rotate(str, n - k, n % m, p1, tail, false);  //flag标志变为false，结束左旋，下面，进入右旋    
     }    
     else    
     {    
         //2、右旋：问题变成gk左移到abc前面，此时n = m’ + m = 5，m = 2，m’ = n % m 1;    
         //abc gk -> a gk bc    
             
         int p1 = tail;    
         int p2 = tail - m;    
             
         // p1，p2移动距离，向左移俩步    
         int k = (n - m) - n % m;    
             
         for (int i = 0; i < k; i++, p1--, p2--)    
             swap(str[p1], str[p2]);    
             
         rotate(str, n - k, n % m, head, p1, true);  //再次进入上面的左旋部分，    
         //3、左旋：问题变成a右移到gk后面，此时n = m’ + m = 3，m = 1，m’ = n % m = 0;    
         //a gk bc-> gk a bc。 由于此刻，n % m = 0，满足结束条件，返回结果。    
     
     }    
 }    
     
 int main()    
 {    
     int i=3;    
     string str = "abcdefghijk";    
     int len = str.length();    
     rotate(str, len, i % len, 0, len - 1, true);    
     cout << str.c_str() << endl;   //转化成字符数组的形式输出    
     return 0;    
 }    
 
  
 
  
 
 
  
 非常感谢。
 
  
     稍后，由下文，您将看到，其实上述思路二的本质即是下文将要阐述的stl rotate算法，详情，请继续往下阅读。
 
  
  
 
  
 思路四、循环移位法
 
      下面，我将再具体深入阐述下此STL 里的rotate算法，由于stl里的rotate算法，用到了gcd的原理，下面，我将
  先介绍辗转相除法(又称欧几里得算法、gcd算法）的算法思路及原理。 
  
 
 
  
     gcd，即辗转相除法，又称欧几里得算法，是求最大公约数的算法，即求两个正整数之最大公因子的算法。此算法作为TAOCP第一个算法被阐述，足见此算法被重视的程度。
 
  
     gcd算法：给定俩个正整数m，n（m>=n），求它们的最大公约数。（注意，一般要求m>=n，若m<n，则要先交换m<->n。下文，会具体解释）。
 
  
     用数学定理表示即为：“定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)”。以下，是此算法的具体流程：
     1、[求余数]，令r=m%n，r为n除m所得余数（0<=r<n）；
     2、[余数为0?]，若r=0，算法结束，此刻，n即为所求答案，否则，继续，转到3；
     3、[重置]，置m<-n，n<-r，返回步骤1.
 
  
     此算法的证明，可参考计算机程序设计艺术第一卷：基本算法。证明，此处略。
 
  
     ok，下面，举一个例子，你可能看的更明朗点。
     比如，给定m=544，n=119，
       则余数r=m%n=544%119=68; 因r!=0，所以跳过上述步骤2，执行步骤3。；
       置m<-119，n<-68，=>r=m%n=119%68=51;
       置m<-68，n<-51，=>r=m%n=68%51=17；
       置m<-51，n<-17，=>r=m%n=51%17=0，算法结束，
 
  
     此时的n=17，即为m=544，n=119所求的俩个数的最大公约数。
 
  
     再解释下上述gcd(m，n)算法开头处的，要求m>=n 的原因：举这样一个例子，如m<n，即m=119，n=544的话，那么r=m%n=119%544=119,
     因为r!=0,所以执行上述步骤3，注意，看清楚了：m<-544，n<-119。看到了没，尽管刚开始给的m<n，但最终执行gcd算法时，还是会把m，n的值交换过来，以保证m>=n。
 
  
     ok，我想，现在，你已经彻底明白了此gcd算法，下面，咱们进入主题，stl里的rotate算法的具体实现。//待续。
 
  
     熟悉stl里的rotate算法的人知道，对长度为n的数组(ab)左移m位，可以用stl的rotate函数（stl针对三种不同的迭代器，提供了三个版本的rotate）。但在某些情况下，用stl的rotate效率极差。
 
  
     对数组循环移位，可以采用的方法有（也算是对上文思路一，和思路二的总结）：
 
  
 
   
      flyinghearts：
       ① 动态分配一个同样长度的数组，将数据复制到该数组并改变次序，再复制回原数组。（最最普通的方法）
       ② 利用ba=(br)^T(ar)^T=(arbr)^T，通过三次反转字符串。（即上述思路一，首先对序列前部分逆序，再对序列后部分逆序，再对整个序列全部逆序）
       ③ 分组交换（尽可能使数组的前面连续几个数为所要结果）：
       若a长度大于b，将ab分成a0a1b，交换a0和b，得ba1a0，只需再交换a1 和a0。
       若a长度小于b，将ab分成ab0b1，交换a和b0，得b0ab1，只需再交换a 和b0。
       通过不断将数组划分，和交换，直到不能再划分为止。分组过程与求最大公约数很相似。
       ④ 所有序号为 (j+i *m) % n (j 表示每个循环链起始位置，i 为计数变量，m表示左旋转位数，n表示字符串长度)，会构成一个循环链（共有gcd(n,m)个，gcd为n、m的最大公约数），每个循环链上的元素只要移动一个位置即可，最后整个过程总共交换了n次（每一次循环链，是交换n/gcd(n,m)次，总共gcd(n,m)个循环链。所以，总共交换n次）。
 
  
 
  
     stl的rotate的三种迭代器，即是，分别采用了后三种方法。
 
  
     在给出stl rotate的源码之前，先来看下我的朋友ys对上述第4种方法的评论：
     ys：这条思路个人认为绝妙，也正好说明了数学对算法的重要影响。
 
  
     通过前面思路的阐述，我们知道对于循环移位，最重要的是指针所指单元不能重复。例如要使abcd循环移位变成dabc(这里m=3,n=4)，经过以下一系列眼花缭乱的赋值过程就可以实现：
     ch[0]->temp, ch[3]->ch[0], ch[2]->ch[3], ch[1]->ch[2], temp->ch[1];  （*）
     字符串变化为：abcd->_bcd->dbc_->db_c->d_bc->dabc;
 是不是很神奇？其实这是有规律可循的。
 
  
     请先看下面的说明再回过头来看。
  对于左旋转字符串，我们知道每个单元都需要且只需要赋值一次，什么样的序列能保证每个单元都只赋值一次呢？
 
  
       1、对于正整数m、n互为质数的情况，通过以下过程得到序列的满足上面的要求：
  for i = 0: n-1
       k = i * m % n;
  end
 
  
     举个例子来说明一下，例如对于m=3,n=4的情况，
         1、我们得到的序列：即通过上述式子求出来的k序列，是0, 3, 2, 1。
         2、然后，你只要只需按这个顺序赋值一遍就达到左旋3的目的了：
     ch[0]->temp, ch[3]->ch[0], ch[2]->ch[3], ch[1]->ch[2], temp->ch[1];   （*） 
 
  
     ok，这是不是就是按上面（*）式子的顺序所依次赋值的序列阿?哈哈，很巧妙吧。当然，以上只是特例，作为一个循环链，相当于rotate算法的一次内循环。
 
  
      2、对于正整数m、n不是互为质数的情况（因为不可能所有的m，n都是互质整数对），那么我们把它分成一个个互不影响的循环链，正如flyinghearts所言，所有序号为 (j + i * m) % n（j为0到gcd(n, m)-1之间的某一整数，i = 0:n-1）会构成一个循环链，一共有gcd(n, m)个循环链，对每个循环链分别进行一次内循环就行了。
 
  
     综合上述两种情况，可简单编写代码如下：
 
  
 
 
  
 
   
 //④ 所有序号为 (j+i *m) % n (j 表示每个循环链起始位置，i 为计数变量，m表示左旋转位数，n表示字符串长度)，  
 //会构成一个循环链（共有gcd(n,m)个，gcd为n、m的最大公约数），  
   
 //每个循环链上的元素只要移动一个位置即可，最后整个过程总共交换了n次  
 //（每一次循环链，是交换n/gcd(n,m)次，共有gcd(n,m)个循环链，所以，总共交换n次）。  
   
 void rotate(string &str, int m)   
 {   
     int lenOfStr = str.length();   
     int numOfGroup = gcd(lenOfStr, m);   
     int elemInSub = lenOfStr / numOfGroup;    
       
     for(int j = 0; j < numOfGroup; j++)      
         //对应上面的文字描述，外循环次数j为循环链的个数，即gcd(n, m)个循环链  
     {   
         char tmp = str[j];   
   
         for (int i = 0; i < elemInSub - 1; i++)      
             //内循环次数i为，每个循环链上的元素个数，n/gcd(m,n)次  
             str[(j + i * m) % lenOfStr] = str[(j + (i + 1) * m) % lenOfStr];  
         str[(j + i * m) % lenOfStr] = tmp;   
     }   
 }  
 
  
 
  
 
  
 后来有网友针对上述的思路④，给出了下述的证明：
     1、首先，直观的看肯定是有循环链，关键是有几条以及每条有多长，根据(i+j *m) % n这个表达式可以推出一些东东，一个j对应一条循环链，现在要证明(i+j *m) % n有n/gcd(n,m)个不同的数。
     2、假设j和k对应的数字是相同的， 即(i+j*m)%n = (i+k*m)%n， 可以推出n|(j-k)*m，m=m’*gcd(n.m), n=n’*gcd(n,m), 可以推出n’|(j-k)*m’，而m’和n’互素，于是n’|(j-k)，即(n/gcd(n,m))|(j-k)，
     3、所以(i+j*m) % n有n/gcd(n,m)个不同的数。则总共有gcd(n，m)个循环链。符号“|”是整除的意思。
 以上的3点关于为什么一共有gcd(n, m)个循环链的证明，应该是来自qq3128739xx的，非常感谢这位朋友。
 
  
 由于上述stl rotate源码中，方案④ 的代码，较复杂，难以阅读，下面是对上述第④ 方案的简单改写：
 
  
 
   
 //对上述方案4的改写。    
 //④ 所有序号为 (i+t*k) % n (i为指定整数，t为任意整数)，....    
 //copyright@ hplonline && July 2011.04.18。    
 //July、sahala、yansha，updated，2011.06.02。    
 void my_rotate(char *begin, char *mid, char *end)    
 {       
     int n = end - begin;       
     int k = mid - begin;       
     int d = gcd(n, k);       
     int i, j;       
     for (i = 0; i < d; i ++)       
     {       
         int tmp = begin[i];       
         int last = i;       
             
         //i+k为i右移k的位置，%n是当i+k>n时从左重新开始。    
         for (j = (i + k) % n; j != i; j = (j + k) % n)    //多谢laocpp指正。       
         {       
             begin[last] = begin[j];           
             last = j;       
         }           
         begin[last] = tmp;       
     }       
 }     
 
  
 
  
 
 
      对上述程序的解释：关于第二个for循环中，j初始化为（i+k）%n，程序注释中已经说了，i+k为i右移k的位置，%n是当i+k>n时从左重新开始。为什么要这么做呢?很简单，n个数的数组不管循环左移多少位，用上述程序的方法一共需要交换n次。当i+k>=n时i+k表示的位置在数组中不存在了，所以又从左边开始的(i+k)%n是下一个交换的位置。
  
 
  
 
  
 
  
好比5个学生,，编号从0开始，即0 1 2 3 4，老师说报数，规则是从第一个学生开始，中间隔一个学生报数。报数的学生编号肯定是0 2 4 1 3。这里就相当于i为0，k为2，n为5；
然后老师又说，编号为0的学生出列，其他学生到在他前一个报数的学生位置上去，那么学生从0 1 2 3 4=》2 3 4 _ 1，最后老师说，编号0到剩余空位去，得到最终排位2 3 4 0 1。此时的结果，实际上就是相当于上述程序中左移k=2个位置了。而至于为什么让 编号为0 的学生 出列。实际是这句：int last = i; 因为要达到这样的效果0 1 2 3 4 => 2 3 4 0 1，那么2 3 4 必须要移到前面去。怎么样，明白了么?。
 
  
 关于本题，不少网友也给出了他们的意见，具体请参见此帖子微软100题，维护地址。 
 
  
 
 
 
  
 
 
  
 思路五、三步翻转法
 
  
 
 
  
     对于这个问题，咱们换一个角度，可以这么做：
 
  
 将一个字符串分成两部分，X和Y两个部分，在字符串上定义反转的操作X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么我们可以得到下面的结论：(X^TY^T)^T=YX。显然我们这就可以转化为字符串的反转的问题了。
 
  
 不是么?ok,就拿abcdef 这个例子来说，若要让def翻转到abc的前头，那么只要按下述3个步骤操作即可：
 1、首先分为俩部分，X:abc，Y:def；
 2、X->X^T，abc->cba， Y->Y^T，def->fed。
 3、(X^TY^T)^T=YX，cbafed->defabc，即整个翻转。
 
  
 我想，这下，你应该一目了然了。
 
  
     其次，在《编程珠玑》上也有这样一个类似的问题，它的解法同本思路一致，如下图所示：
 
  
 
   
 
  
 
  
 
 
  
 然后，代码可以这么写：
 
  
 
 
  
 
   
 //Copyright@ 小桥流水 && July    
 //c代码实现，已测试正确。    
 //http://www.smallbridge.co.cc/2011/03/13/100%E9%A2%98    
 //_21-%E5%B7%A6%E6%97%8B%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html    
 //July、updated，2011.04.17。    
 char * invert(char *start, char *end)    
 {       
     char tmp, *ptmp = start;        
     while (start != NULL && end != NULL && start < end)      
     {       
         tmp = *start;       
         *start = *end;          
         *end = tmp;         
         start ++;       
         end --;     
     }    
     return ptmp;    
 }    
   
 char *left(char *s, int pos)   //pos为要旋转的字符个数，或长度，下面主函数测试中，pos=3。    
 {    
     int len = strlen(s);    
     invert(s, s + (pos - 1));  //如上，X->X^T，即 abc->cba    
     invert(s + pos, s + (len - 1)); //如上，Y->Y^T，即 def->fed    
     invert(s, s + (len - 1));  //如上，整个翻转，(X^TY^T)^T=YX，即 cbafed->defabc。    
     return s;    
 }    
 
  
 
  
 
   
 《编程之美》中的题目要求只使用两个附加变量。王晓东编著的《算法设计与实验题解》中要求只用到O(1)的辅助空间。其它地方两本书的要求相同，都是O(n)的时间复杂度。两本书中的解法总结起来就是三种方法：（1）循环换位算法（2）三次反转算法（3）排列循环算法。这三种算法在王晓东的著作中都有实现代码。第一种算法是最原始的算法。第二种算法比较巧妙，即使用VU=reverse(reverse(U)reserve(V))，写成数学形式就是：
 
   
  。
 
   
 于是使用三次反转也可实现。第三种方法与数学有较大关系，以下着重解释第三种方法，借此复习一下数学。
 
   
 对于第三种方法，王晓东老师在著作中介绍了一条循环置换分解定理：对于给定数组A[0..N-1]向后循环换位N-K位运算，可分解为恰好gcd(K,N-K)个循环置换，且0,...,gcd(K,N-K)-1中的每个数恰属于一个循环置换。其中gcd(x,y)表示x和y的最大公因数。
 
   
 我们从头开始分析这个问题，对于数组A[0..n-1]，要将其向后循环移动k位元素。因为每个元素右移n位后又回到了原来的位置上，所以右移k位等于右移k mod n位。考虑每个元素右移k位后的最终位置，比如对于A[0]，右移k位后在k mod n位置上，原来在k mod n位置上的元素右移k位后到了2*k mod n的位置上，把如此因为A[0]的移动而受到连环影响必须移动的位置列出来，就是下面这样一个位置序列：0,k,2*k,...,(t-1)k。其中每一项都是在模n的意义下的位置。t*k mod n 的结果是0。t是使得t*k mod n的结果为0的最小正整数。
 
   
 这个位置序列实质上是模n加法群中由元素k生成的一个循环子群。由群论中的结论(该结论的证明见最后)知，循环子群(k)的周期为n / gcd(k,n)，元数为n / gcd(k,n)，其陪集个数为gcd(k,n)。换句话说，A[0..n-1]循环右移k位的结果是循环子群(k)以及它的所有陪集循环右移一位。例如，将A[0..5] = {1,2,3,4,5,6}循环右移4位，这里n = 6, k = 4, gcd(k, n) = 2。A[0]的最终位置是4,A[4]的最终位置是2,A[2]的最终位置是0，这样，位置0,4,2便是由k=4生成的循环群，周期为6 / gcd(4,6) = 6 / 2 = 3，这样的循环子群共有gcd(4,6) = 2个。
 
   
 第三种方法的完整代码如下：
 
   
 
 
   
 
    
 
     
 
      [cpp] 
      view plain
      copy 
      
 
      
 
     
 
    
 
    
 // 数组的循环移位  
 #include <cstdio>  
   
 int gcd(int m, int n) {  
     int r;  
     while(r = m % n) {  
         m = n; n = r;  
     }  
     return n;  
 }  
   
 void shiftArray(int A[], int n, int k) {  
     // 因为左移的代码比右移的代码好实现的多，而右移k位  
     // 等价于左移-k位，-k = n - k。以下代码是通过左移-k位来实现右移k位  
     k = n - (k % n);  
     for(int i = 0, cnt = gcd(n, k); i < cnt; i++) {  
         int t = A[i], p = i, j = (k+i) % n;  
         while(j != i) {  
             A[p] = A[j]; p = j; j = (k + p) % n;  
         }  
         A[p] = t;  
     }  
 }  
   
 void printArray(int A[], int n) {  
     for(int i = 0; i < n; i++) {  
         printf("%-3d", A[i]);  
         if((i+1)%10 == 0) printf("/n");  
     }  
 }  
 int main() {  
     int A[] = {1,2,3,4,5,6, 7};  
     shiftArray(A, 7, 4);  
     printArray(A, 7);  
     return 0;  
 }  
 
   
 
   
 
   
 上述所用到的那个群论结论的证明：
 
   
 结论：设G是一个循环群，其中一个生成元素为a，若r和n的最大公约数为d，则a^r的周期为n / d。
 
   
  
 
   
 在模n加法群中，1是一个生成元素，任意元素k=1*k，所以任意元素k生成的循环子群(k)的周期为n / gcd(k,n)。因为gcd(k,n)=gcd(k,n-k)，所以也可以写成n / gcd(k, n-k)。