编程珠玑中的问题(1)——向量旋转

墨蓝 2022-09-18 07:51 149阅读 0赞

摘自《Programming Pearls》2rd 第2章  
  
问题：将一个具有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 <stdio.h>   
\# 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 cnt   
 void 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  
  
算法的实现如下：

![None.gif][] \#include  < stdio.h >   
![None.gif][]\#include  < stdlib.h >   
![None.gif][]  
![None.gif][]typedef unsigned  int  size\_t;  
![None.gif][]typedef  char  ELEMENT;  
![None.gif][]  
![None.gif][] void  Reverse(ELEMENT  \*  str,size\_t size);  
![None.gif][] void  Whirl( ELEMENT  \*  str, size\_t size,  int  cnt);  
![None.gif][] void  SwapElement(ELEMENT  \*  str, int  index1, int  index2);  
![None.gif][]  
![None.gif][] int  main ( int  argc, char  \*  argv\[\])  
![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ... \{  
![InBlock.gif][]  
![ExpandedSubBlockStart.gif][]![ContractedSubBlock.gif][]char target\[\]=...\{ 'a','b','c','d','e','f','g'\};  
![InBlock.gif][] Whirl(target,sizeof(target),atoi(argv\[1\]) );  
![InBlock.gif][]  
![InBlock.gif][]int index;  
![InBlock.gif][]  
![InBlock.gif][]for(index=0; index <sizeof(target);index\++)  
![InBlock.gif][] printf("%c",target\[index\]);  
![InBlock.gif][]  
![InBlock.gif][] printf("");  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][] void  SwapElement(ELEMENT  \*  str, int  index1, int  index2)  
![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ... \{  
![InBlock.gif][]char tmp=str\[index1\];  
![InBlock.gif][] str\[index1\]=str\[index2\];  
![InBlock.gif][] str\[index2\]=tmp;  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][]  
![None.gif][] void  Reverse(ELEMENT  \*  str,size\_t size)  
![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ... \{  
![InBlock.gif][]int index;  
![InBlock.gif][]  
![InBlock.gif][]for(index=0;index<size/2;index\++)  
![InBlock.gif][] SwapElement(str,index,size\-index\-1);  
![InBlock.gif][]  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][] void  Whirl( ELEMENT  \*  str, size\_t size,  int  cnt)  
![ExpandedBlockStart.gif][]![ContractedBlock.gif][] ... \{  
![InBlock.gif][]  
![InBlock.gif][] cnt%=size;  
![InBlock.gif][]  
![InBlock.gif][] Reverse(str,cnt);  
![InBlock.gif][]  
![InBlock.gif][] Reverse(str\+cnt,size\-cnt);  
![InBlock.gif][]  
![InBlock.gif][] Reverse(str,size);  
![ExpandedBlockEnd.gif][]\}   
![None.gif][]  
![None.gif][]  
![None.gif][]

从算法的实现也可以看出第二种算法的优越性，不仅有更少的代码量，而且逻辑更清晰。

[None.gif]: /images/20220828/6f4166ae31d94ecf84b365e0e8a9d7b3.png
[ExpandedBlockStart.gif]: http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedBlockStart.gif
[ContractedBlock.gif]: /images/20220828/445758ebc8fd42ecbe76f3ac0edc9f8a.png
[InBlock.gif]: /images/20220828/41159bfa0c26404490e8100215e50137.png
[ExpandedSubBlockStart.gif]: http://images.csdn.net/syntaxhighlighting/OutliningIndicators/ExpandedSubBlockStart.gif
[ContractedSubBlock.gif]: /images/20220828/216b1dad2aa1480a9059efefe63f34f1.png
[ExpandedBlockEnd.gif]: /images/20220828/e3b4413ec7644eb48294a40cb00a563b.png