问题描述：

Ex9.1-1

Show that the second smallest of n elements can be found with comparisons in the worst case. (Hint: Also find the smallest element.)

证明在n个元素中找到第2小的元素在最坏情况下需要次比较。（提示：这个方法同时也能找到最小的元素）。

证明：

刚接到题目的时候并没有什么想法，因为从常规的擂台方法求最小元素的方法如果作用在第2小的元素在最坏情况下需要2n-3次比较（一开始选取两个元素比较之，随后在最坏情况下，和后面的n-2个元素都需要比较两次，即有2*(n-1)+1=2n-3）。超出了我们的要求。

但是从分析的角度来看，题目给出的结论当中存在一个lg n，这通常是二分策略的标志，而且题目后面又提示说这个方法也能够找到最小的元素，而在寻找最小元素的方法中存在二分思想的方法就是著名的竞赛树方法，如下图所示：

简单地说，我们将所有的元素两两配对，在每一对中找到较小的那个数并提取出来，然后就像淘汰赛一样，将这提取出的较小的数在两两配对，并在每一对中找到较小的数并提取出来……如此反复，当最后只剩下一个数的时候，我们就最终得到了最小的数。

这个方法的效率其实是和朴素的擂台方法效率相同的，为n-1次比较，但是它的好处是利用了二分的思想，从而在对于数组中的每一个元素，最多和个别的元素进行比较，而对于最小的元素进行比较，我们把这些数用红色的框框出：

我们可以发现在整棵树中和最小元素进行比较的元素在此之前都是该分支中最小的元素，它们是遭遇了最小的元素才“落败”的，也就是说，第2小的数一定就存在于他们之中（稍后给出详细证明），于是我们得到如下的算法：

首先，我们使用竞赛树方法得到整个竞赛树和最小的元素，注意竞赛树的保存方法，由于我们是从树叶向上逆向存储的，因此需要额外的空间保存结点的两个子女的编号。

随后，从树的根（也就是最小的元素）开始，向下遍历整个最小的元素经过的路径，观察整个路径中最小元素旁的兄弟结点（也就是在和最小元素比较中“落败”的结点）的值，找出其中最小的，即为第2小的元素。

证明算法的正确性：

初始状态：在一开始，我们从树的根开始寻找第2小的元素，最初在最小元素旁的兄弟结点是必然有的（很显然，否则为什么还要再比较一次？），而根据竞赛树的性质，竞赛树中的任意子树的根结点都是整个竞赛树中最小的元素，因此这个兄弟结点的值必然是它所在子树的最小值，然而它大于最小的值，因此在当前（根及它所在的子树），它确实是第2小的值。

保持：随着遍历过程的深入，我们不断地得到在最小元素旁的兄弟结点，它们也和先前的那个元素一样，在其所在的子树中是最小的，但大于最小的元素。而将它和当前的第2小元素进行比较，找到较小的值，我们就能得到当前树结构中的第2小的值。

结论：如此往复，当遍历到树叶时，我们得到的值就是第2小的了。

效率：

在前一部分生成竞赛树所需要的比较数为n-1，随后的遍历过程中需要的比较数取决于竞赛树的深度，由于竞赛树也满足平衡性，因此设竞赛树的深度为len，则有：

2^(len-1)<n<2^len，其中n为元素的个数，因此有，而根结点下的第一个“第2小的元素”我们不需要进行比较，因此在这个阶段我们所需要的比较数为。

综上，我们得到这个算法在最坏情况下需要的比较次数为。从而问题得到了圆满的解决。

搜索的经典，巧妙的剪枝

——pku1011解题报告

问题描述

给定n根木棒（n<=64），每根木棒的长度最大不超过50个单位长度，但长度不一，现在希望将它们合并成m根长度一样的木棒，要求在合并后得到木棒的可能的最小长度。

举例：

N=9

5 2 1 5 2 1 5 2 1

那么最小长度为6，对应（5+1），（5+1），（5+1），（2+2+2）4根。

思路与分析

第一个问题：什么算法？

问题的描述很简单，也容易理解。现在的问题就是要寻求一个合适的算法。

结合实际情况，我们想象一下人在解决这个问题时候的问题，无非就是一个反复枚举实验的过程。而且虽然本题是一个求最优解的问题，但是没有贪心策略。而由于对于一个状态其存储的信息量不足（也就是一个可达不可达的信息），又不能够有效地压缩其状态，因此使用DP并不能提高效率。同时由于问题的规模不大，因此我们最终采用搜索算法来解此题。

既然是搜索酸法，那么首先要解决的问题就是：

第二个问题：怎么搜索？

问题要求“合并后所得的木棒长度最短”，因此第一层枚举的时候肯定是从小到大枚举合并后的木棒长度，这没有什么异议。但是随后的搜索以判断该长度是否能够完成的过程却有两种不同的方法：搜索时先确定一根原木棒的位置（搜索的是原木棒应当在新合成的木棒中所在的位置，原木棒是搜索的主体），和首先合并完一个木棒后再合并下一根（搜索的是当前正在合并的木棒中应当加入的原木棒，以当前合并的木棒为搜索的主体。）这两种方法的效率相仿，但是从剪枝的角度来看两者剪枝的策略会有很大的差别，甚至有些剪枝是不能互通的，在怎么搜真个问题上我反复了几次，我会在剪枝的过程中详述。

我首先选择的方法是后者，不加剪枝的搜索策略的效率是O(n!*m) ，巨大无比，显然是超时的。所以说剪枝是必然的。

我们从简单的剪枝开始：

一些的简单剪枝。

剪枝1：首先，最明显的一个剪枝是，如果说当前所要求的木棒长度不是所有木棒总长度的约数的话那么当前所要求的木棒长度显然是不成立的。原因很明显：问题要求所有合并后的木棒长度一致，那么木棒的个数*木棒的长度的积应当等于原来木棒的总长度。

剪枝2：接下来一个剪枝还是关于枚举新的木棒长度的：所枚举的木棒长度必须要大于等于原有木棒中最长的那根木棒。其原因也很显然。

剪枝3：当然如果1/2总木棒长度都不能得到解的话就可以直接将总木棒长度作为答案了，仍然因为 问题要求所有合并后的木棒长度一致的缘故。

剪枝4：对于要拼n根木棒的情况，我们只要拼出其中的n-1根我们就能够得到解，因为有了剪枝1的保证，第四个剪枝也很容易理解：我们在开始进行搜索的时候已经保证了数据在数量上是完全合理的。严格地说这个剪枝并不强，但在有些时候确实能够起到很重要的作用。

上面的这些剪枝都是很明显的，也不需要什么特别的思考就能够想到，然而即使使用了上述剪枝，对于整个搜索的效率影响最大的一块——枚举以后的判断过程的效率仍然为O(n!)，没有下降，仍旧是一个很大的问题。

联想人在进行拼接过程中所采用的方法，我们又得到一些启示：

剪枝5：首先对于一个正在拼接的新木棒来说，如果新木棒中的空余空间小于最短的原木棒的长度，那么显然当前的这根新木棒是得不到解的。其原因显而易见。

从我个人的角度我认为，如果是我进行拼接的过程，我会首先拼接比较长的一些木棒，因为相较于比较短那些木棒来说，比较长的木棒的灵活度要小一些，先解决困难的木棒可以保证如果本长度没有解的话可以避免一些没有必要的搜索过程。

所以说，我们首先可以做的是对原有的木棒按照其长度从大到小进行排序，这样可以在一定程度上提高算法的效率。

按照这个思路联想下去，我很快发现在所有的木棒中只要有一根木棒没有办法得到安放的话整个问题就是没有解的，那么是否一根一根地拼接木棒的策略是有问题的呢？我于是改用基于原木棒的顺序搜索的策略。在这种搜索策略下，原木棒是搜索主体，我们使用一个数组对每一根要合成木棒的当前长度进行记录。在这样的情形下，我观察了一些数据：

15 11 8 8 8 4 3 2 1

结果：拼成3根长度为20的木棍：

15+3+2=20

11+8+1=20

8+8+4=20

8 8 6 4 2 2

结果：拼成3根长度为10的木棍：

8+2=10

8+2=10

6+4=10

5 5 5 2 2 2 1 1 1

结果：拼成4根长度为6的木棍：

5+1=6

5+1=6

5+1=6

2+2+2=6

我发现所有长度超过计划合成的木棒长度的一半的原木棒必须唯一地出现在一个待合并的新木棒（剪枝6）中，因此我们可以先行确定这些木棒（很明显这些木棒的总数不可能超过待合并的新木棒的总数）。

紧接着我们得出后续结论：如果某两根原木棒可以组成一个待合并的新木棒，那么我们不需要更改这两根木棒的配置（剪枝7）。我给出这样的说明：首先，这两根原木棒要么长度一致，要么其中一根的长度超过当前要拼成的木棒的长度的一半。如果对于前一种情况，我们固然可以将其中的任意一根换成两根或者更多根较短的木棒，但是很明显较多的小木棒的灵活性比单根较长的木棒的灵活性来得高，因此可以“锁定”当前木棒；对于后一种情况，显然较长的那根木棒是不能移动的（根据上一段的推理），而那根较短的木棒当然也可以换成更多的木棒拼接而成，但是同样的，单根木棒可以得到的长度组合显然没有更多根木棒能拼接的长度组合来得多，因此同样可以“锁定”当前木棒。

但是这里必须说明一点，超过三根原木棒组成的新木棒是不能“锁定”的，我们来看以下数据：

15 11 8 8 8 4 3 2 1

正确答案应该为15+3+2，11+8+1，8+8+4这三根长度为20木棒，但是如果我们对木棒按长度进行排序后搜索到的第一根长度为20的木棒却是15+4+1=20，如果当时立刻“锁定”该木棒，那么剩下的11，8，8，8，3，2，1无论如何也拼不出一根长度为20的木棒，长度为20的枚举就会失败，我们只能在长度为30的枚举中得到15+11+4=30，8+8+8+3+2+1=30这样一组数据了。而实际上长度20是能够出解的。因此并不存在“短木棒的灵活性一定比长木棒的灵活性要高”的结论。

根据数据找原因

剪枝到此，我认为效率已经得到了很大程度的提高，然而再一次尝试提交之后我得到了TLE的结果，在无法想出新的剪枝的时候我想到了去寻找一些网上的讨论，于是我得到了如下的一组“委琐”数据：

64

40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40

40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40

40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40

40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40

（一共1个43，2个42，1个41，1个10，1个4，以及58个40）

正确的解是：

43+42+42+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+4=1251

41+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+40+10=1251

我的程序超时得厉害，按照我的想法进入动态调试查看整个搜索过程以发现重复的搜索，我于是发现每一层中的58个40的元素都被反复搜索了很多次，看来问题出在这里，必须剪掉这些冗余的搜索。

歧路的剪枝，错误的搜索策略

很明显这58个40元素应当都是等价的，也就是说从当前的搜索策略（将原木棒从大到小地一个一个放入可能的新木棒容器中）角度来说如果那么就有如下的策略：对于每一根原木棒，如果其前一根木棒的长度与当前木棒的长度相等，那么本木棒就必须从前一根木棒所“落户”的新木棒起向后搜索。这是根据排列组合中的加法原理得到的，很容易理解。

我期望这个剪枝能够很好地起到剪枝的效果，可事实让我失望了，效果并不明显。

其实问题很明显，对于值的元素如果在相同的状态下（在同样的第i根原木棒，投放到第j根新木棒，此时新木棒中已有长度为k的情况下）进行的搜索所得到的结果必然是相同的，其之间应该可以互相借鉴，是否可以认为，那么投放到相同的新木棒，且新木棒的已有长度为一定的情况下使用相同的元素进行搜索的所得到的结果是一样的呢？于是我决定列一个矩阵，存储当原木棒的长度为i，投放到第j根新木棒，此时新木棒中已有长度为k的情况下的解是否存在这样一个信息，结果很让人欣慰，达到了要求，可是1<=i<=50，1<=j<=64，0<=k<=3200，50*64*3200=(3200)^2=1.024MB，然而本题的空间限制恰为1MB，超空间了，我还想尝试一些新的剪枝，可是都没有办法，解题陷入了僵局。

这时我发现论坛上成功解出本题的人使用的搜索策略都是以一个一个地试探能否组成一根新的木棒为搜索策略的（也就是说以新木棒为搜索基础，和我提出的后一种搜索策略一致）。

是不是搜索策略有问题？我于是决定尝试改变搜索思路，很快发现剪枝6其实是可以加强的，其实对于当前最长的原木棒，必须要出现在一根崭新的新木棒中（剪枝6-1），这要如何理解呢？其实前面的剪枝都是剪去一些确定必然不存在的分支，而新的剪枝6是一个固定顺序的过程，即在很多种情况都可以得到解的情况下，我们确定出一个顺序来，将一些冗余的，重复出现的枝剪掉。我们再举15 11 8 8 8 4 3 2 1这个例子，其组成的三根新木棒（15+3+2=20, 11+8+1=20, 8+8+4=20）中顺序是不重要的，其实3+15+2, 1+8+11,8+4+8这样也是可以的，但是这样一个搜索过程和原解相比较是冗余的，完全可以剪掉，而剪掉冗余枝的过程就是确定一个顺序，在这里为：我们应当首先保证比较长的原木棒能够优先得到被分割的权利。

新剪枝加上去后，效率有了一定的提高，剪枝的思路也更加清晰了，直接导致了随后的强剪枝的诞生，而这个剪枝是使用以原木棒为基础的搜索策略难以使用的。

有的时候改变搜索策略竟然是如此的有效！后来我发现前面提出的“记忆化搜索”是有漏洞的，即使剪了也难免Wrong Answer，看来这种搜索策略果然是错误的。

强剪枝

其实前面的思路没有问题：减少冗余枝的搜索，其实如果一根原木棒在投入某一根新木棒的过程中失败了，那么其相同的长度的原木棒就没有必要再投入进去，直接跳过即可（剪枝8）。但这里有一个条件必须成立：在此之前的所有新木棒的状态要填满，如果没有填满，则我们完全有可能存在可以回填的原木棒，也就是说用前一种搜索策略是得不到这样一个剪枝方法的，至少说要想到它很困难，但是在我们现在的搜索策略中很容易想到。

剪枝8的效率很高，对于上面的那组BT数据，加了剪枝8之后只用了几十ms就解决了，无疑这是一个强剪枝。本题也因此得到了解。如此看来选择搜索策略果然是很重要的。

小结

“搜索是硬道理”，在所有的问题中搜索问题完全是依靠程序员的经验和对问题的理解深度，完全凭真工夫。解搜索问题的过程中要解决两个问题：搜索策略，即搜什么的问题；剪枝策略，即哪些枝是不需要的。其中要剪枝策略可以分为两种：不能达到解的解分支和本质上相同的解分支。

非典型DP

——pku1742解题报告

问题描述

编写一个程序，读入n，m。有币值A1、A2、A3…、An的硬币，对应各有C1、C2、C3、…、Cn数量的硬币，问它们能够在1~m元中组合成多少中不同的币值？

举例：

对于输入：

3 10

1 2 4

2 1 1

即说明有2个1元硬币，1个2元硬币，1个4元硬币，求他们能够在10元中组合成多少中不同的币值。

显然能够组成1（1），2（2），3（2+1），4（4），5（4+1），6（4+2），7（4+2+1），8（4+2+1+1）8种不同的币值，于是输出为8。

再举一例：

2 5

1 4

2 1

即说明有2个1元硬币， 1个4元硬币，求他们能够在5元中组合成多少中不同的币值。

能够组成1（1），2（1+1），4（4），5（4+1），6（4+1+1）5种不同的币值，但是6这个值超过了限定，于是输出为5。

思考与分析

第一个算法

1<=m<=100000，即使使用4个字节来表示，4*100000=391K，从空间的角度来说是完全没有问题的，因此我们完全可以用一个一元数组f[i]来表示使用题目提供的硬币能否组合成i元。对于第i种币值的第j枚硬币（即每一枚硬币），我们遍历整个f数组，标记所有可能到达的点，用动态转移方程来描述的话，就是下面的样子：

，其中保证初态

在问题的最后，我们只需要再遍历一次f数组，累计所有从1~m范围中f[i]值为1的元素的个数作为最后的答案就可以了。需要注意的是顺序，由于在同一个数组中进行操作，如果我们从低到高地遍历整个数组的话，会出现一枚硬币重复计算的情况（例如前面所举的例2，如果我们从低到高地遍历整个数组的话，会在第一个循环中就将F数组的所有元素的值均置为1），这在很大程度上是由于初态F[0]为1的缘故，也就是说，很明显地我们可以感觉到1这个信号是由低到高地“蔓延”的，硬币重复计算的原因是因为我们在向后拓展1的时候使用到了本次生成的1，因此我们使用从高向低地遍历就可以解决这个问题。

整个问题的时间复杂度为O（n*m*Max（Ci））。提交以后，结果为TLE。

优化

从经验来看n*m*Max(Ci)=O(100*100000*1000)=O（10^10），确实超时了，然而其实差距并不是特别的大，但是从状态的角度来看，哪些状态是可以压缩的呢？

压缩n很困难，因为原则上来说，这组数据有其下属的数据（即硬币的面值及个数），压缩的话会丢失数据。

那么压缩m和Ci那个容易呢？m的数据也很困难，毕竟从先前的朴素算法来看，这是一种类似于动态规划的算法，或者说这就是DP，只不过并不是一个很典型的DP而已（因为状态的类似于打表，也不同于一般的DP最后的答案往往是递推的终点）。既然是DP的话就要保证整个递推的过程的无后效性，而且由于我们DP最后的答案需要用到所有的状态，如果我们压缩m的话，我们如何保证信息的完整性？要保证信息的完整性，以及让m的数据能够顺利地完成递推是困难的。

于是主要的能够压缩的地方就集中在了Max（Ci）上，确实这里存在冗余，因为对于Ci中的每一个数字，我们都要将m个数遍历一遍，这很浪费，也不值得，完全可以压缩。

如何压缩呢？仔细观察整个1“蔓延”的过程你会发现，如果去除掉ci的限制，问题就变成了一个类似于的背包问题的问题，而的ci就是加在各个硬币上的一个限制而已，其实我们不妨换一个思路，为什么要先确定它的限制呢？——逆向思维之——我们完全可以不用先确定它的限制，而在要标记这个结点的时候对其使用了多少个当前币值的硬币进行记录，并对其进行判断，如果我们要构成当前币值已经超过了最大的当前币值硬币限制数，我们就舍弃这个答案，于是乎，一个新的动态转移方程就这样产生了：

其中prev[k]表示当得到值k的时候已经使用了多少当前币值的硬币。每当有一个新的F[k]置为1，则有prev[k]=prev[k-A[i]] + 1，并保证prev[0]=0。

F[k]的值可以从1开始由低向高遍历，因为已经有一个额外的数组prev[k]记录限制了。

这样的话在实际进行搜索的过程中我们就可以省去一维，从而似的整个问题的时间复杂度降为O(n*m)，效率提高了不少。

小结

1. 提高动态规划效率的方法最主要的是压缩状态，而增加维数在很多时候被认为是在状态方程无法列出的时候用于建模时才使用的技巧，可是在解本题的过程中，我们通过增加记录的东西，用空间换时间，成功地提高了效率。也验证了动态规划是记忆化的搜索这样一种说法。

2. 动态规划并不是一门单一的算法，把动态规划算法严格地定义成递推式DP和递归式DP会影响到DP的灵活性。其实DP应当是一种思想，本题在解题的过程中掺杂了一定的Ad Hoc成分，但究其本质仍然是DP，只不过不是很明显而已。虽然有经典DP存在，但是没有典型DP存在，DP本身就是非典型的。

一个小时的思考，5分钟的编程

——pku1063解题报告

问题描述

这个迷题首先给出了一个由m个黑盘子和n个白盘子组成椭圆形的轨道，轨道中有一个能够滑动的十字转门（也就是说能够翻转），这个十字转门能容纳3个连续的盘子。在图一中，轨道上有8个黑色的盘子和10个白色的盘子。你可以旋转十字转门来翻转其中的三个盘子或者将十字转门在轨道上滑动一格。

这个迷题的目标是为了形成如下图所示的盘子的布局形式：

你被要求写一个程序来确定对于一个给定的序列能否达到目标。如果目标是可以到达的，输出“YES”，否则，输出“NO”。

思考与分析

本题乍一看来似乎难以下手，但是向来迷题类的问题往往都能够转化成一个数学问题。我们需要对模型进行建模。

建模过程

观察整个问题后我们发现，整个轨道组成一个环，也就是说不存在端点，也就不一定要求整个轨道的最后状态一定要什么黑盘在左，白盘在右，其实问题只是要求黑盘和白盘分别“聚集”在一起就可以了，不一定一定要存在一个端点，而且由于所谓的“十字转门”是可以滑动的，这就是说我可以任意地“翻转”序列中任意的三个连续的元素。或者说，我可以将一个元素向前跳一格或者向后跳一格（隔一个元素）。而游戏的目的是要黑盘和白盘分置在序列的两侧（当然序列是循环的，我们这里这样做是为了方便后面的描述）。

这样，问题就转化为，给定一个序列，序列中有两种不同的元素，元素可以每隔一个元素向前（后）跳转，问我能否将两种不同的元素分置于两侧。

探测解法

其实在模型建立之前我就开始进行一些小数据的测试（比如最少要3个数字，010），为的是使模型更加清晰，现在我继续进行一些小数据的测试，以期找到解法：

实际过程中，我探测了以下的数据：

0101 无解，无法达成0011

01001 有解，将2位和4位交换即可

010101 无解

001101 有解，将3位和5位交换即可

1010101 有解，解法：

1010101=>（1位和6位交换）

0010111=>（6位和4位交换）

0011101=>（3位和1位交换）

1001101=>（1位和6位交换）

0001111

似乎只要序列的长度奇数的就一定有解？

对于这类的问题很多时候都可以归结到一个同余问题上来（一个经典的例子就是01年浙江省选的“青蛙的约会”），但是同余我并不熟悉，怎么办呢？

其实，从问题的规模和迷题的复杂性来看，这题的长度不会很长，查看网上的discuss中很多人也提到了通过奇偶性来判断有解。那么是不是就此展开分析呢？

思路分析

其实我探察的最后一个数据已经给出了大致的解迷题的思路——尽量地向一个方向靠拢，我们已经了解到迷题是否有解似乎与长度的奇偶性有关，那么我们是不是在这上面做一点文章呢？

如果涉及到奇偶性的问题往往有两种原因：1、问题本身存在两种状态，两种状态是互相不可达的（经典例子有八数码问题）；2、奇偶性可能会使得有些状态不可达。

首先我们观察一个偶数数列（如n=6）：

123456

我们发现，如果我从1出发，向前后跳转，我就只能够到达1、3、5这三个位置，也就是说在奇数位上出现的数字永远也不可能到偶数位上，由于我们所要的最终结果是要黑色（白色也是同样的）连续的出现，因此黑色（白色）中奇数和偶数的个数就要相等，最多奇数比偶数多一个或者偶数比奇数多一个。对于一个长度为偶数的数列，由于相同颜色的盘子所在位置的奇偶性是不可改变的，于是初始状态时的位置排列就决定了解的可能性。而对于一个奇数长度的数列（如n=7）：

1234567

从任何一个位置出发都可以到达所有的位置，因此从这个方面看来，确实没有无解的情况。其实也一定可以保证有解，对于偶数数列的情况，相当于两个不同的数列，每个数列中的元素都可以与相邻的数据做交换，如n=6就形成了数列135和246，这样必然能够产生所有的排列；对于奇数数列的情况，不失一般性，我们使用n=5时的例子，如：

12345

我要交换3和4之间的位置，同时不影响别的数据，可以这样完成：

12345=>

14325=>

15324=>

15432=>

12435=>

此例同样适应于更大的数据，可以使用数学归纳法证明，显然可得。

结论

整个结果与数列的长度和布局有关，当数列长度为奇数时，一定有解，为偶数时，如果说对于某个颜色的盘子（如黑色），其在奇数位置上的盘子的个数与在偶数位置上的盘子的个数相差的绝对值小于等于1时，有解，反之则无解。

代码

非常简单的一个判断过程，代码略。

小结

总共花了一个小时来思考整个解题的过程，其实在最终写报告之前仍然是有一些部分是我不能理解的，整个解题的编码过程十分简单，而思考及数学推理的过程却很长，这从一个侧面证明了在很多程序设计的过程中，代码的工作量其实只是很小的一部分，更大的部分在思考和数学推理上。

“语言是工具”
    ——上海交通大学 王成
人与人交流，依靠的是自然语言。
人与计算机交流，依靠的仍旧是语言.
因此不管C语言再如何地成功，它终究还是一门语言而已，语言是工具，因此我们学任何一门计算机语言的时候都不要拘泥于语言本身，这就是我想阐述的观点。
是的，几乎所有的老师在教授C语言的时候都会强调“语言是基础”这一个观点，其实从我的角度来看，这其实说的并非是C语言本身，很多学校都把这门课叫做“结构化程序设计”，因此其实这里的“基础”应当指的是结构化程序设计思想，这的确是作为计算机系学生最为基础的——这门课要教给大家的，其实就是如何用计算机的方法来思考、解决问题。
也就是说学习C语言的重点应当是在程序设计思想的方面，比如说学习三大结构（顺序、选择、循环），就不应当仅仅局限于这三个结构的形式以及C语言语法上，既然dijkstra说通过这三大结构可以实现所有的程序，那么我们不妨去问问为什么？不使用三大结构来写程序会有什么问题？等等，这样学习C语言才是有意义的，当然对于刚接触计算机的同学来说恐怕要求太高了一点，但我觉得只有做到了这一点才称得上是学好了这门课。
我在中学时期曾经接触过Pascal语言，从计算机程序设计语言的分类上来说它和C语言是“同源”的（共同起源于Ada语言）。因此对于我来说学习C语言的语法并算不上是什么困难的事情，只有指针的概念让人颇为头疼了一下，现在想起来指针仍旧是一个让人感到颇为玄妙的东西——C语言结合了高级语言和汇编语言的特征，结构化程序设计体现了高级语言的特征，指针则是C语言从汇编语言中借鉴的特征。应该说这两个概念同样重要，也同样的难，但为什么几乎所有的同学都不会对结构化程序设计的学习产生疑问感呢？而三大程序设计结构中的概念在我们的日常生活中能够见到，在我们没有接触C语言之前就已经对这些概念有了一定的认识。但是对于没有深入接触过计算机的人来说，所谓指向“内存的指针”这样一种概念显然是抽象而模糊的，也就是说要解决指针的概念关键是需要让它“具体”起来，一个有效的方法是画图——不过首先要理解内存中的存储单元的概念。很有帮助的。当然这只是指简单的指针概念，其实C指针的内容还有很多，但是其中更多要涉及到操作系统和计算机组成原理方面的知识，我不认为既然我们是在学习程序设计语言，就应当更加专注于程序设计方法和设计思想这一块——大学中更多的要学习的还是思想，而不是技术，过早的专注于指针的理解和研究其实和研究语法本身一样，拘泥与C语言本身了，如果要想了解C语言是如何实现指针的，又需要有更多背景知识……有些困难，大一的时候还有许多公共课，给C语言牵扯了太多的精力并不合适。

手札是什么东西？在我的理解当中可以简单地认为是笔记，或者某某人曾经大肆宣扬的所谓“回忆笔记”。即把对于某门课程的个人经验和理解用笔的方式写出来，同时添加上自己的理解。这被认为是非常有效的一种复习手段，我也这么认为。
取名字叫枫叶则是自己的象征，就好像很多人问我为什么要把网名起成叫xish这样一个不伦不类有带给人一点莫名其妙遐想的名字一样。其实没有什么特别的道理，完全是因为自己的感觉，呵呵，一种感觉而已。
一直以来都在想写这样一个东西，可是一来呢没有足够的资历，而来呢也抽不出足够的时间来写，那么为什么会选在这么一个没有任何意义的时间些这个东西呢？
心血来潮了，同时也不愿意看到自己的Blog就这样荒废下去……
在尽可能忠实地整理自己大学至今所有的专业课笔记的同时我也会有一些别的东西，比方说某些短评出现，总之也可以把手札理解成是简单的随笔，就像写Blog一样。
先给个预告，接下来的第一篇是关于C语言的。