## 題目詳情 有個長度為2n的數組{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，請考慮有無時間復雜度o(n)，空間復雜度0(1)的解法。 **題目來源**：此題是去年2013年UC的校招筆試題，看似簡單，按照題目所要排序后的字符串蠻力變化即可，但若要完美的達到題目所要求的時空復雜度，則需要我們花費不小的精力。OK，請看下文詳解，一步步優化。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#分析與解法)分析與解法 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#解法一蠻力變換)解法一、蠻力變換 題目要我們怎么變換，咱們就怎么變換。此題@陳利人也分析過，在此，引用他的思路進行說明。為了便于分析，我們取n=4，那么題目要求我們把 a1，a2，a3，a4，**b1，b2，b3，b4** 變成 a1，b1，a2，b2，a3，b3，a4，b4 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#11步步前移)1.1、步步前移 仔細觀察變換前后兩個序列的特點，我們可做如下一系列操作： 第①步、確定b1的位置，即讓b1跟它前面的a2，a3，a4交換： a1，b1，a2，a3，a4，**b2，b3，b4** 第②步、接著確定b2的位置，即讓b2跟它前面的a3，a4交換： a1，b1，a2，b2，a3，a4，**b3，b4** 第③步、b3跟它前面的a4交換位置： a1，b1，a2，b2，a3，b3，a4，b4 b4已在最后的位置，不需要再交換。如此，經過上述3個步驟后，得到我們最后想要的序列。但此方法的時間復雜度為O（N^2），我們得繼續尋找其它方法，看看有無辦法能達到題目所預期的O（N）的時間復雜度。 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#12中間交換)1.2、中間交換 當然，除了如上面所述的讓b1，b2，b3，b4步步前移跟它們各自前面的元素進行交換外，我們還可以每次讓序列中最中間的元素進行交換達到目的。還是用上面的例子，針對a1，a2，a3，a4，b1，b2，b3，b4 第①步：交換最中間的兩個元素a4，b1，序列變成（待交換的元素用粗體表示）： **a1，a2，a3**，b1，a4，**b2，b3，b4** 第②步，讓最中間的兩對元素各自交換： **a1，a2**，b1，a3，b2，a4，**b3，b4** 第③步，交換最中間的三對元素，序列變成： a1，b1，a2，b2，a3，b3，a4，b4 同樣，此法同解法1.1、步步前移一樣，時間復雜度依然為O（N^2），我們得下點力氣了。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#解法二完美洗牌算法)解法二、完美洗牌算法 玩過撲克牌的朋友都知道，在一局完了之后洗牌，洗牌人會習慣性的把整副牌大致分為兩半，兩手各拿一半對著對著交叉洗牌，如下圖所示： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.1.jpg) 如果這副牌用a1 a2 a3 a4 b1 b2 b3 b4表示（為簡化問題，假設這副牌只有8張牌），然后一分為二之后，左手上的牌可能是a1 a2 a3 a4，右手上的牌是b1 b2 b3 b4，那么在如上圖那樣的洗牌之后，得到的牌就可能是b1 a1 b2 a2 b3 a3 b4 a4。 技術來源于生活，2004年，microsoft的Peiyush Jain在他發表一篇名為：“A Simple In-Place Algorithm for In-Shuffle”的論文中提出了完美洗牌算法。 這個算法解決一個什么問題呢？跟本題有什么聯系呢？ Yeah，顧名思義，完美洗牌算法解決的就是一個完美洗牌問題。什么是完美洗牌問題呢？即給定一個數組a1,a2,a3,...an,b1,b2,b3..bn,最終把它置換成b1,a1,b2,a2,...bn,an。讀者可以看到，這個完美洗牌問題本質上與本題完全一致，只要在完美洗牌問題的基礎上對它最后的序列swap兩兩相鄰元素即可。 即： ~~~ a1,a2,a3,...an,b1,b2,b3..bn ~~~ 通過完美洗牌問題，得到： ~~~ b1,a1,b2,a2,b3,a3... bn,an ~~~ 再讓上面相鄰的元素兩兩swap，即可達到本題的要求： ~~~ a1,b1,a2,b2,a3,b3....,an,bn ~~~ 也就是說，如果我們能通過完美洗牌算法（時間復雜度O(N)，空間復雜度O(1)）解決了完美洗牌問題，也就間接解決了本題。 雖然網上已有不少文章對上篇論文或翻譯或做解釋說明，但對于初學者來說，理解難度實在太大，再者，若直接翻譯原文，根本無法看出這個算法怎么一步步得來的，故下文將從完美洗牌算法的最基本的原型開始說起，以讓讀者能對此算法一目了然。 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#21位置置換pefect_shuffle1算法)2.1、位置置換pefect_shuffle1算法 為方便討論，我們設定數組的下標從1開始，下標范圍是[1..2n]。 還是通過之前n=4的例子，來看下每個元素最終去了什么地方。 起始序列：a1 a2 a3 a4 b1 b2 b3 b4 數組下標：1 2 3 4 5 6 7 8 最終序列：b1 a1 b2 a2 b3 a3 b4 a4 從上面的例子我們能看到，前n個元素中， > 第1個元素a1到了原第2個元素a2的位置，即1->2； > > 第2個元素a2到了原第4個元素a4的位置，即2->4； > > 第3個元素a3到了原第6個元素b2的位置，即3->6； > > 第4個元素a4到了原第8個元素b4的位置，即4->8； 那么推廣到一般情況即是：前n個元素中，第i個元素去了 第（2 * i）的位置。 上面是針對前n個元素，那么針對后n個元素，可以看出： > 第5個元素b1到了原第1個元素a1的位置，即5->1； > > 第6個元素b2到了原第3個元素a3的位置，即6->3； > > 第7個元素b3到了原第5個元素b1的位置，即7->5； > > 第8個元素b4到了原第7個元素b3的位置，即8->7； 推廣到一般情況是，后n個元素，第i個元素去了第 (2 * (i - n) ) - 1 = 2 * i - (2 * n + 1) = (2 * i) % (2 * n + 1) 個位置。 再綜合到任意情況，任意的第i個元素，我們最終換到了 (2 * i) % (2 * n + 1)的位置。為何呢？因為： > 當0 < i < n時， 原式= (2i) % (2 * n + 1) = 2i； > > 當i > n時，原式(2 * i) % (2 * n + 1)保持不變。 因此，如果題目允許我們再用一個數組的話，我們直接把每個元素放到該放得位置就好了。也就產生了最簡單的方法pefect_shuffle1，參考代碼如下： ~~~ // 時間O(n)，空間O(n) 數組下標從1開始 void PefectShuffle1(int *a, int n) { int n2 = n * 2, i, b[N]; for (i = 1; i <= n2; ++i) { b[(i * 2) % (n2 + 1)] = a[i]; } for (i = 1; i <= n2; ++i) { a[i] = b[i]; } } ~~~ 但很明顯，它的時間復雜度雖然是O(n)，但其空間復雜度卻是O(n)，仍不符合本題所期待的時間O(n)，空間O(1)。我們繼續尋找更優的解法。 與此同時，我也提醒下讀者，根據上面變換的節奏，我們可以看出有兩個圈， > 一個是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1； > > 一個是3 -> 6 -> 3。 下文2.2.1、走圈算法cycle_leader將再次提到這兩個圈。 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#22完美洗牌算法perfect_shuffle2)2.2、完美洗牌算法perfect_shuffle2 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#221走圈算法cycle_leader)2.2.1、走圈算法cycle_leader 因為之前perfect_shuffle1算法未達到時間復雜度O（N）并且空間復雜度O（1）的要求，所以我們必須得再找一種新的方法，以期能完美的解決本節開頭提出的完美洗牌問題。 讓我們先來回顧一下2.1節位置置換perfect_shuffle1算法，還記得我之前提醒讀者的關于當n=4時，通過位置置換讓每一個元素到了最后的位置時，所形成的兩個圈么？我引用下2.1節的相關內容： 當n=4的情況： 起始序列：a1 a2 a3 a4 b1 b2 b3 b4 數組下標：1 2 3 4 5 6 7 8 最終序列：b1 a1 b2 a2 b3 a3 b4 a4 即通過置換，我們得到如下結論： “于此同時，我也提醒下讀者，根據上面變換的節奏，我們可以看出有兩個圈， > 一個是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1； > > 一個是3 -> 6 -> 3。” 這兩個圈可以表示為（1,2,4,8,7,5）和（3,6），且perfect_shuffle1算法也已經告訴了我們，不管你n是奇數還是偶數，每個位置的元素都將變為第（2*i） % （2n+1）個元素： 因此我們只要知道圈里最小位置編號的元素即圈的頭部，順著圈走一遍就可以達到目的，且因為圈與圈是不相交的，所以這樣下來，我們剛好走了O（N）步。 還是舉n=4的例子，且假定我們已經知道第一個圈和第二個圈的前提下，要讓1 2 3 4 5 6 7 8變換成5 1 6 2 7 3 8 4： 第一個圈：1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1 第二個圈：3 -> 6 -> 3： 原始數組：1 2 3 4 5 6 7 8 數組下標：1 2 3 4 5 6 7 8 走第一圈：5 1 3 2 7 6 8 4 走第二圈：5 1 6 2 7 3 8 4 上面沿著圈走的算法我們給它取名為cycle_leader，這部分代碼如下： ~~~ //數組下標從1開始，from是圈的頭部，mod是要取模的數 mod 應該為 2 * n + 1，時間復雜度O(圈長） void CycleLeader(int *a, int from, int mod) { int t,i; for (i = from * 2 % mod; i != from; i = i * 2 % mod) { t = a[i]; a[i] = a[from]; a[from] = t; } } ~~~ ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#222神級結論若2n3k---1則可確定圈的個數及各自頭部的起始位置)2.2.2、神級結論：若2*n=（3^k - 1），則可確定圈的個數及各自頭部的起始位置 下面我要引用此論文“A Simple In-Place Algorithm for In-Shuffle”的一個結論了，即 對于2*n = （3^k-1）這種長度的數組，恰好只有k個圈，且每個圈頭部的起始位置分別是1,3,9，...3^(k-1)。 論文原文部分為： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.2.jpg) 也就是說，利用上述這個結論，我們可以解決這種特殊長度2*n = （3^k-1）的數組問題，那么若給定的長度n是任意的咋辦呢？此時，我們可以采取分而治之算法的思想，把整個數組一分為二，即拆分成兩個部分： 讓一部分的長度滿足神級結論：若2*m = （3^k-1），則恰好k個圈，且每個圈頭部的起始位置分別是1,3,9，...3^(k-1)。其中m < n，m往神級結論所需的值上套； 剩下的n-m部分單獨計算； 當把n分解成m和n-m兩部分后，原始數組對應的下標如下（為了方便描述，我們依然只需要看數組下標就夠了）： 原始數組下標：1..m m+1.. n， n+1 .. n+m, n+m+1,..2*n 且為了能讓前部分的序列滿足神級結論2*m = （3^k-1），我們可以把中間那兩段長度為n-m和m的段交換位置，即相當于把m+1..n，n+1..n+m的段循環右移m次（為什么要這么做？因為如此操作后，數組的前部分的長度為2m，而根據神級結論：當2m=3^k-1時，可知這長度2m的部分恰好有k個圈）。 而如果讀者看過本系列第一章、左旋轉字符串的話，就應該意識到循環位移是有O（N）的算法的，其思想即是把前n-m個元素（m+1.. n）和后m個元素（n+1 .. n+m）先各自翻轉一下，再將整個段（m+1.. n， n+1 .. n+m）翻轉下。 這個翻轉的代碼如下： ~~~ //翻轉字符串時間復雜度O(to - from) void reverse(int *a, int from, int to) { int t; for (; from < to; ++from, --to) { t = a[from]; a[from] = a[to]; a[to] = t; } } //循環右移num位 時間復雜度O(n) void RightRotate(int *a, int num, int n) { reverse(a, 1, n - num); reverse(a, n - num + 1, n); reverse(a, 1, n); } ~~~ 翻轉后，得到的目標數組的下標為： ~~~ 目標數組下標：1..m n+1..n+m m+1 .. n n+m+1,..2*n ~~~ OK，理論講清楚了，再舉個例子便會更加一目了然。當給定n=7時，若要滿足神級結論2*n=3^k-1，k只能取2，繼而推得n‘=m=4。 ~~~ 原始數組：a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 b6 b7 ~~~ 既然m=4，即讓上述數組中有下劃線的兩個部分交換，得到： ~~~ 目標數組：a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 b5 b6 b7 ~~~ 繼而目標數組中的前半部分a1 a2 a3 a4 b1 b2 b3 b4部分可以用2.2.1、走圈算法cycle_leader搞定，于此我們最終求解的n長度變成了n’=3，即n的長度減小了4，單獨再解決后半部分a5 a6 a7 b5 b6 b7即可。 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#223完美洗牌算法perfect_shuffle3)2.2.3、完美洗牌算法perfect_shuffle3 從上文的分析過程中也就得出了我們的完美洗牌算法，其算法流程為： > 輸入數組　A[1..2 * n] > > step 1 找到 2 * m = 3^k - 1 使得 3^k <= 2 * n < 3^(k +1) > > step 2 把a[m + 1..n + m]那部分循環移m位 > > step 3 對每個i = 0,1,2..k - 1，3^i是個圈的頭部，做cycle_leader算法，數組長度為m，所以對2 * m + 1取模。 > > step 4 對數組的后面部分A[2 * m + 1.. 2 * n]繼續使用本算法, 這相當于n減小了m。 上述算法流程對應的論文原文為： 以上各個步驟對應的時間復雜度分析如下： > 因為循環不斷乘3的，所以時間復雜度O(logn) > > 循環移位O(n) > > 每個圈，每個元素只走了一次，一共2*m個元素，所以復雜度omega(m), 而m < n，所以 也在O(n)內。 T(n - m) > > 因此總的時間復雜度為 T(n) = T(n - m) + O(n) ，m = omega(n) ，解得：T(n) = O(n)。 此完美洗牌算法實現的參考代碼如下： ~~~ //copyright@caopengcs 8/24/2013 //時間O(n)，空間O(1) void PerfectShuffle2(int *a, int n) { int n2, m, i, k, t; for (; n > 1;) { // step 1 n2 = n * 2; for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3) ; m /= 2; // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1) // step 2 right_rotate(a + m, m, n); // step 3 for (i = 0, t = 1; i < k; ++i, t *= 3) { cycle_leader(a , t, m * 2 + 1); } //step 4 a += m * 2; n -= m; } // n = 1 t = a[1]; a[1] = a[2]; a[2] = t; } ~~~ ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#224perfect_shuffle2算法解決其變形問題)2.2.4、perfect_shuffle2算法解決其變形問題 啊哈！以上代碼即解決了完美洗牌問題，那么針對本章要解決的其變形問題呢？是的，如本章開頭所說，在完美洗牌問題的基礎上對它最后的序列swap兩兩相鄰元素即可，代碼如下： ~~~ //copyright@caopengcs 8/24/2013 //時間復雜度O(n)，空間復雜度O(1)，數組下標從1開始，調用perfect_shuffle3 void shuffle(int *a, int n) { int i, t, n2 = n * 2; PerfectShuffle2(a, n); for (i = 2; i <= n2; i += 2) { t = a[i - 1]; a[i - 1] = a[i]; a[i] = t; } } ~~~ 上述的這個“在完美洗牌問題的基礎上對它最后的序列swap兩兩相鄰元素”的操作（當然，你也可以讓原數組第一個和最后一個不變，中間的2 * (n - 1)項用原始的標準完美洗牌算法做），只是在完美洗牌問題時間復雜度O(N)空間復雜度O(1)的基礎上再增加O(N)的時間復雜度，故總的時間復雜度O(N)不變，且理所當然的保持了空間復雜度O(1)。至此，咱們的問題得到了圓滿解決！ ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#問題擴展)問題擴展 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#神級結論是如何來的)神級結論是如何來的？ 我們的問題得到了解決，但本章尚未完，即決定完美洗牌算法的神級結論：若2*n=（3^k - 1），則恰好只有k個圈，且每個圈頭部的起始位置分別是1,3,9，...3^(k-1)，是如何來的呢？ [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.3.jpg) 要證明這個結論的關鍵就是：這所有的圈合并起來必須包含從1到M之間的所有正數，一個都不能少。這個證明有點麻煩，因為證明過程中會涉及到群論等數論知識，但再遠的路一步步走也能到達。 首先，讓咱們明確以下相關的概念，定理，及定義（搞清楚了這些東西，咱們便證明了一大半）： > 概念1 mod表示對一個數取余數，比如3 mod 5 =3，5 mod 3 =2； > > 定義1 歐拉函數?(m) 表示為不超過m（即小于等于m）的數中，與m互素的正整數個數 > > 定義2 若?(m)=Ordm(a) 則稱a為m的原根，其中Ordm(a)定義為：a ^d （ mod m），其中d=0,1,2,3…，但取讓等式成立的最小的那個d。 結合上述定義1、定義2可知，2是3的原根，因為2^0 mod 3 = 1, 2^1 mod 3 = 2, 2^2 mod 3 = 1, 2^3 mod 3 = 2，{a^0 mod m，a^1 mod m，a^2}得到集合S={1,2}，包含了所有和3互質的數，也即d=?(2)=2，滿足原根定義。 而2不是7的原根，這是因為2^0 mod 7 = 1, 2^1 mod 7 = 2, 2^2 mod 7 = 4, 2^3 mod 7 = 1，2^4 mod 7 = 2，2^5 mod 7 = 4，2^6 mod 7 = 1，從而集合S={1,2,4}中始終只有1、2、4三種結果，而沒包含全部與7互質的數（3、6、5便不包括）,，即d=3，但?(7)=6，從而d != ?(7)，不滿足原根定義。 再者，如果說一個數a，是另外一個數m的原根，代表集合S = {a^0 mod m, a^1 mod m, a^2 mod m…… }，得到的集合包含了所有小于m并且與m互質的數，否則a便不是m的原根。而且集合S = {a^0 mod m, a^1 mod m, a^2 mod m…… }中可能會存在重復的余數，但當a與m互質的時候，得到的{a^0 mod m, a^1 mod m, a^2 mod m}集合中，保證了第一個數是a^0 mod m，故第一次發現重復的數時，這個重復的數一定是1，也就是說，出現余數循環一定是從開頭開始循環的。 > 定義3 對模指數，a對模m的原根定義為?[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.4.jpg),st:[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.5.jpg)中最小的正整數d 再比如，2是9的原根，因為[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.6.jpg)，為了讓[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.7.jpg)除以9的余數恒等于1，可知最小的正整數d=6，而?(m)=6，滿足原根的定義。 > 定理1 同余定理：兩個整數a，b，若它們除以正整數m所得的余數相等，則稱a，b對于模m同余，記作[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.8.jpg)，讀做a與b關于模m同余。 > > 定理2 當p為奇素數且a是[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.9.jpg)的原根時? a也是[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.10.jpg)的原根 > > 定理3 費馬小定理：如果a和m互質，那么a^?(m) mod m = 1 > > 定理4 若(a,m)=1 且a為m的原根，那么a是(Z/mZ)*的生成元。 取a = 2, m = 3。 我們知道2是3的原根，2是9的原根，我們定義S(k)表示上述的集合S，并且取x = 3^k（x表示為集合S中的數）。 所以： ~~~ S(1) = {1, 2} S(2) = {1, 2, 4, 8, 7, 5} ~~~ 我們沒改變圈元素的順序，由前面的結論S(k)恰好是一個圈里的元素，且認為從1開始循環的，也就是說從1開始的圈包含了所有與3^k互質的數。 那與3^k不互質的數怎么辦？如果0 < i < 3^k與 3^k不互質，那么i 與3^k的最大公約數一定是3^t的形式（只包含約數3)，并且 t < k。即gcd(i , 3^k) = 3^t，等式兩邊除以個3 ^ t，即得gcd( i/(3^t)，3^(k - t) ) = 1， i/(3^t) 都與3^(k - t) 互質了，并且i / (3^t) < 3^(k - t), 根據S(k)的定義，可見i/(3^t) 在集合S(k - t)中。 同理，任意S(k - t)中的數x，都滿足gcd(x , 3^k) = 1,于是gcd(3^k , x* 3^t) = 3 ^ t, 并且x_3^t < 3^k。可見S(k - t)中的數x_3^t 與 i形成了一一對應的關系。 也就是說S(k - t)里每個數x* 3^t形成的新集合包含了所有與3^k的最大公約數為3^t的數，它也是一個圈,原先圈的頭部是1，這個圈的頭部是3^t。 于是，對所有的小于 3^k的數，根據它和3^k的最大公約數，我們都把它分配到了一個圈里去了，且k個圈包含了所有的小于3^k的數。 下面，舉個例子，如caopengcs所說，當我們取“a = 2, m = 3時， 我們知道2是3的原根，2是9的原根，我們定義S(k)表示上述的集合S，并且x= 3^k。 所以S(1) = {1, 2} S(2) = {1, 2, 4, 8, 7, 5} 比如k = 3。 我們有： S(3) = {1, 2 ,4 , 8, 16, 5, 10, 20, 13, 26, 25, 23, 19, 11, 22, 17, 7, 14} 包含了小于27且與27互質的所有數，圈的首部為1，這是原根定義決定的。 那么與27最大公約數為3的數，我們用S(2)中的數乘以3得到。 S(2) * 3 = {3, 6, 12, 24, 21, 15}, 圈中元素的順序沒變化，圈的首部是3。 與27最大公約數為9的數，我們用S(1)中的數乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的順序沒變化，圈的首部是9。 因為每個小于27的數和27的最大公約數只有1, 3, 9這3種情況，又由于前面所證的一一對應的關系，所以S(2) * 3包含了所有小于27且與27的最大公約數為3的數，S(1) * 9 包含了所有小于27且和27的最大公約數為9的數。” 換言之，若定義為整數，假設/N定義為整數Z除以N后全部余數的集合，包括{0...N-1}等N個數，而（/N)*則定義為這Z/N中{0...N-1}這N個余數內與N互質的數集合。 則當n=13時，2n+1=27，即得/N =｛0,1,2,3,.....,26}，（/N)*相當于就是｛0,1,2,3,.....,26}中全部與27互素的數的集合； 而2^k(mod 27)可以把（/27)*取遍，故可得這些數分別在以下3個圈內： 取頭為1，（/27)*＝｛1,2,4,8,16,5,10,20,13,26,25,23,19,11,22,17,7,14｝，也就是說，與27互素且小于27的正整數集合為{1,2,4,8,16,5,10,20,13,26,25,23,19,11,22,17,7,14}，因此?(m) = ?(27)=18, 從而滿足[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.11.jpg)的最小d = 18，故得出2為27的原根； 取頭為3，就可以得到｛3,6,12,24,21,15｝，這就是以3為頭的環，這個圈的特點是所有的數都是3的倍數，且都不是9的倍數。為什么呢？因為2^k和27互素。 具體點則是：如果3×2^k除27的余數能夠被9整除，則有一個n使得3_2^k=9n(mod 27)，即3_2^k－9n能夠被27整除，從而3*2^k－9n＝27m，其中n，m為整數，這樣一來，式子約掉一個3，我們便能得到2^k＝9m＋3n，也就是說，2^k是3的倍數，這與2^k與27互素是矛盾的，所以，3×2^k除27的余數不可能被9整除。 此外，2^k除以27的余數可以是3的倍數以外的所有數，所以，2^k除以27的余數可以為1,2,4,5,7,8，當余數為1時，即存在一個k使得2^k-1=27m，m為整數。 式子兩邊同時乘以3得到：3_2^k-3=81m是27的倍數，從而3_2^k除以27的余數為3； 同理，當余數為2時，2^k - 2 = 27m，=> 3_2^k- 6 =81m，從而3_2^k除以27的余數為6； 當余數為4時，2^k - 4 = 37m，=> 3_2^k - 12 =81m，從而3_2^k除以27的余數為12； 同理，可以取到15，21，24。從而也就印證了上面的結論：取頭為3，就可以得到｛3,6,12,24,21,15｝。 取9為頭，這就很簡單了，這個圈就是｛9,18} 你會發現，小于27的所有自然數，要么在第一個圈里面，也就是那些和27互素的數；要么在第二個圈里面，也就是那些是3的倍數，但不是9的倍數的數；要么在第三個圈里面，也就是是9倍數的數，而之所以能夠這么做，就是因為2是27的本原根。證明完畢。 最后，咱們也再驗證下上述過程： 因為[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.12.jpg)，故： i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 由于n=13，2n+1 = 27，據此[](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.13.jpg)公式可知，上面第 i 位置的數將分別變成下述位置的： i = 2 4 6 8 10 12 14 16 18 20 22 24 26 1 3 5 7 9 11 13 15 17 19 21 23 25 0 根據i 和 i‘ 前后位置的變動，我們將得到3個圈： ~~~ 1->2->4->8->16->5->10->20->13->26->25->23->19->11->22->17->7->14->1； 3->6->12->24->21->15->3 9->18->9 ~~~ 沒錯，這3個圈的數字與咱們之前得到的3個圈一致吻合，驗證完畢。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#舉一反三)舉一反三 至此，本章開頭提出的問題解決了，完美洗牌算法的證明也證完了，是否可以止步了呢？OH，NO！讀者有無思考過下述問題： 1、既然完美洗牌問題是給定輸入：a1,a2,a3,……aN,b1,b2,b3,……bN，要求輸出：b1,a1,b2,a2,……bN,aN；那么有無考慮過它的逆問題：即給定b1,a1,b2,a2,……bN,aN,，要求輸出a1,a2,a3,……aN,b1,b2,b3,……bN ？ 2、完美洗牌問題是兩手洗牌，假設有三只手同時洗牌呢？那么問題將變成：輸入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN，要求輸出是c1,b1,a1,c2,b2,a2,……cN,bN,aN，這個時候，怎么處理？