// 剩余部分依次置入中间数组 // 将中间数组的内容拷贝回原数组 * 将中间数组bridge中的内容拷贝到原数组中 * 要拷贝的第一个元素的下标 * 要拷贝的最后一个元素的下标

Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。

如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。

事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：2⁶⁴- 1 = 为5.82e+16年，也就是约5000世纪，如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 

Fibonacci为1200年代的欧洲数学家，在他的著作中曾经提到：“若有一只免子每个月生一只小免子，一个月后小免子也开始生产。起初只有一只免子，一个月后就有两只免子，二个月后有三只免子，三个月后有五只免子（小免子投入生产）......”。

如果不太理解这个例子的话，举个图就知道了，注意新生的小免子需一个月成长期才会投入生产，类似的道理也可以用于植物的生长，这就是Fibonacci数列，一般习惯称之为费氏数列，例如以下：

依说明，我们可以将费氏数列定义为以下：

（3）巴斯卡（Pascal）三角形

巴斯卡（Pascal）三角形基本上就是在解 nCr ，因为三角形上的每一个数字各对应一个nCr，其中 n 为 row，而 r 为 column，如下：

对应的数据如下图所示：

巴斯卡三角形中的 nCr 可以使用以下这个公式来计算，以避免阶乘运算时的数值溢位：

（4）蒙地卡罗法求 PI

蒙地卡罗为摩洛哥王国之首都，该国位于法国与义大利国境，以赌博闻名。蒙地卡罗的基本原理为以乱数配合面积公式来进行解题，这种以机率来解题的方式带有赌博的意味，虽然在精确度上有所疑虑，但其解题的思考方向却是个值得学习的方式。

蒙地卡罗的解法适用于与面积有关的题目，例如求PI值或椭圆面积，这边介绍如何求PI值；假设有一个圆半径为1，所以四分之一圆面积就为PI，而包括此四分之一圆的正方形面积就为1，如下图所示：

如果随意的在正方形中投射飞标（点）好了，则这些飞标（点）有些会落于四分之一圆内，假设所投射的飞标（点）有n点，在圆内的飞标（点）有c点，则依比例来算，就会得到上图中最后的公式。

至于如何判断所产生的点落于圆内，很简单，令乱数产生X与Y两个数值，如果X^2+Y^2等于1就是落在圆内。

（5）最大公因数、最小公倍数

最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：

Armstrong数的寻找，其实就是在问如何将一个数字分解为个位数、十位数、百位数......，这只要使用除法与余数运算就可以了，例如输入 input为abc，则：

现将举行一个餐会，让访客事先填写到达时间与离开时间，为了掌握座位的数目，必须先估计不同时间的最大访客数。

这个题目看似有些复杂，其实相当简单，单就计算访客数这个目的，同时考虑同一访客的来访时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了，假设访客 i 的来访时间为x[i]，而离开时间为y[i]。

在资料输入完毕之后，将x[i]与y[i]分别进行排序（由小到大），道理很简单，只要先计算某时之前总共来访了多少访客，然后再减去某时之前的离开访客，就可以轻易的解出这个问题

（8）洗扑克牌（乱数排列）

洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如1～N）打乱重新排列，只不过洗扑克牌多了一个花色判断的动作而已。

初学者通常会直接想到，随机产生1～N的乱数并将之存入阵列中，后来产生的乱数存入阵列前必须先检查阵列中是否已有重复的数字，如果有这个数就不存入，再重新产生下一个数，运气不好的话，重复的次数就会很多，程式的执行速度就很慢了，这不是一个好方法。

以1～52的乱数排列为例好了，可以将阵列先依序由1到52填入，然后使用一个回圈走访阵列，并随机产生1～52的乱数，将产生的乱数当作索引取出阵列值，并与目前阵列走访到的值相交换，如此就不用担心乱数重复的问题了，阵列走访完毕后，所有的数字也就重新排列了。

至于如何判断花色？这只是除法的问题而已，取商数判断花色，取余数判断数字，您可以直接看程式比较清楚。

据说着名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示：

使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列，41个人而报数3的约琴夫排列如下所示：

由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

将一组数字、字母或符号进行排列，以得到不同的组合顺序，例如1 2 3这三个数的排列组合有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。

可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为1 [2 3 4]、2 [1 3 4]、3 [1 2 4]、4 [1 2 3]进行排列，这边利用旋转法，先将旋转间隔设为0，将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如：

假设有一教师依学生座号输入考试分数，现希望在输入完毕后自动显示学生分数的排行，当然学生的分数可能相同。

这个问题基本上要解不难，只要使用额外的一个排行阵列走访分数阵列就可以了，直接使用下面的程式片段作说明：

上面这个方法虽然简单，但是反覆计算的次数是n^2，如果n值变大，那么运算的时间就会拖长；改变juni阵列的长度为n+2，并将初始值设定为0，如下所示：

接下来走访分数阵列，并在分数所对应的排行阵列索引元素上加1，如下所示：

将排行阵列最右边的元素设定为1，然后依序将右边的元素值加至左边一个元素，最后排行阵列中的「分数+1」」就是得该分数的排行，如下所示：

这样的方式看起来复杂，其实不过在计算某分数之前排行的人数，假设89分之前的排行人数为x人，则89分自然就是x+1了，这也是为什么排行阵列最右边要设定为1的原因；如果89分有y人，则88分自然就是x+y+1，整个阵列右边元素向左加的原因正是如此。

如果分数有负分的情况，由于C/C++或Java等程式语言无法处理负的索引，所以必须加上一个偏移值，将所有的分数先往右偏移一个范围即可，最后显示的时候记得减回偏移值就可以了。

（12）选择、插入、气泡排序

选择排序（Selection sort）、插入排序（Insertion sort）与气泡排序（Bubble sort）这三个排序方式是初学排序所必须知道的三个基本排序方式，它们由于速度不快而不实用（平均与最快的时间复杂度都是O(n2)），然而它们排序的方式确是值得观察与探讨的。

将要排序的对象分作两部份，一个是已排序的，一个是未排序的，从后端未排序部份选择一个最小值，并放入前端已排序部份的最后一个，例如：

像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置，例如：

顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法，将大的元素交换至右端，所以大的元素会不断的往右移动，直到适当的位置为止。

基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生任何的交换动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作，例如：

在上面的例子当中，还加入了一个观念，就是当进行至i与i+1时没有交换的动作，表示接下来的i+2至n已经排序完毕，这也增进了气泡排序的效率。

（13）快速排序（一）

快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n²)，但是在多数的情况下，快速排序法的效率表现是相当不错的。

快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。

这边所介绍的第一个快速排序法版本，是在多数的教科书上所提及的版本，因为它最容易理解，也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解。

这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为 s

令索引 i 从数列左方往右方找，直到找到大于 s 的数

令索引 j 从数列左右方往左方找，直到找到小于 s 的数

如果 i < j，则交换索引i与j两处的值

将左侧的轴与 j 进行交换

透过以下演算法，则轴左边的值都会小于s，轴右边的值都会大于s，如此再对轴左右两边进行递回，就可以对完成排序的目的，例如下面的实例，*表示要交换的数，[]表示轴：

在上面的例子中，41左边的值都比它小，而右边的值都比它大，如此左右再进行递回至排序完成。

（14）快速排序（二）

在快速排序法（一）中，每次将最左边的元素设为轴，而之前曾经说过，快速排序法的加速在于轴的选择，在这个例子中，只将轴设定为中间的元素，依这个元素作基准进行比较，这可以增加快速排序法的效率。

在这个例子中，取中间的元素s作比较，同样的先得右找比s大的索引 i，然后找比s小的索引 j，只要两边的索引还没有交会，就交换 i 与 j 的元素值，这次不用再进行轴的交换了，因为在寻找交换的过程中，轴位置的元素也会参与交换的动作，例如：

首先left为0，right为9，(left+right)/2 = 4（取整数的商），所以轴为索引4的位置，比较的元素是45，您往右找比45大的，往左找比45小的进行交换：

完成以上之后，再初别对左边括号与右边括号的部份进行递回，如此就可以完成排序的目的。

（15）快速排序（三）

之前说过轴的选择是快速排序法的效率关键之一，在这边的快速排序法的轴选择方式更加快了快速排序法的效率，它是来自演算法名书 Introduction to Algorithms 之中。

先说明这个快速排序法的概念，它以最右边的值s作比较的标准，将整个数列分为三个部份，一个是小于s的部份，一个是大于s的部份，一个是未处理的部份，如下所示 ：

在排序的过程中，i 与 j 都会不断的往右进行比较与交换，最后数列会变为以下的状态：

然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：

整个演算的过程，直接摘录书中的虚拟码来作说明：

之前所介绍的排序法都是在同一个阵列中的排序，考虑今日有两笔或两笔以上的资料，它可能是不同阵列中的资料，或是不同档案中的资料，如何为它们进行排序？

可以使用合并排序法，合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。

有人问道，如果两笔资料本身就无排序顺序，何不将所有的资料读入，再一次进行排序？排序的精神是尽量利用资料已排序的部份，来加快排序的效率，小笔资料的排序较为快速，如果小笔资料排序完成之后，再合并处理时，因为两笔资料都有排序了，所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率。

那么可不可以直接使用合并排序法本身来处理整个排序的动作？而不动用到其它的排序方式？答案是肯定的，只要将所有的数字不断的分为两个等分，直到最后剩一个数字为止，然后再反过来不断的合并，就如下图所示：

不过基本上分割又会花去额外的时间，不如使用其它较好的排序法来排序小笔资料，再使用合并排序来的有效率。

在之前所介绍过的排序方法，都是属于「比较性」的排序法，也就是每次排序时 ，都是比较整个键值的大小以进行排序。

这边所要介绍的「基数排序法」（radix sort）则是属于「分配式排序」（distribution sort），基数排序法又称「桶子法」（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些「桶」中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

以LSD为例，假设原来有一串数值如下所示：

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

接着再进行一次分配，这次是根据十位数来分配：

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演 算方式则都相同。

（18）循序查找法（使用卫兵）

搜寻的目的，是在「已排序的资料」中寻找指定的资料，而当中循序搜寻是最基本的搜寻法，只要从资料开头寻找到最后，看看是否找到资料即可。

    初学者看到循序搜寻，多数都会使用以下的方式来进行搜寻：

这个方法基本上没有错，但是可以加以改善，可以利用设定卫兵的方式，省去if判断式，卫兵通常设定在数列最后或是最前方，假设设定在列前方好了（索引0的 位置），我们从数列后方向前找，如果找到指定的资料时，其索引值不是0，表示在数列走访完之前就找到了，在程式的撰写上，只要使用一个while回圈就可 以了。

如果搜寻的数列已经有排序，应该尽量利用它们已排序的特性，以减少搜寻比对的次数，这是搜寻的基本原则，二分搜寻法是这个基本原则的代表。

    在二分搜寻法中，从数列的中间开始搜寻，如果这个数小于我们所搜寻的数，由于数列已排序，则该数左边的数一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻的数大于所搜寻的对象，则右边的数无需再搜寻，直接搜寻左边的数。

所以在二分搜寻法中，将数列不断的分为两个部份，每次从分割的部份中取中间数比对，例如要搜寻92于以下的数列，首先中间数索引为(0+9)/2 = 4（索引由0开始）：

由于67小于92，所以转搜寻右边的数列：

由于90小于92，再搜寻右边的数列，这次就找到所要的数了：

如果却搜寻的资料分布平均的话，可以使用插补（Interpolation）搜寻法来进行搜寻，在搜寻的对象大于500时，插补搜寻法会比 二分搜寻法 来的快速。

插补搜寻法是以资料分布的近似直线来作比例运算，以求出中间的索引并进行资料比对，如果取出的值小于要寻找的值，则提高下界，如果取出的值大于要寻找的值，则降低下界，如此不断的减少搜寻的范围，所以其本原则与二分搜寻法是相同的，至于中间值的寻找是透过比例运算，如下所示，其中K是指定要寻找的对象， 而m则是可能的索引值：

二分搜寻法每次搜寻时，都会将搜寻区间分为一半，所以其搜寻时间为O(log(2)n)，log(2)表示以2为底的log值，这边要介绍的费氏搜寻，其利用费氏数列作为间隔来搜寻下一个数，所以区间收敛的速度更快，搜寻时间为O(logn)。

    费氏搜寻使用费氏数列来决定下一个数的搜寻位置，所以必须先制作费氏数列，这在之前有提过；费氏搜寻会先透过公式计算求出第一个要搜寻数的位置，以及其代表的费氏数，以搜寻对象10个数字来说，第一个费氏数经计算后一定是F5，而第一个要搜寻的位置有两个可能，例如若在下面的数列搜寻的话（为了计算方便， 通常会将索引0订作无限小的数，而数列由索引1开始）：

如果要搜寻5的话，则由索引F5 = 5开始搜寻，接下来如果数列中的数小于指定搜寻值时，就往左找，大于时就向右，每次找的间隔是F4、F3、F2来寻找，当费氏数为0时还没找到，就表示寻找失败，如下所示：

由于第一个搜寻值索引F5 = 5处的值小于19，所以此时必须对齐数列右方，也就是将第一个搜寻值的索引改为F5+2 = 7，然后如同上述的方式进行搜寻，如下所示：

至于第一个搜寻值是如何找到的？我们可以由以下这个公式来求得，其中n为搜寻对象的个数：

也就是说Fx必须找到不大于n的费氏数，以10个搜寻对象来说：

如果数列number在索引5处的值小于指定的搜寻值，则第一个搜寻位置就是索引5的位置，如果大于指定的搜寻值，则第一个搜寻位置必须加上m，也就是F₅ + m = 5 + 2 = 7，也就是索引7的位置，其实加上m的原因，是为了要让下一个搜寻值刚好是数列的最后一个位置。

费氏搜寻看来难懂，但只要掌握F_x + m = n这个公式，自己找几个实例算一次，很容易就可以理解；费氏搜寻除了收敛快速之外，由于其本身只会使用到加法与减法，在运算上也可以加快。

    如果在矩阵中，多数的元素并没有资料，称此矩阵为稀疏矩阵（sparse matrix），由于矩阵在程式中常使用二维阵列表示，二维阵列的大小与使用的记忆体空间成正比，如果多数的元素没有资料，则会造成记忆体空间的浪费，为 此，必须设计稀疏矩阵的阵列储存方式，利用较少的记忆体空间储存完整的矩阵资讯。

在这边所介绍的方法较为简单，阵列只储存矩阵的行数、列数与有资料的索引位置及其值，在需要使用矩阵资料时，再透过程式运算加以还原，例如若矩阵资料如下，其中0表示矩阵中该位置没有资料：

这个矩阵是5X6矩阵，非零元素有4个，您要使用的阵列第一列记录其列数、行数与非零元素个数：

阵列的第二列起，记录其位置的列索引、行索引与储存值：

所以原本要用30个元素储存的矩阵资讯，现在只使用了15个元素来储存，节省了不少记忆体的使用。

（23）多维矩阵转一维矩阵

    有的时候，为了运算方便或资料储存的空间问题，使用一维阵列会比二维或多维阵列来得方便，例如上三角矩阵、下三角矩阵或对角矩阵，使用一维阵列会比使用二维阵列来得节省空间。

以二维阵列转一维阵列为例，索引值由0开始，在由二维阵列转一维阵列时，我们有两种方式：「以列（Row）为主」或「以行（Column）为主」。由于 C/C++、Java等的记忆体配置方式都是以列为主，所以您可能会比较熟悉前者（Fortran的记忆体配置方式是以行为主）。

以列为主的二维阵列要转为一维阵列时，是将二维阵列由上往下一列一列读入一维阵列，此时索引的对应公式如下所示，其中row与column是二维阵列索引，loc表示对应的一维阵列索引：

以行为主的二维阵列要转为一维阵列时，是将二维阵列由左往右一行一行读入一维阵列，此时索引的对应公式如下所示：

公式的推导您画图看看就知道了，如果是三维阵列，则公式如下所示，其中i（个数u1）、j（个数u2）、k（个数u3）分别表示三维阵列的三个索引：

    更高维度的可以自行依此类推，但通常更高维度的建议使用其它资料结构（例如物件包装）会比较具体，也不易搞错。

（24）上三角、下三角、对称矩阵

下三角矩阵是矩阵在对角线以上的元素均为0，即A_ij = 0，i < j，例如：

对称矩阵是矩阵元素对称于对角线，例如：

上三角或下三角矩阵也有大部份的元素不储存值（为0），我们可以将它们使用一维阵列来储存以节省储存空间，而对称矩阵因为对称于对角线，所以可以视为上三角或下三角矩阵来储存。

假设矩阵为nxn，为了计算方便，我们让阵列索引由1开始，上三角矩阵化为一维阵列，若以列为主，其公式为：loc = n*(i-1) - i*(i-1)/2 + j

下三角矩阵化为一维阵列，若以列为主，其公式为：loc = i*(i-1)/2 + j

    将1到n(为奇数)的数字排列在nxn的方阵上，且各行、各列与各对角线的和必须相同，如下所示：

    填魔术方阵的方法以奇数最为简单，第一个数字放在第一行第一列的正中央，然后向右(左)上填，如果右(左)上已有数字，则向下填，如下图所示：

一般程式语言的阵列索引多由0开始，为了计算方便，我们利用索引1到n的部份，而在计算是向右(左)上或向下时，我们可以将索引值除以n值，如果得到余数为1就向下，否则就往右(左)上，原理很简单，看看是不是已经在同一列上绕一圈就对了。

    与  相同，在于求各行、各列与各对角线的和相等，而这次方阵的维度是4的倍数。

简单的说，就是一个从左上由1依序开始填，但遇对角线不填，另一个由左上由16开始填，但只填在对角线，再将两个合起来就是解答了；如果N大于2，则以 4X4为单位画对角线：

至于对角线的位置该如何判断，有两个公式，有兴趣的可以画图印证看看，如下所示：

    方阵的维度整体来看是偶数，但是其实是一个奇数乘以一个偶数，例如6X6，其中6=2X3，我们也称这种方阵与单偶数方阵。

    如果您会解奇数魔术方阵，要解这种方阵也就不难理解，首先我们令n=2(2m+1)，并将整个方阵看作是数个奇数方阵的组合，如下所示：

首先依序将A、B、C、D四个位置，依奇数方阵的规则填入数字，填完之后，方阵中各行的和就相同了，但列与对角线则否，此时必须在A-D与C- B之间，作一些对应的调换，规则如下：

将A中每一列(中间列除外)的头m个元素，与D中对应位置的元素调换。

将A的中央列、中央那一格向左取m格，并与D中对应位置对调

将C中每一列的倒数m-1个元素，与B中对应的元素对调

举个实例来说，如何填6X6方阵，我们首先将之分解为奇数方阵，并填入数字，如下所示：

接下来进行互换的动作，互换的元素以不同颜色标示，如下：