### 問題描述 （來源于**《編程珠璣》第2版**的第2章第11頁問題B） 請將一個具有n個元素的一維向量向左旋轉i個位置。例如，假設n=8，i=3，那么向量abcdefgh旋轉之后得到向量defghabc。簡單編碼使用一個具有n個元素的中間向量分n步即可完成此作業。你可以僅使用幾十字節的微小內存，花費與n成比例的時間來旋轉該向量嗎？ ### 解決思路 ### 方案一： 將向量x中的前i個元素復制到一個臨時數組中，接著將余下的n-i個元素左移i個位置，然后再將前i個元素從臨時數組中復制回x中的后面位置。該方案使用了i個額外的位置，如i足夠大，過于浪費空間。 ~~~ #include <stdio.h> void Rotate(char *a, int length, int i) { char tmp[10]; int step = i % length; if (step == 0) { return; } int j = 0; for (j = 0; j < step; j++){ tmp[j] = a[j]; } tmp[step] = '\0'; for (j = step; j < length; j++){ a[j -step] = a[j]; } while((a[length - step + j] = tmp[j]) != '\0'){ j++; } } void main() { char a[9] = "abcdefgh"; Rotate(a,8,3); printf("%s",a); } ~~~ ### 方案二： 定義一個函數來將x向左旋轉一個位置，然后調用該函數i次。該方案需要將數組移到i將，過于浪費時間。 ### 方案三： 先將x[0]移臨時變量t中，然后將x[i]移到x[0]中，x[2i]移到x[i]中，依次類推，直到我們又回到從x[0]中提取元素，不過在這時我們要從t中提取元素，然后結束該過程。當i=3，n=12時，該階段將以下面的次序移到各個元素。  如果該過程不能移動所有的元素，那么我們再從x[1]開始移動，一直依次進行下去，直到移動了所有的元素時為止。 該方案過于精巧，像書中所說的一樣堪稱巧妙的雜技表演，非常容易出錯。 ### 方案四： 旋轉向量x實際上就是將向量ab的兩個部分交換為向量ba，這里a代表x的前i個元素。假設a比b短。將b分割成bl和br，使br的長度和a的長度一樣。交換a和br，將ablbr轉換成brbla。因為序列a已在它的最終位置了，所以我們可以集中精力交換b的兩個部分了。由于這個新問題和原先的問題是一樣的，所以我們以遞歸的方式進行解決。 該方案要求編碼細膩，還需要深思熟慮，以確保程序具有足夠的效率。 ### 方案五： [最佳] 將這個問題看作是把數組ab轉換成數組ba吧，但同時也假定我們具有在數組中轉置指定部分元素的函數。我們先從ab開始，轉置a得到arb，再轉置b得到arbr，然后再轉置整個arbr得到（arbr）r，實際上就是ba。 ~~~ reverse(0, i-1) /*cbadefgh*/ reverse(i, n-1) /*cbahgfed*/ reverse(0, n-1) /*defghabc*/ ~~~ 該轉置代碼在時間和空間上都很有效，并且是這么簡短和簡單，想出錯都很難。 書中還提供了將10個元素的數組向上旋轉5個位置的手搖法例子：先是掌心對著你自己，左手在右手上面，如圖所示  ### 代碼實現 ~~~ #include <stdio.h> void swap(int *p, int *q); void reverse(int *vector, int index_begin, int index_end); void revrot(int *vector, int len, int step); int main(int argc, char **argv){ int step = 3; int i = 0; int vector[1024] = {1,2,3,4,5,6,7,8}; revrot(vector, 8, step); printf("after revolve: "); for(i = 0; i < 8; i++){ printf("%d ", vector[i]); } printf("\n"); } void swap(int *p, int *q){ int temp; temp = *p; *p = *q; *q = temp; } void reverse(int *vector, int index_begin, int index_end){ while(index_begin < index_end){ swap(vector + index_begin, vector + index_end); index_begin++; index_end--; } } void revrot(int *vector, int len, int step){ reverse(vector, 0, step - 1); reverse(vector, step, len - 1); reverse(vector, 0, len - 1); } ~~~ **轉載請注明出處**：[http://blog.csdn.net/utimes/article/details/8762497](http://blog.csdn.net/utimes/article/details/8762497)