Tony Bai

一般在考虑到内存对齐的程序里面势必要使用数的圆整算式，一般来说在计算机程序里一般都是圆整到2的次幂上，而很多书上也有很多基于'移位'操作的圆整到2的次幂上的算法公式，形式都是很简单的，很实用。

这里要说的是一个圆整到任意正整数(n > 1，圆整到1没有必要^_^)的算式，突然觉得如果说算法有些大了。我们来推导一下，也不是严密推导。就是怎么想的怎么说。

如果有两个正整数a、b，其中a >= 1, b > 1，求a圆整于b后的结果？

这里不妨考虑三种情况：
(1) a = b
毫无疑问结果应该就是b；

(2) a > b
a > b > 1 => a/b >= 1(计算机语言中的a/b) => 圆整结果为(a/b + 1) * b；---(1)

(3) a < b
1 =< a < b => a/b = 0 (计算机语言中的a/b) => 圆整结果为b <=> (0 + 1) * b => (a/b + 1) * b。---(2)

从上面式子可以看出当a b时可以统一成(a/b + 1) * b，但是a = b时 (a/b + 1) *b = 2b显然和正确结果b不符。这时如何统一算式呢？我们从条件考虑：
假设我们现在有一个x = a - 1 > b > 1，从x > b我们可以通过代入上面的公式(1)得出圆整结果：(x/b + 1) * b，这里a有了更严格的限制 a > 2；同样有一个 1 =< x = a - 1 < b，同样代入上面的公式(2)可以得出圆整结果： (x/b +1) * b，这里a >= 2了。

由上面两个结果，可以推出另一个形式的圆整算式: ((a - 1)/b + 1) * b，它对于(a >=2，b > 1成立)
那么当1 =

这样((a - 1)/b + 1) * b对于a >=1，b >1就都成立了，这个算式形式就统一了^_^。

#define ROUNDTO(a, boundary) ((((a) - 1)/(boundary) + 1) * (boundary))

//测试一下
std::cout << ROUNDTO(1, 2) 输出结果：
2
3
21
7附：
也谈内存对齐

也谈内存对齐(续)

再说内存

三谈内存对齐－背后的故事

当一个算法(如二分查找)中包含对自己的递归调用时，关于这个算法时间复杂性的分析最终都转化为一个递归方程的求解问题，而这样的算法不在少数。实际上这是数学领域的问题，但是计算机科学又怎么能脱离数学而存在呢？^_^ 数学是好东西呀，可惜自己在这方面造诣颇浅，今生之遗憾亚。^_^

还好，解决递归方程涉及的数学知识我还是能应付的了的^_^。在MIT算法导论中介绍了3种方法，我们这里就说说这三种方法！这些是基础，如果以后要深入研究算法的话，这些知识是必须要精通的；如果并不想在算法方面有所深入的话，多学些知识也没错。我本身也是在学习，像这类的知识一般都比较死性，有些记住了，就可以掌握了。

1、Substitution Method
这是一种使用数学归纳法推导证明的方法，其步骤为先假设一个解，然后带入到递归方程中，利用数学归纳法推导，以验证假设的解是否合理。我们拿ITA(Introduction to Algorithm)中的例子说明吧，比较保险^_^。
[Ex1.]
T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。

解：(这里我们只来找上界)
我们假设T(1) = θ(1)，猜测一个解T(n) = O(n^3)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^3，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出：
T(n) = 4T(n/2) + n
     <= 4c((n/2)^3) + n
     = (c/2)n^3 + n
     = cn^3 - ((c/2)n^3 - n)
当c >= 2, n >= 1时，((c/2)n^3 - n) >= 0，这时T(n) <= cn^3，即T(n) = O(n^3)；

我们再回过头来看看当n = 1时这个解是否成立，即证明一下T(1) = θ(1)。对于1 <= n < n0, θ(1) <= cn^3 (c足够大)，即该推导出的解也满足初始条件，所以O(n^3)是T(n)的一个上界。但是O(n^3)是否是严紧的上界呢，我们不妨缩小上界范围再推导一次，这次我们猜测解为T(n) = O(n^2)，根据O符号的定义，我们得到对k < n, 有T(k) <= ck^2，把这个解代入到T(n) = 4T(n/2) + n，并进行推导得出：
T(n) = 4T(n/2) + n
     <= 4c((n/2)^2) + n
     = cn^2 + n
     = cn^2 - (-n)
不能严格符合T(n) <= cn^2的定义，所以推导失败。但是失败是不是说明，T(n) = O(n^2)一定不成立呢？我们再做一次最后的努力，当出现上面的这种情况时，我们假设解仍为：T(n) = O(n^2)，只是我们选择对k < n, 有T(k) <= ak^2 - bk，我们选择减去一个低阶的项，这不会影响到n足够大时的渐进性的，这里是一个常用的技巧。
T(n) = 4T(n/2) + n
     <= 4(a(n/2)^2 - b(n/2)) + n
     = an^2 - bn - (bn - n)
     <= an^2 - bn (当b >= 1时)

这样我们找到了严紧解T(n) = O(n^2)。

2、Iteration method(Recursion-tree method)
这个方法的思想是："迭代地展开递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计"。而我们可以借助'树'的形式来帮助迭代展开的过程。

[Ex2.]
T(n) = T(n/4) + T(n/2)+ n^2；解这个递归等式，分析T(n)的渐近性。

解：
T(n) = n^2 + T(n/4) + T(n/2)
     = n^2 + {(n/4)^2 + T(n/16) + T(n/8)} + {(n/2)^2 + T(n/8) + T(n/4)}
     = ...
     = n^2 {1 + 5/16 + (5/16)^2 + (5/16)^3 + ... }
     = θ(n^2)

3、Master Method
这是一种典型的套用公式的方法，解决形如'T(n) = aT(n/b) + f(n)'递归方程形的解的方法。这种递归方程是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子间题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。如果用T(n)表示规模为n的原问题的复杂性，用f(n)表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程'T(n) = aT(n/b) + f(n)'。

在f(n)的三类情况下，我们有T(n)的渐近估计式有三类情况：(log(b, a)表示以b为底的对数)
(1) 若对于某常数ε>0，有f(n) = O(n^log(b, a-ε))，即f(n)以慢于n^(log(b, a))的速率渐进增长，则T(n) = θ(n^(log(b, a))；

(2) 若有f(n) = θ(n^log(b, a) * (lgn)^k)，即f(n)以相似于n^(log(b, a))增长的速率渐进增长，则T(n) = θ(n^(log(b, a) * (lgn)^(k+1))，k为一常数，k >= 0；

(3) 若对于某常数ε>0，有f(n) = Ω(n^log(b, a+ε))，即f(n)以快于n^(log(b, a))的速率渐进增长，且对于某常数c > 1和所有充分大的正整数n有af(n/b) <= cf(n)，则T(n) = θ(f(n))。

举例来说吧：

[Ex3.]
T(n) = 4T(n/2) + n，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n我们得到a = 4, b = 2, f(n) = n, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2，而f(n) = n = O(n^(2-ε))，此时ε= 1，根据Case (1)，我们得到T(n) = θ(n^2)。

[Ex4.]
T(n) = 4T(n/2) + n^2，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n^2，我们得到a = 4, b = 2, f(n) = n^2, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^2 = θ(n^2 * (lgn)^0)，即k = 0，这样按照Case (2)，我们得到T(n) = θ(n^2 * (lgn)^(k+1)) = θ(n^2 * (lgn))。

[Ex5.]
T(n) = 4T(n/2) + n^3，解这个递归等式，分析T(n)的渐近性。

解：对T(n) = 4T(n/2) + n^3，我们得到a = 4, b = 2, f(n) = n^3, 计算得出n^(log(b, a) = n^(log(2, 4) = n^2, f(n) = n^3 = Ω(n^(2+ε)，此时ε= 1，且4f(n/2) = (n^3)/2 <= cn^3(c >= 1/2)，所以得到T(n) = θ(n^3)。

对于大部分人来说'Master Method'应该是最常用的，这几个Case可要牢牢记在心上才行哟。

在我的评论栏中有人说："你是程序员?"，我可以确定、一定以及肯定地告诉他/她：'我就是一个程序员，如假包换'。也许是最近技术类的blog写得少了，其他类的多写了些，让人家误会了，这也无可厚非。不过我倒是想到这样一个问题：程序员一定要满篇地谈技术么，程序员也有自己丰富多彩的生活呀。好了，切入正题。今天我们谈谈算法时间复杂性的分析。我没系统学过，都是在书上看到的以及MIT算法导论课上听到的。这里仅从我的理解的角度写一些罢了，不是很严谨哟。^_^

啥也别说，先看一段算法程序吧。这段代码以前在blog中出现过(摘自MIT Press算法导论2nd)，不过那时它是用来阐述'Pseudocode Conventions'的。
Insertion-Sort(A) △ A[1..n]
    for j <- 2 to length[A]
        do key <- A[j]
            △ Insert A[j] into the sorted sequence A[1..j-1].
            i <- j-1
            while i > 0 and A[i] > key
                do A[i+1] <- A[i]
                    i <- i-1
            A[i+1] <- key
假设我们目前没有学过什么算法复杂性分析之类的知识，如果让你去计算这个算法的运行时间的话，你会怎么做呢？最简单、最直观的方法就是把每条语句的执行时间累加在一起。对于上面这个简单的算法，我们'掰手指头'还是可以计算的。不过我们必须在计算前有个约定，什么约定呢，就是事先约定好一些'basic operation'的执行时间。我们定义一个'单位时间(UC, Unit Cost)'的概念，所有的语句的执行时间均为该'单位时间'的整数倍。那么这样我们可以约定并得出：
1、赋值操作、比较操作、算术运算、逻辑运算、访问(读写)单个常量或单个变量(包括一个数组的单个分量或一个记录的单个域)的时间为1 UC；
2、对于条件语句(if condition then ...)和'switch condition case 1...n'语句来说，它们的执行时间为'计算condition值的时间' + '最耗时分支语句的执行时间'，即T(condition) + max(Tcase1, Tcase2, ... Tcasen)；
3、对于for...loop语句，其执行时间显而易见为：'执行循环体的时间 x 循环次数'，一般来说这个循环次数都是显式可知的；
4、对于do ... while之类的循环语句，其执行时间类似于for ... loop，为：'执行循环体的时间 x 循环次数'，但其循环次数是处于隐含状态的；
5、对于goto语句，如果结构合理，无滥用goto的情况(如将控制权转移到goto前面的语句)，其运行时间忽略不计；
6、对于函数或者是过程调用，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行过程(或函数)本身，这时可以根据过程(或函数)调用的层次，由里向外运用规则(l)-(6)进行分析，一层一层地剥，直到计算出最外层的运行时间便是所求。

OK，知道了'时间约定'，我们就来算算这个算法程序需要花费我们多长时间呢。
for j <- 2 to length[A] --->>> (n - 2 + 1) x 1 = n - 1；
key <- A[j]             --->>> (n - 2 + 1) x 1 = n - 1；
i <- j-1                --->>> (n - 2 + 1) x 1 = n - 1；
while i > 0 and A[i] > key --->>> 由于while循环的'隐式执行次数'，这里我们设该语句执行了Tj次，那么该条语句需要 (1 + 1 + 1) x Tj = 3 x Tj；
do A[i+1] <- A[i]       --->>> (Tj - 1) x 1 = Tj - 1；
i <- i - 1              --->>> (Tj - 1) x 1 = Tj - 1；
A[i+1] <- key           --->>> (n - 2 + 1) x 1 = n - 1；
我们来作和: Total_Running_Time = 4 x (n - 1) + Sum(3 x Tj) + 2 x Sum(Tj -1) = 4 x n - 4 + 3 x Sum(Tj) + 2 x Sum(Tj - 1); j belongs to [2,n]。这里唯一的未知量就是Tj，如何确定Tj呢？考虑两种极端的情况：
1、输入数字串是已经排好序的(already sorted) -- Best Case
这里while i > 0 and A[i] > key语句只需执行一次，Tj = 1，这样我们可以得出：Total_Running_Time = 7 x (n - 1)，即n的线性函数；

2、输入数字串是逆序的(reverse sorted) -- Worst Case
此时A[i]要与A[1..j-1]的每一个元素比较，所以Tj = j - 1，这样我们可以得出：Total_Running_Time = 5/2 x (n^2 - n)；

奇怪我们算出了两种不同的结果，到底采用那个呢？相信从直觉出发，大家也都会选择'Worst Case'，'Worst Case'给了我们一种保证(guarantee)：针对某种规模的输入n，该算法能保证其时间复杂性不超过某个上界限(upper bound)。而'Best Case'大多是个'Cheating'，毫无意义的(meaningless)。在大多数算法领域我们使用的也是'Worst Case'分析，还有一种分析方式叫'Average Case'分析，就拿上面的'INSERTION-SORT'而言，如何计算其'Average Case'的时间复杂性呢？'Average Case'一般依赖一个前提假设，而这个假设都符合一定的'Probability distribution'，这里我们可以假定Tj = j/2，也就是说已经sorted的数字串中一半的值 > key，另一半 < key；这样计算出来的Total_Running_Time也是n^2一级的。

Ok，那么是不是针对每个算法都需要精确计算出其时间复杂性结果呢？我想不必要，在我们平时的工作中，多数时间是在选择算法，当然从事算法设计的专业人员除外，而选择算法的时候，我们大致只需要知道这个算法的一个时间上限即可，再根据特定的问题模型选择适当的算法。如何找到一个算法的时间复杂性上界是我们面临的问题。像INSERTINO-SORT这样的简单算法我们还可以处理，但随着问题规模的扩大，结构越来越复杂，算法分析的工作量之大、步骤之繁将令人难以承受，人们遂引入了'渐近性分析'方法，其主旨就是简化算法分析的工作量。看上面我们得到的INSERTION-SORT的'Worst Case'的结果：5/2 x (n^2 - n)，这个结果中既包含n^2又包含n^1，对于这个简单的公式我们还是可以分析的，但是对于复杂的算法，可能存在这样的计算结果：n的诸多高次幂多项式，这样的多项式分析起来较为复杂，而渐近性恰是简化这样问题的好方法。

什么是渐近性？用数学语言表述就是：对于f(n)，如果存在g(n)，使得当n > 0, n -> ∞时有：(f(n) - g(n)) / f(n) -> 0，则g(n) 称为 f(n)的渐近表达式。用工程上的方法表述就是：g(n)是f(n)中略去低阶项(包括常数项)所留下的最高阶项，所以它无疑比f(n)来得简单。有了渐近表达式，寻找算法时间复杂性的界限就相对容易了。以后比较两个算法，就只需要比较两个算法的渐近表达式了，这样极大的简化了工作量。

我们定义了几种常用的渐近性符号用来对算法进行渐近性分析：
1、O符号
常用来分析算法复杂性上限(upper bound)，其定义为：O(g(n)) = {对f(n)，n为正整数，存在正整数常量C和N，使得0 <= f(n) <= Cg(n)，n >= N}，可以看出O(g(n))是一个集合，为了表示T(n)是该集合内的一个成员，我们将之表示为：T(n) = O(g(n))。

2、θ符号
常用来给出算法复杂性的上下限(lower bound and upper bound)，其定义为：θ(g(n)) = {对f(n)，n为正整数，存在正整数常量C1、C2和N，使得0 <= C1g(n) <= f(n) <= C2g(n)，n >= N}，可以看出O(g(n))也是一个集合，为了表示T(n)是该集合内的一个成员，我们将之表示为：T(n) = θ(g(n))。由于给出了上下限，所以θ符号集合为O符号集合的子集。

3、Ω符号
常用来分析算法复杂性的下限(lower bound)，不常用。其定义为：Ω(g(n)) = {对f(n)，n为正整数，存在正整数常量C和N，使得0 <= Cg(n) <= f(n) ，n >= N}，可以看出O(g(n))是一个集合，为了表示T(n)是该集合内的一个成员，我们将之表示为：T(n) = Ω(g(n))。

有了这些符号我们再来看看如何理解带有渐近性符号的一些等式:
[例1] 渐近性符号仅仅用在等式右边
如：2n^2 + 6n + 1 = 2n^2 + θ(n)，这里我们可以将该等式看成2n^2 + 6n + 1 = 2n^2 + a(n)，这里a(n)是一个匿名函数，并且a(n)是θ(n)集合中的一个函数。

[例2] 渐近性符号出现在等式两边
如：2n^2 + θ(n) = θ(n^2)，按照[例1]中匿名函数的方法，我们可以得到: 2n^2 + a1(n) = a2(n)，其中a1(n)属于θ(n)集合，a2(n)属于θ(n^2)集合。这个等式需要这样理解"无论等式左边的匿名函数a1(n)取任何函数，等式右边的总存在一个匿名函数a2(n)使等式相等"。

以上是渐近性分析的一些基本知识，但是在实践中还是需要技巧的，实践证明在渐近性分析存在大量的递归函数，要想真正掌握复杂算法的渐近性分析，解决递归问题必不可少，不过这是以后的内容了。

Pseudocode，即伪码，它常常用来描述一个算法，目的是能使被描述的算法能够容易的以任何一种计算机程序语言实现。'Pseudocode Conventions'可以理解为'伪码约定'，既然是'约定'那就并非强制性的标准。但是在专业的有关算法的文献和资料中，其相关内容多符合这些'Pseudocode Conventions'。如果你是一个想学习和钻研算法的人，那么建议你熟悉这些'Conventions'，俗话说：'磨刀不误砍柴工'吗！

'Pseudocode Conventions'应该说也是有多种多样的，但是随着这么多年的积累和进化，渐渐的一些'Conventions'退出了人们的视线，此时你在一些重要的图书典籍上能看到的大概就是被人们广泛接受的一种'Convention'了。这里介绍一种比较常用的'Pseudocode Convention'，这种'Convention'在MIT Press出版的'Introduction to Algorithms 2nd'中被广泛采用，在国内的一些算法书籍中也是'屡见不鲜'。

介绍'Pseudocode Conventions'其实与介绍一种程序设计语言的语法相似，看多了就会产生厌烦，这里先给出一个例子，让大家有个感性认识，找到一种新鲜感。^_^

这个例子源于'Introduction to Algorithms'一书中的那个著名的'Insertion-Sort'：
Insertion-Sort(A) △ A[1..n]
    for j <- 2 to length[A]
        do key <- A[j]
            △ Insert A[j] into the sorted sequence A[1..j-1].
            i <- j-1
            while i > 0 and A[i] > key
                do A[i+1] <- A[i]
                    i <- i-1
            A[i+1] <- key

对应上面的例子，下面是对该'Convention'的一些阐述条款：

1、每个指令占据一行，指令结束或者说行尾无任何符号。
2、利用'缩进(Indentation)'表示程序的块结构(Block Structure)。
3、符号'△'表示该行其后面的内容为注释。
4、'i <- j'为赋值语句，表示将j的值赋给i；而'i <- j <- e'这样的多重赋值形式则等价于'i <- e', 'j <- e'。
5、变量无需声明；一般情况下变量局限于某一特定的Procedure，除非有显式说明我们才使用全局变量。
6、数组A通过A[index]方式访问到数组内元素的值。
7、条件判断语句格式如下：
if (Condition1)
    then [ Block 1 ]
    else if (Condition2)
           then [ Block 2 ]
           else [ Block 3 ] 

8、支持三种循环语句：while、for、repeat ... until。'for t <- 0 to n'表示 t范围为[0, n)。
9、复合数据用对象(Object)来表示。对象由属性(Attribute)和域(Field)构成。域的存取是由域名后接由方括号括住的对象名表示，如上面李子中的length[A]，数组A被看成为一个Object，其域有length，表示数组中元素的个数，即length[A]。用于表示一个数组或对象的变量被看作是指向表示数组或对象的数据的一个指针。对于某个对象x的所有域f，赋值y<-x就使f[y]=f[x]，换言之，在赋值y<-x后，x和y指向同一个对象。有时一个指针不指向任何对象，这时我们赋给它NIL。
10、参数传递方式为'值传递'方式，被调用的过程拥有自己的参数拷贝，被调用过程对参数的修改是不能被调用者看到的。当传递一个对象时，只是拷贝指向该对象的指针，而不拷贝其各个域。
11、布尔运算符'and'和'or'都是'short circuiting'的。如计算表达式'x and y'，如果x为FALSE，那么整个表达式就为FALSE，我们不再计算y了。

OK，罗列了11项，照比C这类的高级语言，这种'语法'显然简单的多，更易理解。以后要做的就是尽量在进行算法描述的时候使用这种'Pseudocode Convention'，毕竟熟才能生巧！

33.00s和14.27s，两个截然不同的运行时间值，两次提交尝试解决素数回文问题，终于搞定了！用两个字形容'恼人'！算法不复杂，就是要求时间很'紧'，大部分工作都在考虑着如何缩短运行时间。桃花在冷空气袭来的日子都开了，我的心也算可以放下了！

最近项目吃紧，连续两天没有做ACM习题了，手都有些生了^_^！按照Volume1的习题顺序，该轮到1004题了！这是一道关于'素数回文(Prime Palindromes)'的习题，源自'USACO'，估计是什么比赛吧！大家一定都知道什么是素数，或者又叫质数！那么什么是回文(Palindromes)，不用定义，举几个例子大家就明白了，如121、1331、14741、89098等等看起来对称的数都叫做回文数，具体的定义或者数学上的定义我也没找到，好像对解决此题关系也不大！

Ok!我们来看一下题目，题目很简单，找出输入的两个数之间的所有素数回文，并按照数值顺序输出，每行一个数！要求：运行时间在15秒以内。输入值范围[5, 1000000000]。

如果不估计时间，大家脑中一定选中了'遍历'这种方案，而达到目标前所要解决的两个问题包括如何判断一个数是否是一个素数和如何判断一个数是否为一个回文数？

如何判断素数？这个在大学学习C语言的时候好像是习题，不过算法早已经忘到了'九霄云外'，这样自己就顺手写了一个宏：
#define IS_PRIMER(i) \
        ((i <= 10) \
         ? (i == 2 || i == 3 || i == 5 || i == 7) \
         : (((i % 2 == 0) || (i % 3 == 0) || (i % 5 == 0) || ( i % 7 == 0)) ? 0 : 1))
用几个数测了一下，屡试不爽！为了更加精确的测试，还是到网上找一个素数表吧！这样有参照的测试势必比较准确无误。试着用这个宏找出500以内的所有素数，发现与素数表中的个数不符，仔细查查，一眼就看到了121这个数，按照我的算法，它就是个'素数'了，但实际上它还能被11所整除，别忘了素数的定义："不能被1和自己之外的任何数整除"，看来我的算法是'漏洞百出'，不过在100之内它是有效的，起码算是个'Uncompleted Algorithm'^_^。重新修整一下，改进版如下：
int is_primer(int x) {
        int i;
        for (i = 2; i <= sqrt(x); ++i) {
                if (x % i == 0) {
                        return 0;
                }
        }
        return 1;
}
这种算法也是网上常见的算法，如果和外层的遍历一起来看，这是个接近O(n^2)的算法，显然性能不高！不过目前还少有好算法公布在网上，就暂用这个吧，我也想不出来什么好方法！也许需要好的数学功底才能提高该算法性能！

如何判断回文？这就是个'见仁见智'的问题了。这里提供两种方案，感觉性能上差不多，各有千秋：
[方案一]
/* 获取一个数i的位数n */
#define GET_DIGITS(n, i) do { \
                n = 1; \
                while (i >= pow(10, n)) { \
                        n++; \
                } \
        } while(0)

/*
 * 从外到内，比较每一个对称位上的数值是否相等
 * 如果全相等则是回文，否则不是。
 *
 * ! 这种方法还是很容易想出来的
 */
int is_palindrome(int x) {
        int     i = 0;
        int     j = 0;
        int     n = 0;

        int     high = 0;
        int     low = 0;

        GET_DIGITS(n, x);
        j = (n % 2) ? ((n-1) / 2) : (n / 2);

        for (i = 1; i <= j; ++i) {
                low = x % (int)(pow(10, i));
                high = x/(pow(10, n-i));
                if (low != high) {
                        return 0;
                }
        }
        return 1;
}

[方案二]
/*
 * '回文数'再造
 * 从低位到高位，按'低位 * 10 + 高位'累加的方式得到一个数
 * 如果该最终数值与原数一致，则为回文数，否则不是
 *
 * 这个方法对后面的方法还是很有启发的！
 */
int is_palindrome(int x) {
        int     rv = 0;
        int     i = x;

        while (i != 0) {
                rv = rv * 10 + i % 10;
                i = i / 10;
        }

        return rv == x;
}

现在两个难题都解决了，我们只需要遍历加判断即可。那么是先判断素数还是先判断回文呢？看起来判断素数较浪费时间，那我们先判断回文吧！第一次提交代码，不出所料，运行时间33s(我想不止33s，也许33s只是服务器的一个时间上限，大于该时间的统一显示为33s)。看来我们的重新考量一下我们的方案了！这种遍历+判断的方法无论如何是不能够蒙混过关的了^_^。

那么怎么来做呢？方案一是拿来一个数，我们来判断是否是回文，这样绝大部分的数都不是回文数，那么这些判断也都是无效的，但却占用了大量的时间，我们能不能尽量让我们每步操作都是生成结果之路上有效的一步呢？我们来尝试自己生成一定范围内的回文数。回文数组成是有一定的规律可循的。现在我们可以将问题集中在'如何生成位数为n的所有回文数'上！我们举几个例子就能看得出来：
[例子]
6446 -- 我们可以看成两个部分 -- 高二位的64和低二位的46互为反序数，我们也可以理解为高二位的值随着低二位的变化而变化；
64546 -- 我们可以看成三个部分 -- 高二位的64和低二位的46互为反序数，再加上中间的一个独立变化的值，我们也可以理解为高二位的值随着低二位的变化而变化；中间值独立变化；

可以看出我们的算法可以将处理分为两类：奇数和偶数。
1、如何生成位数为偶数位的所有回文数？
算法名称：gen_even_palindrome
输入项：n (回文数的位数)
算法步骤：
gen_even_palindrome(n) {
 j = n/2; /* j为独立变化的低位部分的位数 */
 k = (10^j - 1); /* k为独立变化的低位部分的上限值 */
 for (i = 1; i <= k; ++i) {
     /*
      * 这里的i就是低位部分独立变化的值
      */
     if (i % 10) {
      /* 如果 i = 10、1000等这些10^n的数，它们是没有回文的 */
       continue;
     }

     rv = _gen_even_palindrome(i, n); /* rv就是一个n位回文数 */
 }
}

_gen_even_palindrome(x, n) {
        int i = x;
        int j = 1;
        int rv = 0;

 /*
  * 利用低位部分的信息，造出高位部分的数值
  */
        while (i != 0) {
                rv += ((i % 10) * pow(10, n-j));
                i = i / 10;
                j++;
        }

 /* 最后的回文数还要加上低位部分的数 */
        rv += x;
        return rv;
}

2、如何生成位数为奇数位的所有回文数？
算法名称：gen_odd_palindrome
输入项：n (回文数的位数) n > 1 对n = 1作特殊处理便是
算法步骤：
gen_odd_palindrome(n) {
 j = (n + 1)/2; /* j为独立变化的低位部分的位数 */
 k = (10^(j-1) - 1); /* k为独立变化的低位部分的上限值 */

 for (h = 0; h <= 9; ++h) { /* 中间位独立变化 */
  for (i = 1; i <= k; ++i) {
   /*
     * 这里的i就是低位部分独立变化的值
     */
   if (i % 10) {
    /* 如果 i = 10、1000等这些10^n的数，它们是没有回文的 */
    continue;
   }

   rv = _gen_odd_palindrome(i, h, n); /* rv就是一个n位回文数 */
  }
 }
}

_gen_odd_palindrome(x, mid, n) {
        int i = x;
        int j = 1;
        int rv = 0;

 /*
  * 利用低位部分的信息，造出高位部分的数值
  */
        while (i != 0) {
                rv += ((i % 10) * pow(10, n-j));
                i = i / 10;
                j++;
        }

 /* 最后的回文数还要加上中间数和低位部分的数 */
 rv += mid * pow(10, (n-1)/2);
        rv += x;
        return rv;
}

至此，我们算是解决了如何生成回文数的问题了，不过目前还有一点不能满足，那就是按照数值顺序来输出回文素数，不知道大家发现没有，上面的回文数生成算法不能保证按照数值顺序生成会文数，所以我们还要再动动脑筋！

这里不妨尝试一下作弊！^_^ 由于回文数生成算法不能保证按照数值顺序输出回文数，那么我们势必需要记下来已经生成的回文数，那么到底有多少回文素数需要记下来呢？我们可以利用前面提到过的'遍历'方案在本地计算一下，结果是不到10000个，那么OK！我们就分配一个大数组，并用一个static global variable记下当前数组使用情况，待所有的回文素数都写入数组，我们对该数组进行一次quick sort，这又需要有个quick sort算法(O(nlogn)级别的，简单快速是我选它的原因)，不过这个比较容易，这里也不详述了。

把这个'回文生成'解决方案提交后，得出14.27s的结果，状态: Accepted。对了千万别忘了，这里还加了些优化，比如不存在位数为6的素数回文，所以当判断n = 6就直接返回，省着走冤枉路！14.27s属于刚及格范畴！该题肯定还有更快的解法，由于太烦，这里就浅尝辄止了！^_^

关于算法的文章我一直想写，但算法是我的软肋，自己难于下笔。首先自己非科班出身，没有进行过系统的算法设计课程训练；再者自己到目前为止还从未独立设计过一个完整的、实用的算法，在平时工作中较少的涉及到算法设计，这不能说不是一个遗憾。也许有人会问："算法难道还没有过时吗，算法不是属于'Donald E. Knuth'那一代人的事情吗?'。我很难回答这个问题，不过当我今天看到CSDN上的一篇题为'算法是百度工程师的利器'的文章后，我隐约看到了算法的回归！

谈到目前互联网上最热的是什么？100个人有99个会回答：'搜索'，剩下的一个的答案是'Google'。没错！技术公司出身的Google和Baidu在成功背后到底是什么在支撑呢？名为技术，实则算法。Google的成功难道不是'page rank'算法的贡献么？Baidu站在行业的顶峰其脚下也少不了优秀的算法设计。从Baidu工程师入司的练习题也可以看出Baidu是何等的重视算法。可以说搜索引擎技术带来了算法的回归。

2006第四期'程序员'杂志推出了一期技术专题，叫'算法的力量'，在我的印象中'程序员'杂志好像是第一次推出算法专题。由于没买这期杂志所以这里也不知道其中的细节。谈到算法我们不能不提到算法的学习。Donald E. Knuth的'The Art Of Computer Programming'可以说是举世公认的算法领域的鼻祖之作，以至于很多人把这三卷书买回家恭恭敬敬的'供起来'^_^。从这点也可以看出如果拿这本书作为教程的话，难度可见一斑。我们还是介绍点'通俗'的。首当其冲的就是MIT的'算法导论'开放课程(6046)，最新一期的开放课程还有Video可供下载，主讲教师就是'算法导论第二版'的作者之一Charles E.Leiserson。我觉得大师级人物的课与一般讲师不同之处在于其对知识本源的发掘、揭示和解释，有着亲身体会的大师们的见解会让你身临其境印像深刻。当然这门儿课也是一门'大部头'的课，其教材'算法导论第二版'也是一本足以'砸死人'的'大砖头'，国内早在2003年就出版了其英文版，出版社应该是高教。记得当时还在读大三，但我去母校的大学书店买书的时候，店员告诉我"这是哈尔滨第一批展示品，本来是不准备卖的，你消息还挺灵通的吗"。就这样我买下了那本大部头，遗憾的是到目前为止它还和刚买来的时候一样新^_^。

正如百度首席架构师所说："搜索引擎开发中使用的基本算法大部分都在大学课程中涵盖了。对于一个人来说，在学校学习过这个算法，和能够灵活运用是两个概念。只有通过参与较多的项目开发和程序编写，将算法和应用相结合，才能在这方面得到较好的发展。"，单单死扣书本上的东西去学习算法是不能设计出好算法的，必须通过一个不断思考、实践、创新和总结的良性循环，你才能发现算法设计的真谛。最近自己也在理论和实践相结合的锻炼自己的算法能力，而尝试ACM练习是一个很好的将理论和实践相结合的方法，大家也不妨试试。

要想在算法领域有所深入，数学基础必不可少，相信很多人都能意识到这一点，前几天Google的一位科学家吴军在'Google黑板报'上贴出了一篇叫'数学之美'的Blog，也谈了数学工具在Google内部技术研究的重要性。其实对计算机知识认识越深的人越能认识到数学无处不在，CSDN编辑孟岩的一篇文章'数学与算法随想'让我们感受到数学语言的魅力！

题外话：在'南合文斗'的'让泪化作相思雨'-歌曲美妙节奏的驱动下，我的思维好像跑在美国的高速公路上，那是相当的快！周末了，一切都要放下放下！^_^

这又是一道ACM练习题，我的原则就是如果有时间，坚持每天考虑解决一道吸引我的ACM练习题，今天这道'Mixing Milk'题并不难，不过里面蕴含着一个基础的算法，毕竟对算法一类的知识生疏已久，今天就拿它做一次回顾吧！

这道'Mixing Milk'(1003)题目前在'在线测试'系统上的状态是474/1207=39.27%(即accepted/submit=ratio)，算是中等偏下难度的题了，照比我昨天作的1002题要简单(我的感觉)。起码看题之后思路清晰^_^。

'Mixing Milk'的题目大概是这样的，原题是英文，这里把它简单用中文描述一下：说牛奶制品行业是个薄利的边缘行业，那么这个行业靠什么赚钱呢？只有靠降低采购成本。现在有这么一家牛奶厂，每天的牛奶采购量为N(0 <= N <= 2,000,000)，而这些牛奶是从M(0 <= M <= 5,000)个奶农那采购的。当然奶农的牛奶的价格是不一致的，现在你是一个牛奶采购员，如果让你去到奶农那采购牛奶，如何能使采购量为N，而成本却最小，最后根据输入计算出这个成本值。输入输出的格式参见下面的例子：
输入：
100 5 --- (1)
5 20 --- (2)
9 40
3 10
8 80
6 30
输出：
630

简单说一下输入输出，输入部分第一行(1)，这里输入两个数，依次为牛奶厂一天的采购量以及奶农的个数；输入第二行至最后一行描述的都是奶农的信息，以(2)行为例：5 表示 奶农牛奶代价，20表示这天奶农能够提供的最大牛奶量。输出就是采购的总成本。

其实很多人看到这个题就会马上有思路了，可能很多人都会有这样的大众想法："即将输入按照牛奶代价从低到高排序，然后从低的开始采购，直到采购足一天需要的奶量即可"。

这里一个让我回忆起大学曾经学过的诸多排序算法：冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序等等，这里我选择了'插入排序'。也许很多人记不清插入排序是怎么回事儿了，见怪不怪，工作之后接触业务流程性的东西较多，而接触基本算法的机会则少只有少，大多数情况你只需要调用一个已经封装好的接口或着基础库即可。这里简单回顾一下'插入排序'算法，更精确的说法是'直接插入排序'。

[直接插入排序算法]
(1) 基本思想
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
(2) 算法描述
Input: R[1..N]

/* 对R[1..N]按递增序进行插入排序, R[0]是'哨兵'
Procedure InsertSort(Var R[N] : DataType);
 Begin
  for I := 2 To N Do
  begin
     R[0] := R[I]; J := I - 1;
     While R[0] < R[J] Do /* 查找R[I]的插入位置 */
     begin
        R[J+1] := R[J]; /* 将大于R[I]的元素后移 */
        J := J - 1
     end
     R[J + 1] := R[0] ; /* 插入R[I] */
  end
 End; /* InsertSort */

(3) 效率分析
由于算法中有一个嵌套选环，所以估算直接插入排序的时间复杂度为O(n^2)，是一个稳定的排序方法。

(4) 示例
初始序列 5|  2  8  9  7  1
i = 1           2  5|  8  9  7  1
i = 2           2  5  8|  9  7  1
i = 3           2  5  8  9|  7  1
i = 4           2  5  7  8  9|  1
i = 5           1  2  5  7  8  9|
 
这个算法实现起来并不很难，下面是'Mixing Milk'的解决方案(实现插入排序时没有使用'哨兵'，和上面的算法描述不完全一致)，已被在线测试系统Accepted，但未经雕琢过哟(感觉这道题算法重要，其他次之)，呵呵。

/*
 * solution for 1003 in Problems Volume I
 */

#include <stdio.h>
#include <stdlib.h>

int main(void) {
        int     total_milk_per_day;
        int     total_farmers;
        int     i;
        int     j;
        int     k;
        int     h;
        int     *price_amount_pair;
        int     total_price     = 0;
        int     cur_amount      = 0;

        /*
         * 获取牛奶厂每天需要牛奶量和供货商总数
         */
        (void)scanf("%d %d", &total_milk_per_day, &total_farmers);

        price_amount_pair = (int*)malloc(total_farmers * 2 * sizeof(int));

        /*
         * 获取每个供货商的单价和提供量
         */
        for (i = 0; i < total_farmers; ++i) {
                k = 2 * i;
                (void)scanf("%d %d", price_amount_pair + k, price_amount_pair + k + 1);
        }

        /*
         * 利用插入排序使列表从前到后, 单价递增
         */
        for (i = 1; i < total_farmers; ++i) {
                for(j = 0; j < i; ++j) {
                        if (*(price_amount_pair + 2 * j) > *(price_amount_pair + 2 * i)) {
                                k = *(price_amount_pair + 2 * j);
                                h = *(price_amount_pair + 2 * j + 1);
                                *(price_amount_pair + 2 * j) =  *(price_amount_pair + 2 * i);
                                *(price_amount_pair + 2 * j + 1) =  *(price_amount_pair + 2 * i + 1);
                                *(price_amount_pair + 2 * i) = k;
                                *(price_amount_pair + 2 * i + 1) = h;
                        }

                }
        }

        for (i = 0; i < total_farmers; ++i) {
                if (cur_amount < total_milk_per_day) {
                        k = *(price_amount_pair + 2 * i + 1);
                        h = *(price_amount_pair + 2 * i);
                        if ((cur_amount + k) > total_milk_per_day) {
                                j = total_milk_per_day - cur_amount;
                                cur_amount += j;
                                total_price += (h * j);
                                break;
                        } else {
                                cur_amount += k;
                                total_price += (h * k);
                        }
                } else {
                        break;
                }
        }

        printf("%d\n", total_price);
        free(price_amount_pair);
        return 0;
}

发现做ACM练习题居然可以上瘾！^_^

说来惭愧，今天才真正做过一道ACM练习题。自从上个月发现我的母校上有ACM的在线测试站点，我就下决心好好潜心做题，一来提高一下自己解决问题的能力，一方面也想在算法方面多实践实践，而且每天都花一定时间写程序还可以锻炼自己的思维能力。总而言之，由于项目繁忙以至直到今天才开始做第一道ACM练习题，做题的过程'坎坷不平'，让我印象深刻亚!^_^

有人会说：'ACM'中的题都是不实用的，没有实际意义。我之前也曾经是这么想的。不过今天的作题过程让我完全推翻了以前的想法，我发现ACM的习题是很能锻炼个人的思维能力、编程能力的。就拿今天我做的这道看似简单的问题，实际上其背后也蕴含着很多基础理论，如果没有很好的理论基础做后盾，我相信很多人都会在这道题上'碰个头破血流'。

在看题之前我不能不说母校的那套ACM在线测试系统，你只需要做一个简单的注册，即可使用该系统，目前系统支持C/C++良种语言的提交代码，系统会自动对你的源码进行编译、运行和测试，并在你提交代码后大约5分钟内给出你结果。系统提供一个'Problem Set'供大家解决，目前这个'Problem Set'中有超过1000个题目，有兴趣的人大可以去试试，没有什么奖励，就是兴趣而已，特别是像我们这些已经毕业的人更不可能以参加ACM竞赛为目标了^_^。该站点还提供一个论坛，供解决问题者交流心得。

解决ACM练习题不同于开发商业软件，所有的题都有明确的'输入范围'，所以在程序里无需'断言'等'Precondition Check'，对异常的处理也无需太过考虑。ACM主要锻炼的是你的思考过程、算法设计能力以及快速解决问题的能力。要想达到一个很高的层次，需经过大量的训练才可以。

大多数人在解决'Problem Set'中的问题时都是从Problems Volume I开始，我也不例外。Volume I的第一道题1001我觉得是个举例，没必要对它进行过多研究。看完1001后，进入1002，这也是本文想说的一个实例。

1002问题的题目为'A+B+C'，具体内容描述如下：
"For each pair of integers A B and C ( -2^31 <= A, B, C<= 2^31-1 ), Output the result of A+B+C on a single line. "

Sample Input
1 2 3
3 4 3

Sample Output
6
10

题目看起来很简单，不细心的人很可能把1001的解决方案直接拿过来套用，这样当然是错的了。那么这道题到底需要什么知识呢？我们大致来分析一下：这道题其实就是一个加法题，唯一让大家担心的就是几个输入数据的范围照比1001的[1, 10]要扩大了，扩大到无符号整型范围，这样就导致我们必须考虑一个问题：那就是'溢出'问题。很多人都能想到这，那么如何解决这一问题呢？

首先拿出一个方案看看可行不：
[方案一]
#include <stdio.h>

int main(void) {
        int       a;
        int       b;
        int       c;

        while (scanf("%d %d %d", &a, &b, &c) == 3) {
                printf("%d\n", a + b + c);
        }
        return 0;
}

首先将a, b, c定义为int(一般系统的实现都把int默认为unsigned int)可以满足输入需求，但是a + b + c显然可能会溢出，导致结果不正确。

[方案2]
既然直接使用a + b + c，并使用%d输出会溢出，那么我们用一个更大的数据类型来存储相加后的结果呢，这样可行么？不妨看看。
#include <stdio.h>

int main(void) {
        int  a;
        int  b;
        int  c;
 long long rv;

        while (scanf("%d %d %d", &a, &b, &c) == 3) {
  rv = a + b + c;
                printf("%lld\n", rv);
        }
        return 0;
}

我们用2147483647 1 1测试后发现结果为-2147483647。显然这一方案也不成，不过我们得知道为什么不成才能继续给出新的方案。这个方案就在于rv = a + b + c这条语句上，这里有一个原则我们必须先明了，那就是ANSI C在'一般算术运算'的时候采用'值保留'的原则，这区别于K&R C的'无符号保留'原则，我们下面具体分析一下：
a = 2147483647(d) = 0x7FFFFFFF;
b = 1(d) = 0x00000001;
c = 1(d) = 0x00000001;
a + b + c = 0x80000001;
那么0x80000001转为为十进制整型值是多少呢？这里有人认为是-1(d)，这当然不对，我们该如何通过这个0x80000001找到其对应的十进制值呢？我们知道采用二进制补码方式正整数d对应的-d的计算方法为：-d = (~d + 1); 所以我们通过-d求d就可以这样做：
0x80000001 - 1(d) = 0x80000001 - 0x00000001 = 0x80000000;
0x80000000逐位取反得到0x7FFFFFFF, 而0x7FFFFFFF = 2147483647(d)，所以我们得出0x80000001 = -2147483647(d)。
这样rv = a + b + c就变成了rv = -2147483647(d)，同样是'值保留'，那么一个long long类型的rv转换为-2147483647(d)后的'位模式'该是什么样子的呢？其计算方法为(~2147483647(d) + 1)，即(~0x000000007FFFFFFF + 1)，即0xFFFFFFFF80000001，这是个负数，我们要得到其真实值，还得需像上面的计算方式计算：
0xFFFFFFFF80000001 - 1(d) = 0xFFFFFFFF80000001 - 0x0000000000000001 = 0xFFFFFFFF80000000;
0xFFFFFFFF80000000逐位取反得到0x000000007FFFFFFF, 而0x000000007FFFFFFF = 2147483647(d)，所以rv = -2147483647(d)

[方案三]
我们知道上面的问题是由于在不同类型间依照'值保留'原则转型造成的，那么我们大可这么做：
int main(void) {
        long long       a;
        long long       b;
        long long       c;

        while (scanf("%lld %lld %lld", &a, &b, &c) == 3) {
                printf("%lld\n", a + b + c);
        }
        return 0;
}

在在线测试系统提交后，状态'Accepted'，至此问题解决，当然问题的解决方法可以有很多种，我想这种是最简单的方法之一了。

怎么样，其实每道ACM题的背后都会有一些'基础理论'在支撑，所以多多做ACM的练习是大有裨益的，上面的数制转换我以前也是很糊涂，就是因为在此题上的思考才让我'豁然开朗'^_^。