Kevin眼中的我，大概是个重视理论算法胜过编程实践的人，而我的算法和理论基础尚差的出奇（可能这就是知耻而后勇吧:D），可见我的编程实践又会多么的差了。Bugs更是对我整日沉浸于这些不着边际的“空中楼阁”颇有微词，甚至嗤之以鼻。今日若不是要把自己前段时间的豆腐渣粉饰一番，我依然不愿去考虑多线程的具体实现，或者说不是不愿，是不敢，总有一种临深履薄之感。

纵然如此，为了更好的完成工作，我还是拉来Kevin，劳他为我讲解一下多线程，可能是因为我从未仔细看过boost等C++开源库的原因吧，我对于结构封装本身并没有多少概念。说句实话，看到那些模板我就头大，心里想：本来一个简单的东西，为什么要搞的那么复杂呢？当然，我知道，这是因为我对其缺乏了解，在对一样东西没有完全理解就妄测其好坏是自卑的表现:D，所以也请Kevin原谅我的无知，顺便致谢;-)。

还是稍微提一下多线程的东西吧，因为这一次改动并不很大，因此只言片语难以面面俱到，也请各位TX不必较真儿。这儿只是说一下我是怎么偷懒把之前没有使用多线程的I/O部分修改成多线程I/O的，I/O的细节不再详述，而且这台机器上面因为没有VS，仅凭记忆，如果有什么差错，请帮我指出来了:-)。

在项目启动后的初始化中初始化I/O线程：

 1 void SomeApp::Init(void)
 2 {  
 3       // do some other things 
 4 
 5     CIOOperator::Init();  // InitializeCriticalSection for I/O queue(s)
 6 
 7     for( int i=0; i<nIOThreadsNum; ++i ) 
 8     { 
 9         CIOOperator *pOpObj = new CIOOperator; 
10         pOpObj->Create(); 
11         m_vecIOThreads.push_back(pOpObj); 
12     } 
13 
14       // do some other things 
15 }

在项目退出前结束I/O线程： 

 1 void SomeApp::Release(void) 
 2 {  
 3       // do some other things 
 4 
 5     vector<CIOOperator *>::iterator it = m_vecIOThreads.begin(); 
 6     for( ; i!=m_vecIOThreads.end(); ++it ) 
 7     { 
 8         it->End(); 
 9         delete (*it); 
10     } 
11     m_vecIOThreads.clear();
12 
13     CIOOperator::Release();  // DeleteCriticalSectionfor I/O queue(s)
14 
15       // do some other things 
16 } 

I/O线程函数：  

 1 void ThreadFunc( void *pArgument )
 2 {
 3       // do some other things, like exception handling 
 4 
 5     (CIOOperator *)pArgument->Run();  // operating I/O queue(s) until exit
 6 
 7       // do some other things 
 8 
 9     _endthreadex();
10 }

说多线程复杂，无外乎线程的退出策略、同步机制、调试、异常处理等等。多少还是需要一些知识（尤其是同步）和经验（尤其是调试）。

再回来说一下最近比较关注的算法吧，虽然为某些人所不齿，甚至公然批评我最近比较松懈，实在令我难堪的紧。我又没有消极怠工，难道编写代码是积极，学习算法就是消极吗？乡下来的，且不必理他。当然，多少还是需要注意一下分寸吧。

在受到上次解决烙饼排序问题的打击之后，我开始反思：自己思考和解决问题的角度怎么就那么简单和狭隘？细细想来，从本科毕业之后，几乎再没翻过算法的书，几乎再没做过算法的题，写代码只是为了糊口，只能糊口的代码自然只能以垃圾形容。意识粗糙，操作离谱，整个一下里巴人。

在一番深深的自责之后，痛定思痛，痛何如哉，才感觉自己关于算法的思维空间已经局限于if-else、do-while，连穷举、分治、贪心、回溯这些以前念书时天天挂在嘴边侃侃而谈的常用算法都没有概念了，遑论动态规划、最小二乘法、线性回归等复杂一些的（非）数值算法，关于数据结构的思维空间也已经局限于vector、list、map了，再也没有回忆过stack、tree、graph这些读死书、死读书得来的所谓知识。 

可悲啊，为什么拿到一个困难一点的问题，就只知道画图、编码，而不知道组织算法呢？甚至连这个问题到底有无多项式时间解都不去考虑。然而，一提谁都知道：算法复杂性——数据结构第0章就会提到的基础，真正分析起来，却是力不从心。

所以，接着扫扫盲吧，实在没有必要去搞很多艰深的东西，本来想接下来就写NP难题，可是近来工作上的事情确实有些多，之前一篇已经是被Alex（这家伙却至今未开张……）“催出来”的了。

手头只有MIT英文版的《Introduction to Algorithms》ed.2，于是就从网上找了中文电子版，居然是上个世纪94年南京大学译的第一版。看算法的话，多半是以这本书和Wikipedia为主了。

PS: 另外做的一点事情，似乎和词法分析、异常处理等多少有些关联，内容相当琐碎，此刻不再赘述。

对了，和工作、学习并不那么相干的事情就是，今天和几个同事出去钓了几个小时鱼，收获嘛，保密:D。

近期考虑的关键词：无缝世界 网游安全 算法导论 兄弟激情

这篇文章的术语实在是太多了，所以我在文中加入了少量注释，一律以粗斜体注明。

本文的不足之处将随时修正，MIT的《Introduction to Algorithms》第15章是专门讲动态规划的。

_____________________________________________________________

动态规划

在数学与计算机科学领域，动态规划用于解决那些可分解为重复子问题（overlapping subproblems，想想递归求阶乘吧）并具有最优子结构（optimal substructure，想想最短路径算法）（如下所述）的问题，动态规划比通常算法花费更少时间。

上世纪40年代，Richard Bellman最早使用动态规划这一概念表述通过遍历寻找最优决策解问题的求解过程。1953年，Richard Bellman将动态规划赋予现代意义，该领域被IEEE纳入系统分析和工程中。为纪念Bellman的贡献，动态规划的核心方程被命名为贝尔曼方程，该方程以递归形式重申了一个优化问题。

在“动态规划”（dynamic programming）一词中，programming与“计算机编程”（computer programming）中的programming并无关联，而是来自“数学规划”（mathematical programming），也称优化。因此，规划是指对生成活动的优化策略。举个例子，编制一场展览的日程可称为规划。 在此意义上，规划意味着找到一个可行的活动计划。

• 概述

图1 使用最优子结构寻找最短路径：直线表示边，波状线表示两顶点间的最短路径（路径中其他节点未显示）；粗线表示从起点到终点的最短路径。

不难看出，start到goal的最短路径由start的相邻节点到goal的最短路径及start到其相邻节点的成本决定。

最优子结构即可用来寻找整个问题最优解的子问题的最优解。举例来说，寻找图上某顶点到终点的最短路径，可先计算该顶点所有相邻顶点至终点的最短路径，然后以此来选择最佳整体路径，如图1所示。

一般而言，最优子结构通过如下三个步骤解决问题：

a) 将问题分解成较小的子问题；

b) 通过递归使用这三个步骤求出子问题的最优解；

c) 使用这些最优解构造初始问题的最优解。

子问题的求解是通过不断划分为更小的子问题实现的，直至我们可以在常数时间内求解。

图2 Fibonacci序列的子问题示意图：使用有向无环图（DAG, directed acyclic graph）而非树表示重复子问题的分解。

为什么是DAG而不是树呢？答案就是，如果是树的话，会有很多重复计算，下面有相关的解释。

一个问题可划分为重复子问题是指通过相同的子问题可以解决不同的较大问题。例如，在Fibonacci序列中，F3 = F1 + F2和F4 = F2 + F3都包含计算F2。由于计算F5需要计算F3和F4，一个比较笨的计算F5的方法可能会重复计算F2两次甚至两次以上。这一点对所有重复子问题都适用：愚蠢的做法可能会为重复计算已经解决的最优子问题的解而浪费时间。

为避免重复计算，可将已经得到的子问题的解保存起来，当我们要解决相同的子问题时，重用即可。该方法即所谓的缓存（memoization，而不是存储memorization，虽然这个词亦适合，姑且这么叫吧，这个单词太难翻译了，简直就是可意会不可言传，其意义是没计算过则计算，计算过则保存）。当我们确信将不会再需要某一解时，可以将其抛弃，以节省空间。在某些情况下，我们甚至可以提前计算出那些将来会用到的子问题的解。

总括而言，动态规划利用：

1) 重复子问题

2) 最优子结构

3) 缓存

动态规划通常采用以下两种方式中的一种两个办法：

自顶向下：将问题划分为若干子问题，求解这些子问题并保存结果以免重复计算。该方法将递归和缓存结合在一起。

自下而上：先行求解所有可能用到的子问题，然后用其构造更大问题的解。该方法在节省堆栈空间和减少函数调用数量上略有优势，但有时想找出给定问题的所有子问题并不那么直观。

为了提高按名传递（call-by-name，这一机制与按需传递call-by-need相关，复习一下参数传递的各种规则吧，简单说一下，按名传递允许改变实参值）的效率，一些编程语言将函数的返回值“自动”缓存在函数的特定参数集合中。一些语言将这一特性尽可能简化（如Scheme、Common Lisp和Perl），也有一些语言需要进行特殊扩展（如C++，C++中使用的是按值传递和按引用传递，因此C++中本无自动缓存机制，需自行实现，具体实现的一个例子是Automated Memoization in C++）。无论如何，只有指称透明（referentially transparent，指称透明是指在程序中使用表达式、函数本身或以其值替换对程序结果没有任何影响）函数才具有这一特性。

• 例子

1. Fibonacci序列

寻找Fibonacci序列中第n个数，基于其数学定义的直接实现：

   function fib(n)
       if n = 0
           return 0
       else if n = 1
           return 1
       return fib(n-1) + fib(n-2)

如果我们调用fib(5)，将产生一棵对于同一值重复计算多次的调用树：

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特别是，fib(2)计算了3次。在更大规模的例子中，还有更多fib的值被重复计算，将消耗指数级时间。

现在，假设我们有一个简单的映射（map）对象m，为每一个计算过的fib及其返回值建立映射，修改上面的函数fib，使用并不断更新m。新的函数将只需O(n)的时间，而非指数时间：

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if map m does not contain key n
           m[n] := fib(n-1) + fib(n-2)
       return m[n]

这一保存已计算出的数值的技术即被称为缓存，这儿使用的是自顶向下的方法：先将问题划分为若干子问题，然后计算和存储值。

在自下而上的方法中，我们先计算较小的fib，然后基于其计算更大的fib。这种方法也只花费线性（O(n)）时间，因为它包含一个n-1次的循环。然而，这一方法只需要常数（O(1)）的空间，相反，自顶向下的方法则需要O(n)的空间来储存映射关系。

   function fib(n)
       var previousFib := 0, currentFib := 1
       if n = 0
           return 0
       else if n = 1
           return 1
       repeat n-1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

在这两个例子，我们都只计算fib(2)一次，然后用它来计算fib(3)和fib(4)，而不是每次都重新计算。

2. 一种平衡的0-1矩阵

考虑n*n矩阵的赋值问题：只能赋0和1，n为偶数，使每一行和列均含n/2个0及n/2个1。例如，当n=4时，两种可能的方案是：

+ - - - - +             + - - - - +
| 0 1 0 1 |             | 0 0 1 1 |
| 1 0 1 0 |             | 0 0 1 1 |
| 0 1 0 1 |             | 1 1 0 0 |
| 1 0 1 0 |             | 1 1 0 0 |
+ - - - - +             + - - - - +

问：对于给定n，共有多少种不同的赋值方案。

至少有三种可能的算法来解决这一问题：穷举法（brute force）、回溯法（backtracking）及动态规划（dynamic programming）。穷举法列举所有赋值方案，并逐一找出满足平衡条件的方案。由于共有C(n, n/2)^n种方案（在一行中，含n/2个0及n/2个1的组合数为C(n,n/2)，相当于从n个位置中选取n/2个位置置0，剩下的自然是1），当n=6时，穷举法就已经几乎不可行了。回溯法先将矩阵中部分元素置为0或1，然后检查每一行和列中未被赋值的元素并赋值，使其满足每一行和列中0和1的数量均为n/2。回溯法比穷举法更加巧妙一些，但仍需遍历所有解才能确定解的数目，可以看到，当n=8时，该题解的数目已经高达116963796250。动态规划则无需遍历所有解便可确定解的数目（意思是划分子问题后，可有效避免若干子问题的重复计算）。

通过动态规划求解该问题出乎意料的简单。考虑每一行恰含n/2个0和n/2个1的k*n(1<=k<=n)的子矩阵，函数f根据每一行的可能的赋值映射为一个向量，每个向量由n个整数对构成。向量每一列对应的一个整数对中的两个整数分别表示该列上该行以下已经放置的0和1的数量。该问题即转化为寻找f((n/2,n/2),(n/2,n/2),...,(n/2,n/2))（具有n个参数或者说是一个含n个元素的向量）的值。其子问题的构造过程如下：

1) 最上面一行（第k行）具有C(n, n/2)种赋值；

2) 根据最上面一行中每一列的赋值情况（为0或1），将其对应整数对中相应的元素值减1；

3) 如果任一整数对中的任一元素为负，则该赋值非法，不能成为正确解；

4) 否则，完成对k*n的子矩阵中最上面一行的赋值，取k=k-1，计算剩余的(k-1)*n的子矩阵的赋值；

5) 基本情况是一个1*n的细小的子问题，此时，该子问题的解的数量为0或1，取决于其向量是否是n/2个(0, 1)和n/2个(1, 0)的排列。

例如，在上面给出的两种方案中，向量序列为：

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0       0       1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

动态规划在此的意义在于避免了相同f的重复计算，更进一步的，上面着色的两个f，虽然对应向量不同，但f的值是相同的，想想为什么吧:D。

该问题解的数量（序列a058527在OEIS）是1, 2, 90, 297200, 116963796250, 6736218287430460752, ...

下面的外部链接中包含回溯法的Perl源代码实现，以及动态规划法的MAPLE和C语言的实现。

3. 棋盘

考虑n*n的棋盘及成本函数C(i,j)，该函数返回方格(i,j)相关的成本。以5*5的棋盘为例：

5 | 6 7 4 7 8
4 | 7 6 1 1 4
3 | 3 5 7 8 2
2 | 2 6 7 0 2
1 | 7 3 5 6 1
- + - - - - -
  | 1 2 3 4 5

可以看到：C(1,3)=5

从棋盘的任一方格的第一阶（即行）开始，寻找到达最后一阶的最短路径（使所有经过的方格的成本之和最小），假定只允许向左对角、右对角或垂直移动一格。

5 |
4 |
3 |
2 |   x x x
1 |     o
- + - - - - -
  | 1 2 3 4 5

该问题展示了最优子结构。即整个问题的全局解依赖于子问题的解。定义函数q(i,j)，令：q(i,j)表示到达方格(i,j)的最低成本。

如果我们可以求出第n阶所有方格的q(i,j)值，取其最小值并逆向该路径即可得到最短路径。

记q(i,j)为方格(i,j)至其下三个方格（(i-1,j-1)、(i-1,j)、(i-1,j+1)）最低成本与c(i,j)之和，例如：

5 |
4 |     A
3 |   B C D
2 |
1 |
- + - - - - -
  | 1 2 3 4 5

q(A) = min(q(B),q(C),q(D)) + c(A)

定义q(i,j)的一般形式：

            |-  inf.                                                  j<1 or j>n
q(i,j) = -+-  c(i,j)                                                i=1
            |-  min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)   otherwise.

方程的第一行是为了保证递归可以退出（处理边界时只需调用一次递归函数）。第二行是第一阶的取值，作为计算的起点。第三行的递归是算法的重要组成部分，与例子A、B、C、D类似。从该定义我们可以直接给出计算q(i,j)的简单的递归代码。在下面的伪代码中，n表示棋盘的维数，C(i,j)是成本函数，min()返回一组数的最小值：

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i,j)
    else
        return min(minCost(i-1,j-1),minCost(i-1,j),minCost(i-1,j+1))+c(i,j)

需要指出的是，minCost只计算路径成本，并不是最终的实际路径，二者相去不远。与Fibonacci数相似，由于花费大量时间重复计算相同的最短路径，这一方式慢的恐怖。不过，如果采用自下而上法，使用二维数组q[i,j]代替函数minCost，将使计算过程快得多。我们为什么要这样做呢？选择保存值显然比使用函数重复计算相同路径要简单的多。

我们还需要知道实际路径。路径问题，我们可以通过另一个前任数组p[i,j]解决。这个数组用于描述路径，代码如下：

function computeShortestPathArrays()
     for x from 1 to n
         q[1, x] := c(1, x)
     for y from 1 to n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     for y from 2 to n
         for x from 1 to n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x)
             if m = q[y-1, x-1]
                 p[y, x] := -1
             else if m = q[y-1, x]
                 p[y, x] :=  0
             else
                 p[y, x] :=  1

剩下的求最小值和输出就比较简单了：

function computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1]
     for i from 2 to n
         if q[n, i] < min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

function printPath(y, x)
     print(x)
     print("<-")
     if y = 2
         print(x + p[y, x])
     else
         printPath(y-1, x + p[y, x])

4. 序列比对

序列比对是动态规划的一个重要应用。序列比对问题通常是使用编辑操作（替换、插入、删除一个要素等）进行序列转换。每次操作对应不同成本，目标是找到编辑序列的最低成本。

可以很自然地想到使用递归解决这个问题，序列A到B的最优编辑通过以下措施之一实现：

插入B的第一个字符，对A和B的剩余序列进行最优比对；

删去A的第一个字符，对A和B进行最优比对；

用B的第一个字符替换A的第一个字符，对A的剩余序列和B进行最优比对。

局部比对可在矩阵中列表表示，单元(i,j)表示A[1..i]到b[1..j]最优比对的成本。单元(i,j)的成本计算可通过累加相邻单元的操作成本并选择最优解实现。至于序列比对的不同实现算法，参见Smith-Waterman和Needleman-Wunsch。

对序列比对的话题并不熟悉，更多的话也无从谈起，有熟悉的朋友倒是可以介绍一下。

• 应用动态规划的算法

1) 许多字符串操作算法如最长公共子列、最长递增子列、最长公共字串；

2) 将动态规划用于图的树分解，可以有效解决有界树宽图的生成树等许多与图相关的算法问题；

3) 决定是否及如何可以通过某一特定上下文无关文法产生给定字符串的Cocke-Younger-Kasami (CYK)算法；

4) 计算机国际象棋中转换表和驳斥表的使用；

5) Viterbi算法（用于隐式马尔可夫模型）；

6) Earley算法（一类图表分析器）；

7) Needleman-Wunsch及其他生物信息学中使用的算法，包括序列比对、结构比对、RNA结构预测；

8) Levenshtein距离（编辑距离）；

9) 弗洛伊德最短路径算法；

10) 连锁矩阵乘法次序优化；

11) 子集求和、背包问题和分治问题的伪多项式时间算法；

12) 计算两个时间序列全局距离的动态时间规整算法；

13) 关系型数据库的查询优化的Selinger（又名System R）算法；

14) 评价B样条曲线的De Boor算法；

15) 用于解决板球运动中断问题的Duckworth-Lewis方法；

16) 价值迭代法求解马尔可夫决策过程；

17) 一些图形图像边缘以下的选择方法，如“磁铁”选择工具在Photoshop；

18) 间隔调度；

19) 自动换行；

20) 巡回旅行商问题（又称邮差问题或货担郎问题）；

21) 分段最小二乘法；

22) 音乐信息检索跟踪。

对于这些算法应用，大多未曾接触，甚至术语翻译的都有问题，鉴于本文主要在于介绍动态规划，所以仓促之中，未及查证。

• 相关

1) 贝尔曼方程

2) 马尔可夫决策过程

3) 贪心算法

• 参考

首先声明：本人没有解决掉这个问题。

相比第一道让CPU占用率曲线听你指挥对Windows系统中CPU占有率概念的考察和对API的使用，以及第二道中国象棋将帅问题对抽象建模的考察。这道题目才算是一道算法题吧？之前那两道尤其是中国象棋将帅问题总有点脑筋急转弯的味道。

题目：星期五的晚上，一帮同事在希格玛大厦附近的“硬盘酒吧”多喝了几杯。程序员多喝了几杯之后谈什么呢？自然是算法问题。有个同事说：

“我以前在餐馆打工，顾客经常点非常多的烙饼。店里的饼大小不一，我习惯在到达顾客饭桌前，把一摞饼按照大小次序摆好——小的在上面，大的在下面。由于我一只手托着盘子，只好用另一只手，一次抓住最上面的几块饼，把它们上下颠倒个个儿，反复几次之后，这摞烙饼就排好序了。

我后来想，这实际上是个有趣的排序问题：假设有n块大小不一的烙饼，那最少要翻几次，才能达到最后大小有序的结果呢？

你能否写出一个程序，对于n块大小不一的烙饼，输出最优化的翻饼过程呢？

排序问题是数据结构和算法中比较重要的一个了，之前在一篇被同事成为标题党的文章中因为提到排序中关于（非）稳定排序的概念还被很多TX鄙视了一番，甚至引来人身攻击，现在想来都有些后怕。

这道题目一眼看上去最先让我想到的居然是那道经典的汉诺塔（Tower of Hanoi）问题（当然，汉诺塔不算排序问题）。

1) 相似点★：

a. 都要不断调整位置，最终实现从小到大排好；

b. 都要借助中间量进行调整。

2) 不同处★：

a. 汉诺塔有多出来的两根针，翻烙饼只有一只手，明确说明没有第三只手；

b. 汉诺塔一次只能移动一个，翻烙饼没限制；

c. 汉诺塔要保证小的始终在上面，翻烙饼没限制；

d. 汉诺塔移动之前就有序，所以其移动次数是固定的，算法的逻辑也固定（不管是递归还是栈操作），翻烙饼没有这个前提。

3) 把题目用程序语言描述一下吧★：

a. Input : n.

b. Process : generate n random number 0-(n-1), sortting.

c. Output : 0, 1, ..., n-1, and move times num.

4) 存储结构★★★：

我最开始想到的是：这一摞烙饼其实就是一个双链表，每翻一次相当于将头节点H与某非头节点N进行如下变换：

H->next = N->next

N->prior = H->prior = NULL

N->next->prior = H

如果使用普通的双链表，这儿就有一个很明显的问题，H和N之间的所有节点（如果有的话）的前趋prior和后继next互换了，对于n比较大的情况，这个操作明显浪费时间啊（交换前趋prior和后继next和题目要求的翻几次似乎也没有关系吧？只是我作为一个一线的Coder考虑的太具体了）。如果摒弃前趋和后继的概念，又该怎样描述呢？

唐朝禅宗大师青原行思曾说：参禅之初，看山是山，看水是水；禅有悟时，看山不是山，看水不是水；禅中彻悟，看山仍然山，看水仍然是水。

俗：日，扯那么多，什么意思？

师：前趋不是前趋，后继不是后继。

俗：日，前趋不是前趋，难道是后继吗？

师：然也。

Fox：O, my God！整点实际的吧！翻转一次之后，前趋视为后继，后继视为前趋，第奇数次翻转的前趋是后继，第偶数次翻转的后继是前趋。

整个链表的形态如下：

H:Head, F:First, G:F's next, B:C's prior, C:Change, D, C's next, L:Last.

H<==>F<==>G<=...=>B<==>C<==>D<=...=>L

F与C交换的操作如下（Word、PS画图），n表示next，p表示prior：

这里只需要修改F、D节点的prior，H、C节点的next，其他节点不变。

后面想了一下，这种方式很难在不添加flag或者对换n、p的情况下正常操作，没有找到好的方法L，如果你有好的方法不妨告诉我。

最后只好作罢，何苦呢？直接使用数组就完了嘛J！既然是数组，除了翻转移动麻烦一点，理解和操作还是很容易的。

果然不是搞数学、算法出身的，一上来考虑的就是如何存储^.^''''，而不是算法本身。

更可笑的是，扯了半天，最后居然还是用数组！

5) 算法分析★★★★★：

冒泡排序思想：

最关键的是要抽象出随机数列特征（含当前和移动后数列特征的抽象），并尽量使每一次翻转有效（所谓有效，即尽量保证每一次操作都向最后的有序靠近而非背离 ）。

师：要使大头在后，应使大头在后。

俗：日，这是什么狗屁逻辑？

师：因果。在前既是在后。

俗：USA, CNN（操你娘）。

师：翻转。既不在前，也不在后，使之在前，使之在后。

俗：日，什么东西？既不在前，也不在后，不前不后，难道在中间啊？

师：然也。

Fox：O, my God！整点实际的吧！整个过程分为n轮，在第i(i=0, 1, ..., n-1)轮：

a. 找到大头n-i，是否有序？是，转g；

b. 是否大头在后？是，转f；

c. 是否大头在前？是，转e；

d. 将队头（第一个元素）与大头n-i对调（别忘了是翻转，中间元素也变序了），++times；

e. 将队头n-i与第n-i个元素对调，++times；

f. ++i，转a；

g. 输出序列（0, 1, ..., n）和翻转次数times；OVER:D。

快速排序思想：

在最开始的时候，我就想到使用快速排序的思想，先使整个数列局部有序，最后调整使全部有序。悲哀的是，在我考虑 4 3 1 2这个数列的时候，我断定还要通过上面的方式重新像冒泡排序一样重新来过，立即放弃想法，于是给了上面的思路，而且坚定的认为这个方法已经很好。结果，下午GR告诉我他的反例：4 3 1 2 --> 2 1 3 4|--> 1 2| 3 4，“|”表示从该处翻转。

我必须承认，这才是好的方法，我过分拘泥于不去改动已经有序的部分。然而，这家伙只知道反驳我，却无法给出算法。

我只好自己重新考虑局部有序之后的问题。

十分钟后，我有了如下的答案（目前我能想到的最佳答案），但不得不承认，表述算法比给出一种情况对应的解要麻烦的多的多的多，假定A、B满足A==B-1，即A、B为相邻数列（为简单记，元素和数列统称数列）。则A、B的组合类型有8种：B(O)A(O)、B(C)A(O)、B(O)A(C)、B(C)A(C)、A(C)B(O)、A(O)B(O)、A(C)B(C)、A(O)B(C)，O表示正向（obverse）C表示逆向（reverse），以1 2 3 4为例：

B(O)A(O)：3 4 1 2<2>、B(C)A(O)：4 3 1 2<4>、B(O)A(C)：3 4 2 1<5>、B(C)A(C)：4 3 2 1<7>；

A(C)B(C)：2 1 4 3<1>、A(O)B(C)：1 2 4 3<3>、A(C)B(O)：2 1 3 4<6>、A(O)B(O)：1 2 3 4<8>。

对应操作规则如下：

a. 0x0101: B(O)A(O) --> B(C)A(O)； 3

b. 0x0001: B(C)A(O) --> A(C)B(O)； 2

c. 0x0101: B(O)A(C) --> B(C)A(C)；1

d. 0x0000: B(C)A(C)：如果当前只剩A、B两个子列，则翻转一次成A(O)B(O)1 2 3 4为最终结果，否则，认为B(C)A(C)可以作为一个逆序有序数列考虑，暂时无需翻转；

e. 0x1010: A(C)B(C) --> A(O)B(C)； 3

f. 0x1110: A(O)B(C) --> B(O)A(C)；  2

g. 0x1011: A(C)B(O) --> A(O)B(O)；1

h. 0x1111: A(O)B(O)：A、B可以作为一个有序数列考虑，如果当前只有A、B两个子列，则正序序列A(O)B(O)1 2 3 4为最终结果。

上面规则的制定其实是反向导出的，遵循的原则是，正序有序的A(O)B(O)和逆序有序的B(C)A(C)可以看作一个序列，A(C)B(O)、B(O)A(C)可一步达到，B(C)A(O)、A(O)B(C)可两步达到，B(O)A(O)、A(C)B(C)可三步达到。即对于4个元素，最坏的的A(C)B(C)需要4步（对应于上面的冒泡法却只需要3步L）。而且当元素比较多的时候，记住1、2个有序子列是可行的，但对于完全无序的数列，分析出所有有序子列，既不现实，也无必要。

修改规则如下：当队头无序&&相邻数列有序||队头有序，翻转队头；否则，将队头连同该元素一同翻转。

由此可见，这算法还要改进：

a. 判断Array[0]是否正序连续（连续个数nNum1），如果nNum1==n，转i，如果nNum1!=1，转c；

b. 判断Array[0]是否逆序连续（连续个数nNum1），如果nNum1==n，翻转Array，转f；

c. 从下标nNum1开始查找Array[0]+1（bObserve = true）和Array[0]-1（bObserve = false）的下标nStart2，如果nNum1==nStart2，bOrder1==true，转e，如果nNum1!=1，置nEnd2=nStart2；

d. 判断( bObserve == true&&Array[nStart2]+1==Array[nStart2+1] ) || ( bObserve == false&&Array[nStart2]==Array[nStart2+1]+1 )，true则置nEnd2=nStart2，false则置nEnd2=nStart2+1；

e. 翻转Array[0] to Array[nEnd2]，转a；

f. 输出Array及times。

这样来看，改进后的算法竟简单了许多！

不幸的是：按上面给出的算法翻转合并1 3 5 6 4 8 7 9 2 0：

1 3 5 6 4 8 7 9| 2| 0

2 9 7 8 4 6 5| 3| 1 0

3 5 6| 4| 8 7 9 2 1 0

4 6| 5| 3 8 7 9 2 1 0

5 6| 4 3 8 7 9 2 1 0

6 5 4 3 8| 7| 9 2 1 0

7 8 3 4 5| 6| 9 2 1 0

进入死循环了……

很明显应该是下面这个样子：

1 3 5 6 4 8 7 9 2| 0

9 8 7 4 6 5| 3 1 2 0

5 6 4| 7 8 9 3 1 2 0

6 5 4 7| 8 9 3 1 2 0

4 5 6 7 8 9 3| 1 2 0

3 4 5 6 7 8 9 1 2| 0

1 9 8 7 6 5 4 3 2| 0

2 3 4 5 6 7 8 9 1| 0

9 8 7 6 5 4 3 2 1 0|

0 1 2 3 4 5 6 7 8 9

执行9次翻转。算法如何得到呢？

a. 确定最小无序完整子集Sn（Sn中含n>1个连续数）；

b. 将Sn最前面的有序子集So（o>1）加以考虑，一个子集？两个子集？

______________________________________________________________________________

O, my God!

这个问题，从前天晚上到现在，思考、分析、抽象了至少有15个小时以上了：

a. Apr.18th-19th: 23:00 - 01:30

b. Apr.19th: 11:00 - 13:00

c. Apr.19th-20th: 22:00 - 05:30

d. Apr.20th: 11:00 - 15:00

结果是，到现在无法给出一个最优的翻转算法。一个周末都花在这上面了，准备放弃L。

LP催着我让我回学校，是该回去了！

晚上没有加班，打游戏打到9点过，后面就又看了一道《编程之美》的题目《中国象棋将帅问题》。

题目：下过中国象棋的朋友都知道，双方的“将”和“帅”相隔遥远，并且它们不能照面。在象棋残局中，许多高手能利用这一规则走出精妙的杀招。假设棋盘上只有“将”和“帅”二子（如图1-3所示）（为了下面叙述方便，我们约定用A表示“将”，B表示“帅”）：

A、B二子被限制在己方3×3的格子里运动。例如,在如上的表格里，A被正方形{d₁₀, f₁₀, d₈, f₈}包围，而B被正方形{d₃, f₃, d₁, f₁}包围。每一步，A、B分别可以横向或纵向移动一格，但不能沿对角线移动。另外，A不能面对B，也就是说，A和B不能处于同一纵向直线上（比如A在d₁₀的位置，那么B就不能在d₁、d₂以及d₃）。

请写出一个程序，输出A、B所有合法位置。要求在代码中只能使用一个变量。

在纸上画了半天，Soft从台湾给带的长寿都让我抽完了，总算对得起这会儿工夫……

我的思路大致如下：

1) 只能使用一个变量nNum ==> 只能使用一个循环，nNum只能用来表示A、B位置的组合，nNum最大为9×9-1=80；

2) 如何用nNum表示一个A、B位置的组合？

下图表示A（红色）、B（蓝色）所在位置：

以nNum%9表示A的位置，nNum/9表示B的位置，如nNum==15，A==6，B==1。

3) 如何确定A、B位置的合法性？

规则都指定了，合法性的确定也就很简单了：A%3 != B%3。

OK，剩下的输出就很简单了，为了好看一点，这里希望直接按题目给的图表示出A、B的位置，如：“A:d10, B:e3”，还有颜色:D。

A的行号：A/3+8；

A的列号：A%3+d；

B的行号：B/3+1；

B的列号：B%3+d；

代码如下（注释掉的部分只是为了输出更“漂亮”一点）：

输出：

点击查看更清晰原图:D

PS: 刚写完，没有来得及总结更多，急着向LP炫耀。但上面的思路应该比较清晰了，也不管书上的答案了，反正我感觉我这点代码效率应该也不会低到哪儿吧:-)？

前两天在买《计算机程序设计艺术》中文版的时候，偶然发现《编程之美》这本书，当时翻了一下，看到“让CPU占用率曲线听你指挥”这样的题目确实让人为之一动。写一段代码，可以让CPU占有率曲线画出平滑的正弦曲线，有点意思:-)。

当然，最后没有买这本书，虽然我可以肯定这是本好书。

我从CSDN读书上找到几节，闲来读一读。今天来讨论一下《让CPU占用率曲线听你指挥》。

题目：写一个程序，让用户来决定Windows任务管理器（Task Manager）的CPU占用率。程序越精简越好，计算机语言不限。例如，可以实现下面三种情况：

1.    CPU的占用率固定在50%，为一条直线；

2.    CPU的占用率为一条直线，但是具体占用率由命令行参数决定（参数范围1~ 100）；

3.    CPU的占用率状态是一个正弦曲线。

在讨论具体实现之前，一个非常重要的问题是：什么是CPU占用率？

《编程之美》写道：“在任务管理器的一个刷新周期内，CPU忙（执行应用程序）的时间和刷新周期总时间的比率，就是CPU的占用率，也就是说，任务管理器中显示的是每个刷新周期内CPU占用率的统计平均值。”

打开“Windows 任务管理器”，“性能”中有“CPU使用记录”一项，给出的就是CPU占有率曲线。

至于一个刷新周期到底是多长，书中似乎没有明确给出，只是说“大约是1秒钟更新一次”，我打开Windows自带的时钟，也感觉大约是1秒钟。

另外的常识是：

单核环境下，空死循环会导致100%的CPU占有率。双核环境下，CPU总占有率大约为50%，四核会不会是25%左右呢？（我没有四核，只能猜测了，估计各核间切换也会耗掉点时间，因为我的双核环境并没有出现一核100%，另一核空闲的情况）。

当CPU整个刷新周期（绝大多数时间）空闲时，CPU占有率趋于0。

书中给出的正弦实现如下：

在单核环境（P4 2.40）下，其表现还是不错的：

点击查看大图

在双核环境（Core2 E4500）下，就有点差强人意不尽人意了：

点击查看大图

不过，总还能看出是正弦曲线。

上面两图的问题：

1) 单核时曲线不够平滑，是由于QQ等程序占用CPU所致；

2) 双核时曲线更加抖动，我的理解是除其他程序影响外，由于线程没有固定运行在一个CPU上导致的，后面看到书上提到线程迁移，个人感觉这个叫法欠妥啊，总觉得线程迁移令人费解。

可以立即想到的是：让进程在指定处理器上运行（处理器亲缘关系），由Windows提供了两个API可以做到这一点：GetCurrentProcess和SetProcessAffinityMask的。

修改之后的代码如下：

双核环境（Core2 E4500）修改之后的输出如下：

点击查看大图

我理想中的表现是：

1) 曲线是平滑的，最好不因其他应用程序或操作的执行而改变；

2) 不管是单核还是双核，峰值皆为100%，谷值为0。

对于第一点，其实就是保证任一刷新周期中的CPU占有率都可以被精确控制在0-100之间，如果你可以使CPU一直保持50%（而不是近似的上下波动），产生一条平滑的曲线就很easy了。

问题的关键在于，除了当前你写的程序可以控制，其他程序或操作如何控制？或者说：如何控制CPU的运行情况才是关键之处。

PS: 一晚上老是断网，搞得思路频频被打断，兴致也损了大半。总之，《编程之美》还是值得玩味一把吧:D。

本文写给满足以下条件的你（前面4点对应只读的你，后面4点对应只写的你)：

1) 经常阅读别人的Blog，所谓经常，平均每天阅读量在100篇左右；

2) 不希望花费大量时间在输入网址、鼠标点击和滚动上；

3) 有固定的阅读习惯，指专注于某一领域、某些特定的Blog；

4) 尚未使用或刚使用Google Reader并愿意使用Google Reader；

5) 经常更新自己的Blog，所谓经常，平均每月更新1篇或以上；

2) 不希望花费大量时间在复制、粘贴上；

3) 希望多与其他人交流；

4) 尚未使用或刚使用Windows Live Writer并愿意使用Windows Live Writer。

1、For只读的你

1) 启用Google Reader

做互联网的就是做互联网的，Google的Google Reader有个帐号就能开启。

之前写过一个给我GF看的一点东西，这儿对于启用Google Reader不再赘述了，有需要的TX可以看一下或者直接Google；

2) 添加RSS地址

首先要找到RSS地址，大多数网站提供的Blog，RSS地址都摆在显眼的地方，对于QQ空间这种算不上Blog的Blog来说，QQ空间的RSS也存在，比如，QQ号码为10000的用户，它的RSS就是：http://feeds.qzone.qq.com/cgi-bin/cgi_rss_out?uin=10000。

找到RSS地址之后，就可以将其添加到订阅列表里面了。

3) 关于OPML

如果你想共享或备份你的订阅，Google Reader具有“导入/导出”功能，不提供具体的使用方式了，Google吧。

4) 星标和标签

看过的好文希望下次再读，就加个星标吧。

RSS太多，就使用标签吧。

觉得我这儿写的太简单，就Google吧，或者看看Google Reader的四个常用小技巧。

2、For只写的你

1) 使用Windows Live Writer

做软件的就是做软件的，Microsoft的这个Windows Live Writer是要下载安装的。

具体如何去用，下载下来自然就会用了。

友情提示：Live Writer的格式、超链接、查看、草稿、帐户、日志、分类列表，都很好用。

2) 关于CSS

我不太喜欢Blog的页面太乱，一会儿五号字，一会儿二号字，一会儿宋体，一会儿楷体。

我喜欢把一些我认为重要的地方和链接的内容突出显示，以前没添加CSS的时候，每次都要自己去一个一个的修改链接的字体和颜色，浪费很多时间，如果你的Blog支持CSS，就去看一下怎么使用吧，比如我的CSS就很简单：

<style type=text/css>
#top a{ border-bottom:1px dashed; color:white;  }
#top a:link{ border-bottom:1px dashed; color:white; }
#top a:hover{ border-bottom:1px dashed; color:white; }
#top a:visited{ border-bottom:1px dashed; color:white; }
.post a:link{ border-bottom:1px dashed; color:maroon; }
.post a:hover{ border-bottom:1px dashed; color:maroon; }
.post a:visited{ border-bottom:1px dashed; color:maroon; }
.postbody a{ color:white; background:maroon;  }
.postbody a:link{ color:white; background:maroon;  }
.postbody a:hover{ color:white; background:maroon; }
.postbody a:visited{ color:white; background:maroon; }
</style>

我还使用了DevToolBar帮助我确定了CSS。

3) 添加Google专用的订阅

我为此还专门PS了一张图片，你可以将下面的代码放到“公告”里面，当然，你想放到哪儿就放到哪儿：

<br />订阅到：<br />
<a href="http://fusion.google.com/add?source=atgs&feedurl=http%3A//www.cppblog.com/Fox/Rss.aspx"><img src="http://www.cppblog.com/images/cppblog_com/Fox/6064/o_GoogleRss.jpg" border="0" alt="添加 游戏人生 到 Google 阅读器"></a><br />

我这儿是有图片的，只有文字的就是这样：

<br />订阅到：<br />
<a href="http://fusion.google.com/add?source=atgs&feedurl=http%3A//www.cppblog.com/Fox/Rss.aspx">添加 游戏人生 到 Google 阅读器</a><br />

上面的www.cppblog.com/Fox/Rss.aspx是我的RSS地址，你要换成你的:-)。

4) 关于邮箱地址

不要把邮箱地址直接放在页面上，我之前曾经这样做，后面每天收到不少的垃圾邮件，就取消了，因为这年头，写个邮箱地址搜索器，然后发垃圾邮件太easy了。

PS: 好用的东西还很多，因为我自己是GFans，所有在工作、学习和生活中使用了Analytics、Gmail、iGoogle、Picasa、Reader、Talk、笔记本、快讯、日历、网页历史记录、网站管理员工具、文件，反正都是免费的，而且用来比较方便，一个帐号可以搞定很多东西:D。

John von Neumann说：Any one who considers arithmetical methods of producing random digits is , of course, in a state of sin.

所以，在讨论算法实现随机数的时候，总是说“伪随机数”。

现在，应用最广的随机数生成算法是由Derrick Henry Lehmer1951年给出的线性同余法：

              Xn+1 = ( aXn + c ) mod m,  n>=0.

在上一篇伪随机数的论述中，并没有给出X0, a, c, m的取值规则，只是给出了ANSI C和Microsoft Visual C++的实现。

在这儿我们可以自己先思考一下，我们期望从上式中得到的随机数应该满足：

1) 上式的输出足够随机，这是最基本的要求；

2) 上式给出尽量多的输出，越接近m个越好（不可能超过m），即周期尽量长，最好为m，这样才能保证上式满足均匀分布（m个数在周期m中各出现一次m个数出现的概率相等）；

3) 上式的生成速度足够快。

最容易想到的，m的取值为计算机字大小（如2^32或2^64）。

但是这儿有个很严重的问题：Xn低位的随机性很弱。原因如下：

令d|m, 且

              Yn = Xn mod d

则

              Yn+1 = ( ( aXn + c ) mod m ) mod d

                      = ( aYn + c ) mod d

上述表达式的意义即：Yn为Xn低k位（d=2^k），这样的Yn序列形成周期为d甚至更短的同余序列。举例说明：d为2^1时，Yn为Xn的最低位（可假定为1或0），若Yn+1 != Yn，则Yn+2 == Yn必定成立，仅当a、c皆为奇数时Yn、Yn+1将0、1交替，否则，为常数（0或1）。

暂时抛开随机性不管，先找到周期为m的随机序列中的取值规则。

Donald Knuth在The Art of Computer Programming, Volume 2: Seminumerical Algorithms中的3.2.1.2节对m, a, c和X0取值规则的表述：

1) gcd(c, m) = 1. 即c, m互素，再白一点，c, m除1之外没有其他公因子；

2) 任给质数p, p|m ==> p|(a-1). 即m%p==0，则(a-1)%p==0。

3) 4|m ==> 4|(a-1). 即m%4==0，则(a-1)%4==0。

这个证明过程对于我这样的数论基础不是很扎实的搞应用技术的人来说有点难以理解了。有兴趣的话，还是去看3.2.1.2的证明吧:-)。

上面的规则告诉我们，满足了上述规则后，可以保证序列周期为m。对于前面提到的关于随机性的问题，既然Xn低位的随机性比较弱，可以只取Xn的高位作为输出。高位的随机性和统计意义由a, c确定，其取值涉及统计检验，具体的也还是看3.3吧。

这篇文章解决了具有统计意义的随机数的部分理论问题。

PS: 之前曾经BS过Windows Live Writer，当时觉得Writer编辑功能太少，不能直接设定链接文字的字体颜色，知道CSS可以设定之后，又觉得Word 2007编辑的Blog转成html之后太大，而且也知道Word 2007上面是可以设置链接的target为_blank的。现在发现Writer还是很不错的了，原来是可以设定格式的，也可以直接编辑html，而且可以Web预览，链接还可以加入到链接词汇表，挺方便的。

越来越发现Wikipedia是个和Google一样的好东西！

基本要求：
1、有软件工程思想,熟悉面向对象思想。
2、有良好的编码风格和文档编写习惯
3、熟悉C++语言,了解STL
4、了解多线程程序设计技术
5、热爱游戏、有游戏开发经验者优先
6、有团队开发精神优先

客户端程序员：
1、了解DirectX编程技术，有良好的数学、各种算法基础优先
2、有图形开发经验者优先
3、熟悉UI编程技术优先
4、熟悉引擎开发者优先

服务器端程序员：
1、熟悉通信以及网络安全技术. 熟悉TCP/IP协议及相关编程技术优先
2、有关系数据库编程及概念经验（MySql、PostgreSQL、MS Sql）
3、了解分布式服务器架构技术优先
4、了解Lua、Python有游戏脚本系统设计经验优先

办公地点：成都
有意向的朋友跟贴或发简历到zhouhejian@snda.com

一、随机数

软件实现的随机数生成器(random number generator, RNG)生成的随机数列大多是惟定数列，因此一般被称作伪随机数(pseudorandom number, PRN)，而基于热噪声(thermal noise)、光电效应(photoelectric effect)、放射性衰变(radioactive disintegration)等不可预知的物理现象实现的硬件随机数生成器(hardware random number generator)生成的随机数才被认为是真随机数(truly random number)。PRN在计算机领域主要用于仿真(simulation)和密码学(cryptography)。

本文仅讨论伪随机数软件实现算法，并且仅讨论满足均匀分布(uniform distribution, UD)的伪随机数发生器(pseudorandom number generator, PRNG)。非均匀分布(non-uniform distribution, NUD)的PRNG可通过满足均匀分布的PRNG与非线性函数生成。

本文讨论的PRNG应满足以下三点：

a. 在取值空间内满足UD，即等概率取得取值空间内任意值。

b. 充分随机，即该随机数列周期(period)应尽量长。此点由所谓的熵(entropy)度量。

c.