问题：将一个具有n个元素的一维向量想左旋转k个位置。
例如，假设n=8,k=3,那么向量abcdefgh旋转后得到向量defghabc。
程序给定的限制是仅使用几十字节的微小内存，花费与n成比例的时间来完成旋转。
我的思考：
该问题看起来可以用一个典型的递归思路来解决。
例如题目中所给的例子，可以按如下步骤完成：
(1),将(abc)与原向量的最后三个元素进行一一置换，得到记过(fgh)de(abc)，即(fghde)abc。（这里的括号只是为了标记以提示重点，无其他意义）。
(2).现在可以观察到abc已移动到最终位置，下面只需对剩余的5个元素组成的向量(fghde)向左旋转3个位置，来变为(defgh)，如此，原始问题转化为一个规模更小的子问题。
(3).递归的终止条件？不难看出，当剩余的元素数量为k的2倍时，执行完(1)中的置换后，就已完成了旋转，因此不需要进行递归。此外，当最初的k%n的结果为0时，己不需要进行置换，也不需要进行递归——原向量与旋转后的向量相同。
然而，上面的思考是不全面的：即始终假设每次递归中剩余元素的数量n'至少是k的2倍。事实上一定会出现n'<2k的情况的，这种情况下需要进行一些变形，才能继续递归。方法如下
由于n'<2k，令k'=n‘-k<k , 再以n',k'为参数完成上述的步骤(1);之后，此时，n'中的最后k个元素已移动至最终位置，因此需要对剩余的n'-k'个元素进行递归，其递归参数为n,k-k' 。
上述算法的实现如下：
#include <stdlib.h>
typedef unsigned int size_t;
typedef char ELEMENT;
int
Min( int A,int B);void SwapElement(char * str, int index1 , int index2);
void Swap(char * str,size_t size, int cnt);
void Whirl (char * str, size_t size , int cnt);
int main (int argc
,char * argv[]){
ELEMENT target[]
={'a','b','c','d','e','f','g'};Whirl(target
,sizeof(target),atoi(argv[1]) );int index;
for(index=0; index < sizeof(target);index++)
printf("%c",target[index]);
printf(" ");
}
int
Min( int A,int B){
if(A<=B)
return A;
else
return B;
} // swap the array 's two elements: str[index1]<=>str[index2]
void SwapElement(ELEMENT * str,int index1,int index2)
{
char tmp=str[index1];
str[index1]=str[index2];
str[index2]=tmp;
} // swap the array's two part: str[0]~str[cnt-1] <=> str[size-cnt]~str[size-1]
void Swap(ELEMENT * str,size_t size, int cnt)
{
int index;
for(index=0;index<cnt;index++)
SwapElement(str,index,size-cnt+index);
}
//Whirl the array specified by str by number of cntvoid Whirl (ELEMENT * str, size_t size , int cnt)
{
cnt
%=size;if(cnt==0)
return;
if(cnt== size-cnt)
{
Swap(str,size,cnt);
return;
}
else if (cnt < size-cnt)
{
Swap(str,size,cnt);
Whirl(str,size-cnt,cnt);
}
else if(cnt > size-cnt)
{
int newcnt=size-cnt;
Swap(str,size,newcnt);
Whirl(str+newcnt,size-newcnt,cnt-newcnt);
}
}
写完程序后，参看了书中给出的思路，我想到的这种递归方法是其中的一种，作者给出的评论为：“根据这个递归的算法可以到得到一个非常优雅的程序，但是该程序要求编码细腻，还需要深思熟虑，以确保程序具有足够的效率。
此外，作者还给出了另外一个非常简洁而富有效率的算法，让我觉得不服不行，为啥我就做不到这么直接、清晰的思考问题呢？
该方法的思路如下：
将向量的元素视为数组元素，那么问题可以转化为将最初形式为ab数组，转化为形式为ba的数组；其中a是原数组的前k个元素，而b是剩余元素。
解决该问题， 只需三个步骤：
reverse(0,k-1) //将a部分进行180度的旋转，即将a中位置对称的元素互换，得到r(a)b
reverse(k,n) //将b部分进行180度的旋转 ，得到r(a)r(b)
reverse(0,n-1) //将整个数组进行180度的旋转，得到r(r(a)r(b)) =ba
算法的实现如下：
#include <stdio.h>#include <stdlib.h>typedef unsigned int size_t;typedef char ELEMENT;void Reverse(ELEMENT * str,size_t size);void Whirl( ELEMENT * str, size_t size, int cnt);void SwapElement(ELEMENT * str,int index1,int index2);int main (int argc,char * argv[])
{
char target[]={'a','b','c','d','e','f','g'};
Whirl(target,sizeof(target),atoi(argv[1]) ); int index; for(index=0; index < sizeof(target);index++) printf("%c",target[index]); printf(" ");
}void SwapElement(ELEMENT * str,int index1,int index2){ char tmp=str[index1]; str[index1]=str[index2]; str[index2]=tmp;}void Reverse(ELEMENT * str,size_t size){ int index; for(index=0;index<size/2;index++) SwapElement(str,index,size-index-1);}void Whirl( ELEMENT * str, size_t size, int cnt){ cnt%=size; Reverse(str,cnt); Reverse(str+cnt,size-cnt); Reverse(str,size);} 从算法的实现也可以看出第二种算法的优越性，不仅有更少的代码量，而且逻辑更清晰。