程序员编程艺术第三十四~三十五章：格子取数问题，完美洗牌算法

第三十四~三十五章：格子取数，完美洗牌算法

作者：July、caopengcs、绿色夹克衫。致谢：西芹_new，陈利人，Peiyush Jain，白石，zinking。
时间：二零一三年八月二十三日。

题记

再过一个半月，即到2013年10月11日，便是本博客开通3周年之际，巧的是，那天刚好也是我的25岁生日。写博近3年，访问量趋近500万，无法确切知道帮助了多少人影响了多少人，但有些文章和一些系列是我比较喜欢的，如这三篇：从B树、B+树、B*树谈到R 树；教你如何迅速秒杀掉：99%的海量数据处理面试题；支持向量机通俗导论（理解SVM的三层境界）。

以及这2个系列：数据挖掘十大算法系列，程序员编程艺术。

当然，还有很多文章或系列自己也比较喜欢（如微软面试100题系列，经典算法研究系列等等），只是上面的文章或系列更具代表性。

但若论在上述文章或系列中，哪篇文章或系列对人找工作的帮助最大，则应该是：

程序员编程艺术http://blog.csdn.net/column/details/taopp.html，
秒杀99%的海量数据处理面试题http://blog.csdn.net/v_july_v/article/details/7382693，
微软面试100题系列http://blog.csdn.net/column/details/ms100.html，

其中，尤以编程艺术系列更佳。

OK，话休絮烦，本文讲解此文http://blog.csdn.net/v_july_v/article/details/7974418中的第75题、第79题：

第三十四章：格子取数问题；
第三十五章：完美洗牌算法的变形

若有任何问题，欢迎读者随时批评指正，感谢。

第三十四章、格子取数问题

题目详情：有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。

题目分析：此题是去年2013年搜狗的校招笔试题。初看到此题，因为要让两次走下来的路径总和最大，读者可能最初想到的思路可能是让每一次的路径都是最优的，即不顾全局，只看局部，让第一次和第二次的路径都是最优。

但问题马上就来了，虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图：

上图中，图一是原始图，那么我们有以下两种走法可供我们选择：

如果按照上面的局部贪优走法，那么第一次势必会如图二那样走，导致的结果是第二次要么取到2，要么取到3，
但若不按照上面的局部贪优走法，那么第一次可以如图三那样走，从而第二次走的时候能取到2 4 4，很显然，这种走法求得的最终SUM值更大；

为了便于读者理解，我把上面的走法在图二中标记出来，而把应该正确的走法在上图三中标示出来，如下图所示：

也就是说，上面图二中的走法太追求每一次最优，所以第一次最优，导致第二次将是很差；而图三第一次虽然不是最优，但保证了第二次不差，所以图三的结果优于图二。由此可知不要只顾局部而贪图一时最优，而丧失了全局最优。

解法一、直接搜索

局部贪优不行，我们可以考虑穷举，但最终将导致复杂度过高，所以咱们得另寻良策。

@西芹_new，针对此题，可以使用直接搜索法，一共搜（2n-2）步，每一步有四种走法，考虑不相交等条件可以剪去很多枝，代码如下：

//copyright@西芹_new 2013
#include "stdafx.h"  
#include <iostream>  
using namespace std;  #define N 5  
int map[5][5]={  {2,0,8,0,2},  {0,0,0,0,0},  {0,3,2,0,0},  {0,0,0,0,0},  {2,0,8,0,2}};  
int sumMax=0;  
int p1x=0;  
int p1y=0;  
int p2x=0;  
int p2y=0;  
int curMax=0;  void dfs( int index){  if( index == 2*N-2){  if( curMax>sumMax)  sumMax = curMax;  return;  }  if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))  {  if( p1x>= p2x && p1y >= p2y )  return;  }  //right right  if( p1x+1<N && p2x+1<N ){  p1x++;p2x++;  int sum = map[p1x][p1y]+map[p2x][p2y];  curMax += sum;  dfs(index+1);  curMax -= sum;  p1x--;p2x--;  }  //down down  if( p1y+1<N && p2y+1<N ){  p1y++;p2y++;  int sum = map[p1x][p1y]+map[p2x][p2y];  curMax += sum;  dfs(index+1);  curMax -= sum;  p1y--;p2y--;  }  //rd  if( p1x+1<N && p2y+1<N ) {  p1x++;p2y++;  int sum = map[p1x][p1y]+map[p2x][p2y];  curMax += sum;  dfs(index+1);  curMax -= sum;  p1x--;p2y--;  }  //dr  if( p1y+1<N && p2x+1<N ) {  p1y++;p2x++;  int sum = map[p1x][p1y]+map[p2x][p2y];  curMax += sum;  dfs(index+1);  curMax -= sum;  p1y--;p2x--;  }  
}  int _tmain(int argc, _TCHAR* argv[])  
{  curMax = map[0][0];  dfs(0);  cout <<sumMax-map[N-1][N-1]<<endl;  return 0;  
}

解法二、动态规划

上述解法一的搜索解法是的时间复杂度是指数型的，如果是只走一次的话，是经典的dp。

2.1、DP思路详解

故正如@绿色夹克衫所说：此题也可以用动态规划求解，主要思路就是同时DP 2次所走的状态。

1、先来分析一下这个问题，为了方便讨论，先对矩阵做一个编号，且以5*5的矩阵为例（给这个矩阵起个名字叫M1）：
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
从左上(0)走到右下(8)共需要走8步（2*5-2）。我们设所走的步数为s。因为限定了只能向右和向下走，因此无论如何走，经过8步后（s = 8)都将走到右下。而DP的状态也是依据所走的步数来记录的。
再来分析一下经过其他s步后所处的位置，根据上面的讨论，可以知道：

经过8步后，一定处于右下角(8)；
那么经过5步后(s = 5)，肯定会处于编号为5的位置；
3步后肯定处于编号为3的位置；
s = 4的时候，处于编号为4的位置，此时对于方格中，共有5（相当于n）个不同的位置，也是所有编号中最多的。

故推广来说，对于n*n的方格，总共需要走2n - 2步，且当s = n - 1时，编号为n个，也是编号数最多的。
如果用DP[s,i,j]来记录2次所走的状态获得的最大值，其中s表示走s步，i和j分别表示在s步后第1趟走的位置和第2趟走的位置。
2、为了方便描述，再对矩阵做一个编号（给这个矩阵起个名字叫M2）：
M2
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4

把之前定的M1矩阵也再贴下：
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
我们先看M1，在经过6步后，肯定处于M1中编号为6的位置。而M1中共有3个编号为6的，它们分别对应M2中的2 3 4。故对于M2来说，假设第1次经过6步走到了M2中的2，第2次经过6步走到了M2中的4，DP[s,i,j] 则对应 DP[6,2,4]。由于s = 2n - 2,0 <= i<= <= j <= n，所以这个DP共有O(n^3)个状态。
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
再来分析一下状态转移，以DP[6,2,3]为例(就是上面M1中加粗的部分)，可以到达DP[6,2,3]的状态包括DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]。

3、下面，我们就来看看这几个状态：DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]，用加粗表示位置DP[5,1,2]    DP[5,1,3]    DP[5,2,2]    DP[5,2,3] （加红表示要达到的状态DP[6,2,3]）
0 1 2 3 4    0 1 2 3 4    0 1 2 3 4    0 1 2 3 4
1 2 3 4 5    1 2 3 4 5    1 2 3 4 5    1 2 3 4 5
2 3 4 5 6    2 3 4 5 6    2 3 4 5 6    2 3 4 5 6
3 4 5 6 7    3 4 5 6 7    3 4 5 6 7    3 4 5 6 7
4 5 6 7 8    4 5 6 7 8    4 5 6 7 8    4 5 6 7 8
  因此：

DP[6,2,3] = Max(DP[5,1,2] ，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]) + 6,2和6,3格子中对应的数值（式一）

上面（式一）所示的这个递推看起来没有涉及：“如果两次经过同一个格子，那么该数只加一次的这个条件”，讨论这个条件需要换一个例子，以DP[6,2,2]为例：DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到达，但由于i = j，也就是2次走到同一个格子，那么数值只能加1次。
所以当i = j时，

DP[6,2,2] = Max(DP[5,1,1]，DP[5,1,2]，DP[5,2,2]) + 6,2格子中对应的数值（式二）

4、故，综合上述的（式一），（式二）最后的递推式就是
if(i != j)
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]
else
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]

其中W[s,i]表示经过s步后，处于i位置，位置i对应的方格中的数字。下一节我们将根据上述DP方程编码实现。

2.2、DP方法实现

为了便于实现，我们认为所有不能达到的状态的得分都是负无穷，参考代码如下：

//copyright@caopengcs 2013
const int N = 202;
const int inf = 1000000000;  //无穷大
int dp[N * 2][N][N];  
bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
int y1 = step - x1, y2 = step - x2;return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
}int getValue(int step, int x1,int x2,int n) {  //处理越界 不存在的位置 给负无穷的值return isValid(step, x1, x2, n)?dp[step][x1][x2]:(-inf);
}//状态表示dp[step][i][j] 并且i <= j, 第step步  两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 空间复杂度O(n^3) 
int getAnswer(int a[N][N],int n) {
int P = n * 2 - 2; //最终的步数
int i,j,step;//不能到达的位置 设置为负无穷大for (i = 0; i < n; ++i) {for (j = i; j < n; ++j) {dp[0][i][j] = -inf;}}dp[0][0][0] = a[0][0];for (step = 1; step <= P; ++step) {for (i = 0; i < n; ++i) {for (j = i; j < n; ++j) {dp[step][i][j] = -inf;if (!isValid(step, i, j, n)) { //非法位置continue;}//对于合法的位置进行dpif (i != j) {dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j - 1, n));dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,n));dp[step][i][j] += a[i][step - i] + a[j][step - j];  //不在同一个格子，加两个数}else {dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j,  n));dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,  n));dp[step][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次}}}}return dp[P][n - 1][n- 1];
}

复杂度分析：状态转移最多需要统计4个变量的情况，看做是O(1)的，共有O(n^3)个状态，所以总的时间复杂度是O(n^3)的，且dp数组开了N^3大小，故其空间复杂度亦为O(n^3)。

2.3、DP实现优化版

如上节末所说，2.2节实现的代码的复杂度空间复杂度是O(n^3)，事实上，空间上可以利用滚动数组优化，由于每一步的递推只跟上1步的情况有关，因此可以循环利用数组，将空间复杂度降为O(n^2)。
即我们在推算dp[step]的时候，只依靠它上一次的状态dp[step - 1]，所以dp数组的第一维，我们只开到2就可以了。即step为奇数时，我们用dp[1][i][j]表示状态，step为偶数我们用dp[0][i][j]表示状态，这样我们只需要O(n^2)的空间，这就是滚动数组的方法。滚动数组写起来并不复杂，只需要对上面的代码稍作修改即可，优化后的代码如下：

//copyright@caopengcs 8/24/2013
int dp[2][N][N];bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
int y1 = step - x1, y2 = step - x2;return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
}int getValue(int step, int x1,int x2,int n) {  //处理越界 不存在的位置 给负无穷的值return isValid(step, x1, x2, n)?dp[step % 2][x1][x2]:(-inf);
}//状态表示dp[step][i][j] 并且i <= j, 第step步  两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 使用滚动数组 空间复杂度O(n^2) 
int getAnswer(int a[N][N],int n) {
int P = n * 2 - 2; //最终的步数
int i,j,step,s;//不能到达的位置 设置为负无穷大for (i = 0; i < n; ++i) {for (j = i; j < n; ++j) {dp[0][i][j] = -inf;}}dp[0][0][0] = a[0][0];for (step = 1; step <= P; ++step) {for (i = 0; i < n; ++i) {for (j = i; j < n; ++j) {dp[step][i][j] = -inf;if (!isValid(step, i, j, n)) { //非法位置continue;}s = step % 2;  //状态下表标//对于合法的位置进行dpif (i != j) {dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j - 1, n));dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,n));dp[s][i][j] += a[i][step - i] + a[j][step - j];  //不在同一个格子，加两个数}else {dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j,  n));dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,  n));dp[s][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次}}}}return dp[P % 2][n - 1][n- 1];
}

本第34章分析完毕。

第三十五章、完美洗牌算法

题目详情：有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。

题目来源：此题是去年2013年UC的校招笔试题，看似简单，按照题目所要排序后的字符串蛮力变化即可，但若要完美的达到题目所要求的时空复杂度，则需要我们花费不小的精力。OK，请看下文详解，一步步优化。

解法一、蛮力变换

题目要我们怎么变换，咱们就怎么变换。此题@陈利人也分析过，在此，引用他的思路进行说明。为了便于分析，我们取n=4，那么题目要求我们把

a1，a2，a3，a4，b1，b2，b3，b4

变成

a1，b1，a2，b2，a3，b3，a4，b4

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）的时间复杂度。

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），我们得下点力气了。

解法二、完美洗牌算法

玩过扑克牌的朋友都知道，在一局完了之后洗牌，洗牌人会习惯性的把整副牌大致分为两半，两手各拿一半对着对着交叉洗牌，如下图所示：

如果这副牌用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)）解决了完美洗牌问题，也就间接解决了本题。

虽然网上已有不少文章对上篇论文或翻译或做解释说明，但对于初学者来说，理解难度实在太大，再者，若直接翻译原文，根本无法看出这个算法怎么一步步得来的，故下文将从完美洗牌算法的最基本的原型开始说起，以让读者能对此算法一目了然。

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 pefect_shuffle1(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.3.1、走圈算法cycle_leader将再次提到这两个圈。

2.2、分而治之perfect_shuffle2算法

熟悉分治法的朋友，包括若看了此文的读者肯定知道，当一个问题规模比较大时，则大而化小，分而治之。对于本题，假设n是偶数，我们试着把数组从中间拆分成两半(为了方便描述，只看数组下标就够了)：

原始数组的下标：1....2n，即（1 .. n/2， n/2+1..n）（n+1 .. n+n/2， n+n/2+1 .. 2n）

前半段（1 .. n/2， n/2+1..n）和后半段（n+1 .. n+n/2， n+n/2+1 .. 2n）的长度皆为n。

接下来，我们把前半段的后n/2个元素（n/2+1 .. n）和后半段的前n/2个元素（n+1..n+n/2）交换，得到

新的前n个元素A：（1..n/2 n+1.. n+n/2）

新的后n个元素B：（n/2+1 .. n n+n/2+1 .. 2n）

换言之，当n是偶数的时候，我们把原问题拆分成了A，B两个子问题，继而原n的求解转换成了n‘ = n/2 的求解。

可当n是奇数的时候呢？我们可以把前半段多出来的那个元素a先拿出来放到末尾，后面所有元素前移，于此，新数列的最后两个元素满足已满足要求，只需考虑前2*(n-1)个元素即可，继而转换成了n-1的问题。

针对上述n分别为偶数和奇数的情况，下面举n=4和n=5两个例子来说明下。

①n=4时，原始数组即为

a1 a2 a3 a4 b1 b2 b3 b4

按照之前n为偶数时的思路，把前半段的后2个元素a3 a4同后半段的前2个元素b1 b2交换，可得：

a1 a2 b1 b2 a3 a4 b3 b4

因此，我们只要用pefect_shuffle1算法继续求解A（a1 a2 b1 b2）和B（a3 a4 b3 b4）两个子问题就可以了。

②当n=5时，原始数组则为

a1 a2 a3 a4 a5 b1 b2 b3 b4 b5

还是按照之前n为奇数时的思路，先把a5先单独拎出来放在最后，然后所有剩下的元素全部前移，变为：

a1 a2 a3 a4 b1 b2 b3 b4 b5 a5

此时，最后的两个元素b5 a5已经是我们想要的结果，只要跟之前n=4的情况一样考虑即可。

参考代码如下：

//copyright@caopengcs 8/23/2013
//时间O(nlogn) 空间O(1) 数组下标从1开始  
void perfect_shuffle2(int *a,int n) {  
int t,i;  if (n == 1) {  t = a[1];  a[1] = a[2];  a[2] = t;  return;  }  int n2 = n * 2, n3 = n / 2;  if (n % 2 == 1) {  //奇数的处理  t = a[n];  for (i = n + 1; i <= n2; ++i) {  a[i - 1] = a[i];  }  a[n2] = t;  --n;  }  //到此n是偶数  for (i = n3 + 1; i <= n; ++i) {  t = a[i];  a[i] = a[i + n3];  a[i + n3] = t;  }  // [1.. n /2]  perfect_shuffle2(a, n3);  perfect_shuffle2(a + n, n3);  
}

分析下此算法的复杂度：每次，我们交换中间的n个元素，需要O(n)的时间，n是奇数的话，我们还需要O(n)的时间先把后两个元素调整好，但这不影响总体时间复杂度。

故事实上，当我们采用分治算法的时候，其时间复杂度的计算公式为： T(n) = 2*T(n / 2) + O(n) ，这个就是跟归并排序一样的复杂度式子，由《算法导论》中文第二版44页的主定理，可最终解得T(n) = O(nlogn)。至于空间，此算法在数组内部折腾的，所以是O(1)（在不考虑递归的栈的空间的前提下）。

2.3、完美洗牌算法perfect_shuffle3

2.3.1、走圈算法cycle_leader

因为之前无论是perfect_shuffle1，还是perfect_shuffle2，这两个算法的均未达到时间复杂度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. 1. 1. 一个是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1；
    2. 一个是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 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 cycle_leader(int *a,int from, int mod) {
int last = a[from],t,i;for (i = from * 2 % mod;i != from; i = i * 2 % mod) {t = a[i];a[i] = last;last = t;}a[from] = last;
}

2.3.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)。

论文原文部分为：

也就是说，利用上述这个结论，我们可以解决这种特殊长度2*n = （3^k-1）的数组问题，那么若给定的长度n是任意的咋办呢？此时，我们可以借鉴2.2节、分而治之算法的思想，把整个数组一分为二，即拆分成两个部分：

让一部分的长度满足神级结论：若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.2节、分而治之算法的思路，且更为了能让前部分的序列满足神级结论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 right_rotate(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.3.1、走圈算法cycle_leader搞定，于此我们最终求解的n长度变成了n’=3，即n的长度减小了4，单独再解决后半部分a5 a6 a7 b5 b6 b7即可。

2.3.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 perfect_shuffle3(int *a,int n) {
int n2, m, i, k,t;for (;n > 1;) {// step 1n2 = 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 2right_rotate(a + m, m, n);// step 3for (i = 0, t = 1; i < k; ++i, t *= 3) {cycle_leader(a , t, m * 2 + 1);}//step 4a += m * 2;n -= m;}// n = 1t = a[1];a[1] = a[2];a[2] = t;
}

2.3.4、perfect_shuffle3算法解决其变形问题

啊哈！以上代码即解决了完美洗牌问题，那么针对本章要解决的其变形问题呢？是的，如本章开头所说，在完美洗牌问题的基础上对它最后的序列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;perfect_shuffle3(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)。至此，咱们的问题得到了圆满解决！

2.3.5、神级结论是如何来的？

我们的问题得到了解决，但本章尚未完，即决定完美洗牌算法的神级结论：若2*n=（3^k - 1），则恰好只有k个圈，且每个圈头部的起始位置分别是1,3,9，...3^(k-1)，是如何来的呢？

要证明这个结论的关键就是：这所有的圈合并起来必须包含从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=ϕ(3)=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的原根定义为 ,st:中最小的正整数d

再比如，2是9的原根，因为，为了让除以9的余数恒等于1，可知最小的正整数d=6，而ϕ(m)=6，满足原根的定义。

定理1 同余定理：两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作，读做a与b关于模m同余。

定理2 当p为奇素数且a是的原根时⇒ a也是的原根
定理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, 从而满足的最小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的本原根。证明完毕。

最后，咱们也再验证下上述过程：

因为，故：

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，据此公式可知，上面第 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个圈：

1248165102013262523191122177141；
36122421153
9189

没错，这3个圈的数字与咱们之前得到的3个圈一致吻合，验证完毕。

2.3.6、完美洗牌问题的几个扩展

至此，本章开头提出的问题解决了，完美洗牌算法的证明也证完了，是否可以止步了呢？OH，NO！读者有无思考过下述问题：

既然完美洗牌问题是给定输入：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 ？
完美洗牌问题是两手洗牌，假设有三只手同时洗牌呢？那么问题将变成：输入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN，要求输出是c1,b1,a1,c2,b2,a2,……cN,bN,aN，这个时候，怎么处理？

以上两个完美洗牌问题的几个扩展请读者思考，具体解答请参看参考链接第15条。

本第35章完。

参考链接

huangxy10，http://blog.csdn.net/huangxy10/article/details/8071242；
@绿色夹克衫，http://www.51nod.com/answer/index.html#!answerId=598；
格子取数的蛮力穷举法：http://wenku.baidu.com/view/681c853b580216fc700afd9a.html；
@陈立人，http://mp.weixin.qq.com/mp/appmsg/show?__biz=MjM5ODIzNDQ3Mw==&appmsgid=10000141&itemidx=1&sign=4f1aa1a2269a1fac88be49c8cba21042；
caopengcs，http://blog.csdn.net/caopengcs/article/details/10196035；
完美洗牌算法的原始论文“A Simple In-Place Algorithm for In-Shuffle”，http://att.newsmth.net/att.php?p.1032.47005.1743.pdf；
原始根模：http://en.wikipedia.org/wiki/Primitive_root_modulo_n；
洗牌的学问：http://www.thecodeway.com/blog/?p=680；
关于完美洗牌算法：http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400；
关于完美洗牌算法中圈的说明：http://www.emis.de/journals/DMTCS/pdfpapers/dm050111.pdf；
关于神级结论的讨论：http://math.stackexchange.com/questions/477125/how-to-prove-algebraic-structure-of-the-perfect-shuffle（左边链接中的讨论中有错误，以在本文2.3.5节进行了相关修正）；
caopengcs关于神级结论的证明：http://blog.csdn.net/caopengcs/article/details/10429013；
同余的概念：http://zh.wikipedia.org/wiki/%E5%90%8C%E9%A4%98；
神奇的费马小定理：http://www.xieguofang.cn/Maths/Number_Theory/Fermat's_Little_Theorem_1.htm；
完美洗牌问题的几个扩展：http://blog.csdn.net/caopengcs/article/details/10521603；
原根与指数的介绍：http://wenku.baidu.com/view/bbb88ffc910ef12d2af9e738；
《数论概论》Joseph H. Silverman著，推荐理由：因写上文中的完美洗牌算法遇到了一堆数论定理受了刺激，故推荐此书；

后记

以上第35章可能是整个系列迄今为止我最满意的一篇，不仅仅是因为此章思路清晰，过渡自然，代码风格良好，更因为有了@曹鹏博士的加入，编程艺术如虎添翼，质量更上一层！

:编程艺术通过解决一个个实际的编程面试题，让广大初学者一步步学会分析问题解决问题优化问题的能力，且每个问题的讲解足够通俗，希望后续我(们)做得越来越好！July、二零一三年八月二十四日凌晨零点三十七分。

查看全文
如若内容造成侵权/违法违规/事实不符，请联系编程学习网邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！

[转]ASP,PHP,JSP,ASP.NET 比较
ASP,PHP,JSP,ASP.NET 这是当前比较流行的四种WEB网站编程语言，现在做网站大部分都是使用这几种语言中的其一。 ASP是基于WINDOWS平台的,简单易用,由于是运行在WINDOWS平台上,所以移植性不好,不能跨平台运行.但是国内现在大部分的网站都是使用它来开发的. PHP是当前兴起备受推…...
2024/4/28 15:06:01
AndroidStudio制作个人资料界面模块以及SQLite数据库的使用
前言大家好，我是 Vic，今天给大家带来AndroidStudio制作个人资料界面模块以及SQLite数据库的使用的概述，希望你们喜欢学习目标掌握SQLite数据库的使用，能够实现用数据库来保存用户的信息；学会运用好个人资料，以及个人资料的修改功能实现；个人资料包括用户名，昵称，性别，…...
2024/4/21 9:18:05
python- socket通信以16进制的数据进行传递与解析
struct.pack也就是将数据按照二进制的格式进行传输在网络编程中，利用 socket 进行通信时，常常会用到 struct 模块，在网络通信中，大多数传递的数据以二进制流（binary data）存在。传递字符串时无需过多担心，但传递 int，char 之类的基本数据时，就需要一种机制将某…...
2024/4/21 9:18:04
学习mac开发第九弹 10分钟学会数据库简单操作
学习mac开发第九弹 10分钟学会数据库简单操作简单介绍下我们将用什么数据库，能在10分钟就能会。它就是Realm,在之前我从来没用他开发。只是传说听过他的强大，居然在我简单的看了一眼文档居然就上手操作，我不在这里过分介绍他了，网上很多了，官网也有中文介绍。下面会总结我…...
2024/4/21 9:18:04
php技术资料01
[2007年11月01日 17:17] 通用数据查询及分页函数模块 [2007年10月24日 17:36] vml编辑器 [2007年10月24日 17:33] 首尾相连的滚动 [2007年10月24日 17:32] 表格排序2 [2007年10月24日 17:31] 表格排序 [2007年10月24日 17:29] javascript 验证表单五 [2007年10月24日 17:28] ja…...
2024/4/21 9:18:02
数据库基本知识学习
第一章基本知识数据和信息信息：关于现实世界事物存在方式和运动状态的反映。数据：通常指用符号记录下来的、可以识别的信息。数据处理和数据管理数据处理是指从某些已知的数据出发，推导加工出一些新的信息。数据管理是指数据的收集、整理、存储、维护、检索、传送等操作。这…...
2024/4/21 9:18:03
DBA学习计划
一、DBA技术　　1、作为一个DBA，你必须要精通SQL命令、各种数据库架构、数据库管理和维护、数据库调优，必要的时候，还需要为开发人员搭建一个健壮、结构良好、性能稳定的数据库环境。　　2、数据库是构建在操作系统之上的，你还需要精通系统技术。当然，完全不必要学习系统管…...
2024/5/3 16:32:11
第十四天流程结构（上）
流程结构——讲了一半嗯。。。。。。。。。。额。。。。。。。吼。。。。吼。。。。。哈。。。。。嘿。。。。。。大概就是这样讲完了。。PHP中可以用if(true):（冒号）echo what the fuck!!; else:（冒号）echo shit; endif;（分号）来代替花括号学会耐心，子曾经曰过：克己复…...
2024/5/3 13:15:54
计算机三级数据库：课本知识点总结以及备考方案建议
计算机三级（数据库）备考课本知识点欢迎阅读我的计算机三级总结第一章数据库应用系统开发方法第二章需求分析第三章数据库结构设计（自底向上）第四章数据库应用系统功能设计与实现第五章 UML与数据库应用系统第六章高级数据查询第七章数据库及数据库对象第八章数据库后…...
2024/4/20 18:14:03
【最火的微信开发开源框架】推荐给开发者应该学会的有关微信开发的十个开源项目
经常有做微信的朋友，问我能不能帮他实现公众号的这些功能啊、在微信方面能公开的我都免费共享给大家了，无论是微信网页方面的还是微信数据来源，我都在相关的平台或文章中公开给大家参考。至于怎么用怎么具体实现，这是一个大话题，昨天有位朋友说他买了本微信开发方面的书，…...
2024/4/20 18:14:02
数据库设计教程视频
该数据库设计教程为视频教程共分三部分：第一部分：数据库设计基础篇（黄志洪讲）主要讲述数据库的起源、数据库基础原理、关系型数据库、表、E-R图、数据的概念结构、逻辑结构的设计等内容该部分课程约400分钟时长。第二部分：数据库设计汇总及实战案例主要通过案例详细讲解数…...
2024/5/3 13:40:58
[开心学php100天]第二天:疯狂的数组
上期链接：开心学php100天第一天本期格言：为什么有的人学php总感觉有的知识点学的很好有的知识点却始终学不会,那是因为学的时候脸部肌肉太紧张，导致神经末梢坏死，所以瘸了。本期知识点：php数组数组是php最为标志性的利器功能。学好php数组基本上你就有了在php界混的初…...
2024/4/21 9:18:00
Lua 服务器Socket通信实例
local socket = require"socket" local host = "127.0.0.1" local port = "843" local sever = assert(socket.bind(host, port)) --绑定 sever:settimeout(nil) --不设置阻塞 local tab = {} table.insert(tab, sever) while 1 dolocal …...
2024/5/3 15:35:15
重新学习Mysql数据库3：Mysql存储引擎与数据存储原理
转自：https://draveness.me/mysql-innodb作为一名开发人员，在日常的工作中会难以避免地接触到数据库，无论是基于文件的 sqlite 还是工程上使用非常广泛的 MySQL、PostgreSQL，但是一直以来也没有对数据库有一个非常清晰并且成体系的认知，所以最近两个月的时间看了几本数据库…...
2024/4/21 9:17:57
一些显著性检测的数据库资料
今天来写一些，我在学习过程中用过的一些显著性或是目标检测方面的一些资料：１.一些常用的显著性数据库ａ. ASD数据库：这个数据库包含有1000张图（MSRA1000）这个数据库来自于A two-stage approach to saliency detection inimages 该数据库的说明以及一些算法（IT, MZ, G…...
2024/4/21 9:17:56
Oracle数据库学习笔记（oracle 11g持续更新...）
1、有关软件的安装在此不特意提出，请自行查阅资料 2、我们通过界面化软件操作数据库（命令行的形式） 3、以下代码的诸多效果展示，请自行补全理解1、新建数据库连接 2、创建表：userinfo create table userinfo(--姓名约束：唯一username VARCHAR(10) UNIQUE not NULL,--学…...
2024/4/21 9:17:55
深入浅出解析PHP并发IO问题以及Swoole使用
转载地址：https://www.php1.cn/detail/ShenRuQianChuJie_6e87d307.html目录多进程/多线程同步阻塞多进程/线程模型的流程多进程模型也有一些缺点。Reactor有4个核心的操作：协程是什么 PHP相关扩展PHP语言的优劣势 PHP的优点： PHP的缺点：PHP的Swoole扩展使用PHP+Swoole扩…...
2024/4/22 7:39:17
MySQL学习：使用数据库工具SQLite Expert
标题：MySQL学习：使用数据库工具SQLite Expert 都说不懂数据库的程序员不是合格的程序员，正在学Python的我怎么能不懂数据库，几经思考，终于选了数据库经典入门课程MySQL开始学习。可是刚一开始学我就遇到了难题~！ SQLite Expert? 这是什么？网上查了好久，才明白SQLite …...
2024/4/21 9:17:53
php资源下载
這些資源基本上都是一些免积分或只需要1個积分就能下载的資源,经过整理筛选最后分享给大家,希望大家喜欢:PHP手册(chm) http://download.csdn.net/detail/u011851645/6030287php手册最新版本 http://download.csdn.net/detail/fly367/5989061从零开始学PHP http://download.cs…...
2024/4/21 9:17:53
机器学习-UCI数据库
UCI数据库是加州大学欧文分校(University of CaliforniaIrvine)提出的用于机器学习的数据库数据库地址：http://archive.ics.uci.edu/ml/datasets.html...
2024/4/21 9:17:51

程序员编程艺术第三十四~三十五章：格子取数问题，完美洗牌算法

第三十四~三十五章：格子取数，完美洗牌算法

题记

第三十四章、格子取数问题

解法一、直接搜索

解法二、动态规划

2.1、DP思路详解

2.2、DP方法实现

2.3、DP实现优化版

第三十五章、完美洗牌算法

解法一、蛮力变换

1.1、步步前移

1.2、中间交换

解法二、完美洗牌算法

2.1、位置置换pefect_shuffle1算法

2.2、分而治之perfect_shuffle2算法

2.3、完美洗牌算法perfect_shuffle3

2.3.1、走圈算法cycle_leader

2.3.2、神级结论：若2*n=（3^k - 1），则可确定圈的个数及各自头部的起始位置

2.3.3、完美洗牌算法perfect_shuffle3

2.3.4、perfect_shuffle3算法解决其变形问题

2.3.5、神级结论是如何来的？

2.3.6、完美洗牌问题的几个扩展

参考链接

后记

相关文章

最新文章