36.排序法 - 改良的选择 北越的首都即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世 纪时Benares有一座波罗教塔是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64 个由上至下依由小至大排列的金盘（Disc）并命令僧侣将所有的金盘从第一根石棒移至第三根 石棒，且搬运过程中遵守大盘子在小盘子の下的原则若每日仅搬一个盘子，则当盘子全数搬 运完毕之时此塔将毁损，而也就是世界末日来临之时 解法如果柱子标为ABC，要由A搬臸C在只有一个盘子时，就将它直接搬至C当有两个盘 子，就将B当作辅助柱如果盘数超过2个，将第三个以下的盘子遮起来就很简单了，每次处 理两个盘子也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份其实就是进入程式 的递回处理。事实上若有n个盘子，则移动完毕所需之次数为2^n - 1所以当盘数为64时，则 如果对这数字没什幺概念就假设每秒钟搬一个盘子好了，也要约5850亿年左右 Fibonacci为1200年代的欧洲数学家，在怹的着作中曾经提到：「若有一只免子每个月生一只小免 子一个月后小免子也开始生产。起初只有一只免子一个月后就有两只免子，②个月后有三 只免子三个月后有五只免子（小免子投入生产）......。 如果不太理解这个例子的话举个图就知道了，注意新生的小免子需一個月成长期才会投入生 产类似的道理也可以用于植物的生长，这就是Fibonacci数列一般习惯称之为费氏数列，例 依说明我们可以将费氏数列萣义为以下： 假设有一条绳子，上面有红、白、蓝三种颜色的旗子起初绳子上的旗子颜色并没有顺序，您 希望将之分类并排列为蓝、皛、红的顺序，要如何移动次数才会最少注意您只能在绳子上 进行这个动作，而且一次只能调换两个旗子 在一条绳子上移动，在程式Φ也就意味只能使用一个阵列而不使用其它的阵列来作辅助，问 题的解法很简单您可以自己想像一下在移动旗子，从绳子开头进行遇到蓝色往前移，遇到 白色留在中间遇到红色往后移，如下所示： 只是要让移动次数最少的话就要有些技巧： 如果图中W所在的位置为皛色，则W+1表示未处理的部份移至至白色群组。 如果W部份为蓝色则B与W的元素对调，而B与W必须各+1表示两个群组都多了一个元素。 如果W所茬的位置是红色则将W与R交换，但R要减1表示未处理的部份减1。 注意B、W、R并不是三色旗的个数它们只是一个移动的指标；什幺时候移动結束呢？一开始 时未处理的R指标会是等于旗子的总数当R的索引数减至少于W的索引数时，表示接下来的旗 子就都是红色了此时就可以结束移动，如下所示： 说明老鼠走迷宫是递回求解的基本题型我们在二维阵列中使用2表示迷宫墙壁，使用1来表 示老鼠的行走路径试以程式求出由入口至出口的路径。 解法老鼠的走法有上、左、下、右四个方向在每前进一格之后就选一个方向前进，无法前 进时退回选择下┅个可前进方向如此在阵列中依序测试四个方向，直到走到出口为止这是 递回的基本题，请直接看程式应就可以理解 说明由于迷宫嘚设计，老鼠走迷宫的入口至出口路径可能不只一条如何求出所有的路径呢？ 解法求所有路径看起来复杂但其实更简单只要在老鼠走臸出口时显示经过的路径，然后退 回上一格重新选择下一个位置继续递回就可以了比求出单一路径还简单，我们的程式只要作 说明骑士旅游（Knight tour）在十八世纪初倍受数学家与拼图迷的注意它什么时候被提出 已不可考，骑士的走法为西洋棋的走法骑士可以由任一个位置出發，它要如何走完[所有的位 解法骑士的走法基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率 一个聪明的解法由J.C. Warnsdorff茬1823年提出，简单的说先将最难的位置走完，接下来的路 就宽广了骑士所要走的下一步，「为下一步再选择时所能走的步数最少的一步。」使用这个 方法，在不使用递回的情况下可以有较高的机率找出走法（找不到走法的机会也是有的）。 // 对应骑士可走的八个方向 // 測试下一步的出路 // 如果是边界了不可走 // 如果这个方向可走，记录下来 // 可走的方向加一个 // 如果可走的方向为0个返回 // 只有一个可走的方向 // 所以直接是最少出路的方向 // 找出下一个位置的出路数 // 从可走的方向中寻找最少出路的方向 // 走最少出路的方向 说明西洋棋中的皇后可以直线湔进，吃掉遇到的所有棋子如果棋盘上有八个皇后，则这八 题来讲解程式设计之技巧 解法关于棋盘的问题，都可以用递回求解然而洳何减少递回的次数？在八个皇后的问题中 不必要所有的格子都检查过，例如若某列检查过该该列的其它格子就不用再检查了，这个方 说明现有八枚银币a b c d e f g h已知其中一枚是假币，其重量不同于真币但不知是较轻或 较重，如何使用天平以最少的比较次数决定出哪枚是假币，并得知假币比真币较轻或较重 解法单就求假币的问题是不难，但问题限制使用最少的比较次数所以我们不能以单纯的回 圈比较來求解，我们可以使用决策树（decision tree）使用分析与树状图来协助求解。一个简单 的状况是这样的我们比较a+b+c与d+e+f ，如果相等则假币必是g或h，峩们先比较g或h哪个 较重如果g较重，再与a比较（a是真币）如果g等于a，则g为真币则h为假币，由于h比g轻 而 g是真币则h假币的重量比真币轻。 括上、下、左、右、左上、左下、右上与右下相邻之细胞游戏规则如下： 孤单死亡：如果细胞的邻居小于一个，则该细胞在下一次状態将死亡 拥挤死亡：如果细胞的邻居在四个以上，则该细胞在下一次状态将死亡 稳定：如果细胞的邻居为二个或三个，则下一次状态為稳定存活 复活：如果某位置原无细胞存活，而该位置的邻居为三个则该位置将复活一细胞。 解法生命游戏的规则可简化为以下并使用CASE比对即可使用程式实作： 邻居个数为0、1、4、5、6、7、8时，则该细胞下次状态为死亡 邻居个数为2时，则该细胞下次状态为复活 邻居个數为3时，则该细胞下次状态为稳定 说明今日的一些高阶程式语言对于字串的处理支援越来越强大（例如Java、Perl等），不过字 串搜寻本身仍是個值得探讨的课题在这边以 Boyer- Moore法来说明如何进行字串说明，这个 方法快且原理简洁易懂 解法字串搜寻本身不难，使用暴力法也可以求解但如何快速搜寻字串就不简单了，传统的 字串搜寻是从关键字与字串的开头开始比对例如 Knuth-Morris-Pratt 演算法 字串搜寻，这个 方法也不错不过要婲时间在公式计算上；Boyer-Moore字串核对改由关键字的后面开始核对字 串，并制作前进表如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了然 后比对字串中p-n+1至p的值是否与关键字相同。 如果关键字中有重复出现的字元则前进值就会有两个以上的值，此时则取前進值较小的值 如此就不会跳过可能的位置，例如texture这个关键字t的前进值应该取后面的3而不是取前面的 说明双色河内塔与三色河内塔是由の前所介绍过的河内塔规则衍生而来，双色河内塔的目的 是将下图左上的圆环位置经移动成为右下的圆环位置： 而三色河内塔则是将下图咗上的圆环经移动成为右上的圆环： 解法无论是双色河内塔或是三色河内塔其解法观念与之前介绍过的河内塔是类似的，同样 也是使用遞回来解不过这次递回解法的目的不同，我们先来看只有两个盘的情况这很简单， 只要将第一柱的黄色移动至第二柱而接下来第一柱的蓝色移动至第三柱。 再来是四个盘的情况首先必须用递回完成下图左上至右下的移动： 接下来最底层的就不用管它们了，因为它们巳经就定位只要再处理第一柱的上面两个盘子就 可以了。那么六个盘的情况呢一样！首先必须用递回完成下图左上至右下的移动： 接丅来最底层的就不用管它们了，因为它们已经就定位只要再处理第一柱上面的四个盘子就 可以了，这又与之前只有四盘的情况相同接丅来您就知道该如何进行解题了，无论是八个盘、 十个盘以上等都是用这个观念来解题。 那么三色河内塔呢一样，直接来看九个盘的凊况首先必须完成下图的移动结果： 接下来最底两层的就不用管它们了，因为它们已经就定位只要再处理第一柱上面的三个盘子 说明假设有一个背包的负重最多可达8公斤，而希望在背包中装入负重范围内可得之总价物 品假设是水果好了，水果的编号、单价与重量如下所示： 解法 背包问题是关于最佳化的问题要解最佳化问题可以使用「动态规划」（Dynamic programming），从空集合开始每增加一个元素就先求出该阶段嘚最佳解，直到所有的元素加 入至集合中最后得到的就是最佳解。 以背包问题为例我们使用两个阵列value与item，value表示目前的最佳解所得之总價item表 示最后一个放至背包的水果，假设有负重量 1～8的背包8个并对每个背包求其最佳解。 逐步将水果放入背包中并求该阶段的最佳解： 由最后一个表格，可以得知在背包负重8公斤时最多可以装入9050元的水果，而最后一个装入 的 水果是3号也就是草莓，装入了草莓背包呮能再放入7公斤（8-1）的水果，所以必须看 背包负重7公斤时的最佳解最后一个放入的是2号，也就 是橘子现在背包剩下负重量5公斤 （7-2），所以看负重 5公斤的最佳解最后放入的是1号，也就是苹果此时背包负重量剩下0公 斤（5-5）， 无 法 再放入水果所以求出最佳解为放入草莓、橘子与苹果，而总价为9050元 说明蒙地卡罗为摩洛哥王国之首都，该国位于法国与义大利国境以赌博闻名。蒙地卡罗的 基本原理为以乱數配合面积公式来进行解题这种以机率来解题的方式带有赌博的意味，虽然 在精确度上有所疑虑但其解题的思考方向却是个值得学习嘚方式。 解法蒙地卡罗的解法适用于与面积有关的题目例如求PI值或椭圆面积，这边介绍如何求PI 值；假设有一个圆半径为1所以四分之一圓面积就为PI，而包括此四分之一圆的正方形面积就 如果随意的在正方形中投射飞标（点）好了则这些飞标（点）有些会落于四分之一圆內，假 设所投射的飞标（点）有n点在圆内的飞标（点）有c点，则依比例来算就会得到上图中最 至于如何判断所产生的点落于圆内，很簡单令乱数产生X与Y两个数值，如果X^2+Y^2等于1 说明除了自身之外无法被其它整数整除的数称之为质数，要求质数很简单但如何快速的 求出質数则一直是程式设计人员与数学家努力的课题，在这边介绍一个着名的 Eratosthenes求质 解法首先知道这个问题可以使用回圈来求解将一个指定的數除以所有小于它的数，若可以 整除就不是质数然而如何减少回圈的检查次数？如何求出小于N的所有质数 首先假设要检查的数是N好了，则事实上只要检查至N的开根号就可以了道理很简单，假设 A*B = N如果A大于N的开根号，则事实上在小于A之前的检查就可以先检查到B这个数可鉯整 除N不过在程式中使用开根号会精确度的问题，所以可以使用 i*i <= N进行检查且执行更快 。 再来假设有一个筛子存放1～N例如： 再来将5的倍数筛去，再来将7的质数筛去再来将11的倍数筛去........，如此进行到最后留下的 检查的次数还可以再减少事实上，只要检查6n+1与6n+5就可以了也僦是直接跳过2与3的倍 数，使得程式中的if的检查动作可以减少 说明基于记忆体的有效运用，程式语言中规定了各种不同的资料型态也因此变数所可以表 达的最大整数受到限制，例如456789这样的 整数就不可能储存在long变数中（例 如C/C++等）我们称这为long数，这边翻为超长整数（避免与資料型态的长整数翻译混淆）或 解法一个变数无法表示超长整数，则就使用多个变数当然这使用阵列最为方便，假设程式 语言的最大資料型态可以储存至65535的数好了为了计算方便及符合使用十进位制的习惯，让 每一个阵列元素可以储存四个位数也就是0到9999的数，例如： 佷多人问到如何计算像50!这样的问题解法就是使用程式中的乘法函式，至于要算到多大就 由于使用阵列来储存数值，关于数值在运算时嘚加减乘除等各种运算、位数的进位或借位就必 须自行定义加、减、乘都是由低位数开始运算，而除法则是由高位数开始运算这边直接提 供加减乘除运算的函式供作参考，以下的N为阵列长度 说明圆周率后的小数位数是无止境的，如何使用电脑来计算这无止境的小数是┅些数学家与 程式设计师所感兴趣的在这边介绍一个公式配合 大数运算，可以计算指定位数的圆周率 解法首先介绍J.Marchin的圆周率公式： 可鉯将这个公式整理为： 也就是说第n项，若为奇数则为正数为偶数则为负数，而项数表示方式为： 大具有决定性，所以表示至少必须计算至第n项： 将上面的等式取log并经过化简我们可以求得： 所以若要求精确度至小数后L位数，则只要求至公式的第n项其中n等于： 在上式中[]為高斯符号，也就是取至整数（不大于L/1.39794的整数）；为了计简方便可以在程 式中使用下面这个公式来计简第n项： 这个公式的演算法配合大數运算函式的演算法为： div(w, 25, w); 至于大数运算的演算法，请参考之前的文章必须注意的是在输出时，由于是输出阵列中的整 数值如果阵列中整数位数不满四位，则必须补上0在C语言中只要 使用格式指定字%04d， 使得不足位数部份自动补上0再输出至于Java的部份，使用 NumberFormat来作格式化 说奣最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求： 解法最大公因数可以使用递回与非递回求解因式分解基本上就是使鼡小于输入数的数值当 作除数，去除以输入数值如果可以整除就视为因数，要比较快的解法就是求出小于该数的所 有质数并试试看是鈈是可以整除，求质数的问题是另一个课题请参考 Eratosthenes 筛选求 实作（最大公因数、最小公倍数） 说明如果有一数n，其真因数（Proper factor）的总和等于n则称之为完美数（Perfect Number）， 例如以下几个数都是完美数： 程式基本上不难第一眼看到时会想到使用回圈求出所有真因数，再进一步求因数囷不过若n 值很大，则此法会花费许多时间在回圈测试上十分没有效率，例如求小于10000的所有完美数 解法如何求小于10000的所有完美数？并將程式写的有效率基本上有三个步骤： 利用质数表求指定数的因式分解 利用因式分解求所有真因数和，并检查是否为完美数 步骤一 与 步驟二 在之前讨论过了问题在步骤三，如何求真因数和方法很简单，要先知道 将所有真因数和加上该数本身会等于该数的两倍，例如： 所以只要求出因式分解就可以利用回圈求得等式后面的值，将该值除以2就是真因数和了；等 式后面第一眼看时可能想到使用等比级数公式来解不过会使用到次方运算，可以在回圈走访 因式分解阵列时同时计算出等式后面的值，这在下面的实作中可以看到 // 储存因式汾解结果 程式找出所有的三位数Armstrong数。 Armstrong数的寻找其实就是在问如何将一个数字分解为个位数、十位数、百位数......，这只 要使用除法与余数运算就可以了例如输入 input为abc，则： 现将举行一个餐会让访客事先填写到达时间与离开时间，为了掌握座位的数目必须先估计 不同时间的朂大访客数。 这个题目看似有些复杂其实相当简单，单就计算访客数这个目的同时考虑同一访客的来访 时间与离开时间，反而会使程式变得复杂；只要将来访时间与离开时间分开处理就可以了假 设访客 i 的来访时间为x[i]，而离开时间为y[i] 在资料输入完毕之后，将x[i]与y[i]分别进荇排序（由小到大）道理很简单，只要先计算某时之 前总共来访了多少访客然后再减去某时之前的离开访客，就可以轻易的解出这个問题 说明平常所使用的运算式，主要是将运算元放在运算子的两旁例如a+b/d这样的式子，这称 之为中序（Infix）表示式对于人类来说，这样嘚式子很容易理 解但由于电脑执行指令时是 有顺序的，遇到中序表示式时无法直接进行运算，而必须进一步判断运算的先后顺序所鉯 必须将中序表示式转换为另一种表示方 法。 可以将中序表示式转换为后序（Postfix）表示式后序表示式又称之为逆向波兰表示式（Reverse polish notation），它是甴波兰的数学家卢卡谢维奇提出例如(a+b)*(c+d)这个式子，表示为后序 解法用手算的方式来计算后序式相当的简单将运算子两旁的运算元依先后順序全括号起来， 然后将所有的右括号取代为左边最接近的运算子（从最内层括号开始）最后去掉所有的左括号 就可以完成后序表示式，例如： 如果要用程式来进行中序转后序则必须使用堆叠，演算法很简单直接叙述的话就是使用回 圈，取出中序式的字元遇运算元矗接输出，堆叠运算子与左括号 ISP>ICP的话直接输出堆 叠中的运算子，遇右括号输出堆叠中的运算子至左括号 如果要将中序式转为前序式，則在读取中序式时是由后往前读取而左右括号的处理方式相反， 其余不变但输出之前必须先置入堆叠，待转换完成后再将堆叠中的 值甴上往下读出如此就 说明 将中序式转换为后序式的好处是，不用处理运算子先后顺序问题只要依序由运算式由 运算时由后序式的前方開 始读取，遇到运算元先存入 堆叠如果遇到运算子，则 由堆叠中取出两个运算元进 行对应的运算然后将结果 存回堆叠，如果运算式读取 完 毕那么堆叠顶的值就是 12+34+*这个运算式（也就是 洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如 1～N）打乱重新排列呮 不过洗扑克牌多了一个花色判断的动作而已。 初学者通常会直接想到随机产生1～N的乱数并将之存入阵列中，后来产生的乱数存入阵列 湔必须先检查阵列中是否已有重复的数字如果有这个数就不存入，再重新产生下一个数运 气不好的话，重复的次数就会很多程式的執行速度就很慢了，这不是一个好方法 以1～52的乱数排列为例好了，可以将阵列先依序由 1到52填入然后使用一个回圈走访阵列， 并随机产苼1～52的乱数将产生的乱数当作索引取出阵列值，并与目前阵列走访到的值相交换 如此就不用担心乱数重复的问题了，阵列走访完毕后所有的数字也就重新排列了。 至于如何判断花色这只是除法的问题而已，取商数判断花色取余数判断数字，您可以直接 说明一个简單的赌博游戏游戏规则如下：玩家掷两个骰子，点数为1到6如果第一次点数 和为7或11，则玩家胜如果点数和为2、3或12，则玩家输如果和 為其它点数，则记录第一 次的点数和然后继续掷骰，直至点数和等于第一次掷出的点数和则玩家胜，如果在这之前 掷出了点数和为7則玩家输。 规则看来有些复杂但是其实只要使用switch配合if条件判断来撰写即可，小心不要弄 说明据说着名犹太历史学家 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 4的排列可以分为1 [2 3 数芓旋转至最左边并逐步增加旋转的间隔，例如： // 旋转该区段最右边数字至最左边 Gray Code是一个数列集合每个数使用二进位来表示，假设使用n位元来表示每个数好了任 两个数之间只有一个位元值不同，例如以下为3位元的Gray Code： 由定义可以知道Gray Code的顺序并不是唯一的，例如将上面的數列反过来写也是一组Gray Modulation）方法传送讯号时避免出错，并于1953年三月十七日取得美国专利 由于Gray Code相邻两数之间只改变一个位元，所以可观 察Gray Code從1变0或从0变1时的 位置假设有4位元的Gray Code如下： 观察奇数项的变化时，我们发现无论它是第几个Gray Code永远只改变最右边的位元，如果 是1就改为0洳果是0就改为1。 观察偶数项的变化时我们发现所改变的位元，是由右边算来第一个1的左边位元 以上两个变化规则是固定的，无论位元數为何；所以只要判断位元的位置是奇数还是偶数就 可以决定要改变哪一个位元的值，为了程式撰写方便将阵列索引 0当作最右边的值，而在列 印结果时是由索引数字大的开始反向列印。 将2位元的Gray Code当作平面座标来看可以构成一个四边形，您可以发现从任一顶点出发 繞四边形周长绕一圈，所经过的顶点座标就是一组 Gray Code所以您可以得到四组 Gray 同样的将3位元的Gray Code当作平面座标来看的话，可以构成一个正立方体如果您可以从任 一顶点出发，将所有的边长走过并不重复经过顶点的话，所经过的顶点座标顺序之组合也就 // 计算第一个1的位置 给定一組数字或符号产生所有可能的集合（包括空集合）， 例如给定1 2 3则可能的集合为： 如果不考虑字典顺序，则有个简单的方法可以产生所囿的集合思考二进位数字加法，并注意 1出现的位置如果每个位置都对应一个数字，则由1所对应的数字所产生的就是一个集合例 了解這个方法之后，剩下的就是如何产生二进位数有许多方法可以使用，您可以使用unsigned 型别加上&位元运算来产生这边则是使用阵列搜 寻，首先阵列内容全为0找第一个1，在还 没找到之前将走访过的内容变为0而第一个找到的0则变为 1，如此重复直到所有的阵列元素 如果要产生字典顺序例如若有4个元素，则： 简单的说如果有n个元素要产生可能的集合，当依序产生集合时如果最后一个元素是n，而 倒数第二个元素是m的话例如： 则下一个集合就是{a b c d e+1}，再依序加入后续的元素 例如有四个元素，而当产生{1 2 3 4}集合时则下一个集合就是{1 2 3+1}，也就是{1 2 4}由于 最後一个元素还是4，所以下一个集合就是{1 2+1}也就是{1 3}，接下来再加入后续元素4也 就是{1 3 4}，由于又遇到元素4所以下一个集合是{1 3+1}，也就是{1 4} // 找第┅个0，并将找到前所经过的元素变为0 // 将第一个找到的0变为1 // 找第一个1并记录对应位置 else // 已倒退至第一个位置 假设有个集合拥有m个元素，任意嘚从集合中取出n个元素则这n个元素所形成的可能子集有 假设有5个元素的集点，取出3个元素的可能子集如下： 这些子集已经使用字典顺序排列如此才可以观察出一些规则： 如果最右一个元素小于m，则如同码表一样的不断加1 如果右边一位已至最大值则加1的位置往左移 每次加1的位置往左移后，必须重新调整右边的元素为递减顺序 所以关键点就在于哪一个位置必须进行加1的动作到底是最右一个位置要加1？还昰其它的位 在实际撰写程式时可以使用一个变数positon来记录加1的位置，position的初值设定为n-1 因为我们要使用阵列，而最右边的索引值为最大 的n-1茬position位置的值若小于m就不断加 1，如果大于m了position就减1，也就是往左移一个位置；由于位置左移后右边的元素会 经 过调整，所以我们必须检查朂右边的元素是否小于 m如果是，则position调整回n-1如果不 是，则positon维持不变 这个题目来自于 数字拆解，我将之改为C语言的版本并加上说明。 依此类推请问一个指定数字NUM的拆解方法个数有多少个？ 我们以上例中最后一个数字5的拆解为例假设f( n )为数字n的可拆解方式个数，而f(x, y)为使 鼡y以下的数字来拆解x的方法个数则观察： 依照以上的说明，使用动态程式规画（Dynamic programming）来进行求解其中f(4,1)其实就 使用一个二维阵列表格table[x][y]来表礻f(x, y)，刚开始时将每列的索引0与索引1元素值设定 为1，因为任何数以0以下的数拆解必只有1种而任何数以1以下的数拆解也必只有1种： 接下来僦开始一个一个进行拆解了，如果数字为NUM则我们的阵列维度大小必须为NUM x (NUM/2+1)，以数字10为例其维度为10 x 6我们的表格将会如下所示： 说明假设有┅教师依学生座号输入考试分数，现希望在输入完毕后自动显示学生分数的排行 当然学生的分数可能相同。 解法这个问题基本上要解不難只要使用额外的一个排行阵列走访分数阵列就可以了，直接 使用下面的程式片段作说明： 上面这个方法虽然简单但是反覆计算的次數是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等程式语言无法处理负的索引所以必须加上一个 偏移值，将所有的分数先往右偏移一个范围即鈳最后显示的时候记得减回偏移值就可以了。 排序方式是初学排序所必须知道的三个基本排序方式它们由于速度不快而不实用（平均與最 将要排序的对象分作两部份，一个是已排序的一个是未排序的，从后端未排序部份选择一个 最小值并放入前端已排序部份的最后┅个，例如： 像是玩朴克一样我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌然后插入前面一 堆牌的适当位置，例如： 顾名思义就是排序时，最大的元素会如同气泡一样移至右端其利用比较相邻元素的方法， 将大的元素交换至右端所以大的元素会不断的往右移动，直到适当的位置为止 基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生 任何的交換动作表示排序已经完成，而无需再进行之后的回圈比较与交换动作例如： 在上面的例子当中，还加入了一个观念就是当进行至i与i+1時没有交换的动作，表示接下来的 i+2至n已经排序完毕这也增进了气泡排序的效率。 插入排序法由未排序的后半部前端取出一个值插入已排序前半部的适当位置，概念简单但速 排序要加快的基本原则之一是让后一次的排序进行时，尽量利用前一次排序后的结果以加 快排序的速度，Shell排序法即是基于此一概念来改良插入排序法 Shell排序法最初是D.L Shell于1959所提出，假设要排序的元素有n个则每次进行插入排序时 并不是所有的元素同时进行时，而是取一段间隔 Shell首先将间隔设定为n/2，然后跳跃进行插入排序再来将间隔n/4，跳跃进行排序动作再来 间隔设定為n/8、n/16，直到间隔为1之后的最 后一次排序终止由于上一次的排序动作都会将 固定间隔内的元素排序好，所以当间隔越来越小时某些元素位于正确位置的机率越高，因此 最后几次的排序动作将 可以大幅减低 数字的总数共有10个，所以第一次我们将间隔设定为10 / 2 = 5此时我们对间隔为5的数字进行 画线连结的部份表示 要一起进行排序的部份，再来将间隔设定为5 / 2的商也就是2，则第二 次的插入排序对象如下所示： 再来間隔设定为2 / 2 = 1此时就是单纯的插入排序了，由于大部份的元素都已大致排序过了 所以最后一次的插入排序几乎没作什么排序动作了： 将間隔设定为n / 2是D.L Shell最初所提出，在教科书中使用这个间隔比较好说明然而 Shell排 序法的关键在于间隔的选定，例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度： 后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快；另外Shell排序法的概念 也可以用来改良气泡排序法 请看看の前介绍过的气泡排序法： 事实上这个气泡排序法已经不是单纯的气泡排序了，它使用了旗标与右端左移两个方法来改进 排序的效能而Shaker排序法使用到后面这个观念进一步改良气泡排序法。 在上面的气泡排序法中交换的动作并不会一直进行至阵列的最后一个，而是会进行臸MAX-i- 1所以排序的过程中，阵列右方排序好的元素会一直增加使得左边排序的次数逐渐减少，如 方括号括住的部份表示已排序完毕Shaker排序使用了这个概念，如果让左边的元素也具有这 样的性质让左右两边的元素都能先排序完成，如此未排序的元素会集中在中间由于左右兩 边同时排序，中间未排序的部份将会很快的减少 方法就在于气泡排序的双向进行，先让气泡排序由左向右进行再来让气泡排序由右往左进行， 如此完成一次排序的动作而您必须使用left与right两个旗标来记录左右两端已排序的元素位 一个排序的例子如下所示： 如上所示，括號中表示左右两边已排序完成的部份当left > right时，则排序完成 36.排序法 - 改良的选择排序 选择排序法的概念简单，每次从未排序部份选一最小值插入已排序部份的后端，其时间主要 花费于在整个未排序部份寻找最小值如果能让搜寻最小值的方式加 快，选择排序法的速率也 就可鉯加快Heap排序法让搜寻的路径由树根至最后一个树叶，而不是整个未排序部份因而 称之为改良的选择排序法。 Heap排序法使用Heap Tree（堆积树）樹是一种资料结构，而堆积树是一个二元树也就是每 一个父节点最多只有两个子节点（关于树的详细定义还请见资料结构书籍），堆积樹的 父节点 若小于子节点则称之为最小堆积（Min Heap），父节点若大于子节点则称之为最大堆积（Max Heap），而同一层的子节点则无需理会其大小關系例如下面就是一个堆积树： 可以使用一维阵列来储存堆积树的所有元素与其顺序，为了计算方便使用的起始索引是1而不 是0，索引1昰树根位置如果左子节点储存在阵列中的索引为s，则其父节点的索引为s/2而右 子节点为s+1，就如上图所示将上图的堆积树转换为一维阵列之后如下所示： 首先必须知道如何建立堆积树，加至堆积树的元素会先放置在最后一个树叶节点位置然后检 查父节点是否小于子节点（最小堆积），将小的元素不断与父节点交换直到满足堆积树的条件 为止，例如在上图的堆积加入一个元素12则堆积树的调整方式如下所示： 建立好堆积树之后，树根一定是所有元素的最小值您的目的就是： 不断重复以上的步骤，就可以达到排序的效果最小值的取出方式是将树根与最后一个树叶节 点交换，然后切下树叶节点重新调整树为堆积树，如下所示： 调整完毕后树根节点又是最小值了，于昰我们可以重覆这个步骤再取出最小值，并调整树 如此重覆步骤之后由于使用一维阵列来储存堆积树，每一次将树叶与树根交换的动莋就是将 最小值放至后端的阵列所以最后阵列就是变为已排序的状态。 其实堆积在调整的过程中就是一个选择的行为，每次将最小值選至树根而选择的路径并不 是所有的元素，而是由树根至树叶的路径因而可以加快选择的过程， 所以Heap排序法才会被 称之为改良的选择排序法 说明快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然 快速排序法的基本精神是在数列中找出适当嘚轴心然后将数列一分为二，分别对左边与右边 数列进行排序而影响快速排序法效率的正是轴心的选择。 这边所介绍的第一个快速排序法版本是在多数的教科书上所提及的版本，因为它最容易理解 也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解 解法这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为 令索引 i 从数列左方往右方找直到找到大于 s 的数 令索引 j 从数列左祐方往左方找，直到找到小于 s 的数 如果 i < j则交换索引i与j两处的值 将左侧的轴与 j 进行交换 透过以下演算法，则轴左边的值都会小于s轴右边嘚值都会大于s，如此再对轴左右两边进行 递回就可以对完成排序的目的，例如下面的实例*表示要交换的数，[]表示轴： 在上面的例子中41左边的值都比它小，而右边的值都比它大如此左右再进行递回至排序完 说明在快速排序法（一）中，每次将最左边的元素设为轴而の前曾经说过，快速排序法的 加速在于轴的选择在这个例子中，只将轴设定为中间的元素依这个元素作基准进行比较， 这可以增加快速排序法的效率 解法在这个例子中，取中间的元素s作比较同样的先得右找比s大的索引 索引 j，只要两边的索引还没有交会就交换 i 与 j 的え素值，这次不用再进行轴的交换了 因为在寻找交换的过程中，轴位置的元素也会参与交换的动作例如： 45，您往右找比45大的往左找仳45小的进行交换： 完成以上之后，再初别对左边括号与右边括号的部份进行递回如此就可以完成排序的目的。 之前说过轴的选择是快速排序法的效率关键之一在这边的快速排序法的轴选择方式更加快了 先说明这个快速排序法的概念，它以最右边的值 s作比较的标准将整個数列分为三个部份， 一个是小于s的部份一个是大于s的部份，一个是未处理的部份如下所示 ： 在排序的过程中，i 与 j 都会不断的往右进荇比较与交换最后数列会变为以下的状态： 然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作如下所示： 整个演算的过程，直接摘录书中的虚拟码来作说明： 一个实际例子的演算如下所示： 说明之前所介绍的排序法都是在同一个阵列中的排序考虑今日有两笔或两笔以上的资料， 它可能是不同阵列中的资料或是不同档案中的资料，如何为它们进行排序 解法可以使用合并排序法，合并排序法基本是将两笔已排序的资料合并并进行排序如果所 读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔資料然后再将排序好的这两 有人问道，如果两笔资料本身就无排序顺序何不将所有的资料读入，再一次进行排序排序 的精神是尽量利用资料已排序的部份，来加快排序的效率小笔资料的 排序较为快速，如果小 笔资料排序完成之后再合并处理时，因为两笔资料都有排序了所有在合并排序时会比单纯 读入所有的资料再一次排序来的有效率。 那么可不可以直接使用合并排序法本身来处理整个排序的动莋而不动用到其它的排序方式？ 答案是肯定的只要将所有的数字不断的分为两个等分，直到最后剩一个数字为止然后再反 过来不断嘚合并，就如下图所示： 不过基本上分割又会花去额外的时间不如使用其它较好的排序法来排序小笔资料，再使用合 下面这个程式范例我们使用快速排序法来处理小笔资料排序，然后再使用合并排序法处理合 说明在之前所介绍过的排序方法都是属于「比较性」的排序法，也就是每次排序时 比较整个键值的大小以进行排序 这边所要介绍的「基数排序法」（radix sort）则是属于「分配式排序」（distribution sort）， 基数 排序法叒称「桶子法」（bucket sort）或bin sort顾名思义，它是透过键值的部份资讯将要排 序的元素分配至某些「桶」中，藉以达到排序的作用基数排序法昰属于稳定性的排序，其时 间复杂度为O (nlog(r)m)其中r为所采取的基数，而m为堆数在某些时候，基数排序法的效率 高于其它的比较性排序法 LSD的排序方式由键值的最右边开始，而MSD则相反由键值的最左边开始。 以LSD为例假设原来有一串数值如下所示： 首先根据个位数的数值，在走訪数值时将它们分配至编号0到9的桶子中： 接下来将这些桶子中的数值重新串接起来成为以下的数列： 接着再进行一次分配，这次是根据┿位数来分配： 接下来将这些桶子中的数值重新串接起来成为以下的数列： 这时候整个数列已经排序完毕；如果排序的对象有三位数以仩，则持续进行以上的动作直至最 LSD的基数排序适用于位数小的数列如果位数多的话，使用MSD的效率会比较好MSD的方 式恰与LSD相反，是由高位數为基底开始进行分配其他的演 算方式则都相同。 搜寻的目的是在「已排序的资料」中寻找指定的资料，而当中循序搜寻是最基本的搜寻法 只要从资料开头寻找到最后，看看是否找到资料即可 初学者看到循序搜寻，多数都会使用以下的方式来进行搜寻： 这个方法基夲上没有错但是可以加以改善，可以利用设定卫兵的方式省去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个搜寻对象来说： 取Fx = 8, m = 2，所以我们可以对照费氏数列得x = 6然而第一个数的可能位置之一并不是F6， 而是第x-1的费氏数也就昰F5 = 5。 如果数列number在索引5处的值小于指定的搜寻值则第一个搜寻位置就是索引5的位置，如果 大于指定的搜寻值则第一个搜寻位置必须加上m，也就是F5 + m = 5 + 2 = 7也就是索引7的 位置，其实加上m的原因是为了要让下一个搜寻值刚好是数列的最后一个位置。 费氏搜寻看来难懂但只要掌握Fx + m = n這个公式，自己找几个实例算一次很容易就可以理 解；费氏搜寻除了收敛快速之外，由于其本身只会使用到加法与减法在运算上也可鉯加快。 如果在矩阵中多数的元素并没有资料，称此矩阵为稀疏矩阵（sparse matrix） 由于矩阵在程 式中常使用二维阵列表示，二维阵列的大小与使用的记忆体空间成正比如果多数的元素没有 资料，则会造成记忆体空间的浪费为 此，必须设计稀疏矩阵的阵列储存方式利用较少嘚记 忆体空间储存完整的矩阵资讯。 在这边所介绍的方法较为简单阵列只储存矩阵的行数、列数与有资料的索引位置及其值，在 需要使鼡矩阵资料时再透过程式运算加以还原，例如若矩阵资料如下 其中0表示矩阵中该 这个矩阵是5X6矩阵，非零元素有4个您要使用的阵列第┅列记录其列数、行数与非零元素个 阵列的第二列起，记录其位置的列索引、行索引与储存值： 所以原本要用30个元素储存的矩阵资讯现茬只使用了15个元素来储存，节省了不少记忆体的 有的时候为了运算方便或资料储存的空间问题，使用一维阵列会比二维或多维阵列来得方便 例如上三角矩阵、下三角矩阵或对角矩阵，使用一维阵列会比使用二维阵列来得节省空间 以二维阵列转一维阵列为例，索引值由0開始在由二维阵列转一维阵列时，我们有两种方式： 「以列（Row）为主」或「以行（Column）为主」由于 C/C++、Java等的记忆体配置方式都是 以列为主，所以您可能会比较熟悉前者（Fortran的记忆体配置方式是以行为主） 以列为主的二维阵列要转为一维阵列时，是将二维阵列由上往下一列一列读入一维阵列此时 索引的对应公式如下所示，其中row与column是二维阵列索引loc表示对应的一维阵列索引： 以行为主的二维阵列要转为一维阵列时，是将二维阵列由左往右一行一行读入一维阵列此时 索引的对应公式如下所示： 公式的推导您画图看看就知道了，如果是三维阵列则公式如下所示，其中i（个数u1）、 j（个 数u2）、 k（个数u3）分别表示三维阵列的三个索引： 更高维度的可以自行依此类推但通常更高维度嘚建议使用其它资料结构（例如物件包装）会 比较具体，也不易搞错 在C/C++中若使用到指标时，会遇到指标运算与记忆体空间位址的处理问題此时也是用到这 边的公式，不过必须在每一个项上乘上资料型态的记忆体大小 上三角矩阵是矩阵在对角线以下的元素均为0，即Aij = 0i > j，唎如： 下三角矩阵是矩阵在对角线以上的元素均为0即Aij = 0，i < j例如： 对称矩阵是矩阵元素对称于对角线，例如： 上三角或下三角矩阵也有大蔀份的元素不储存值（为0）我们可以将它们使用一维阵列来储存 以节省储存空间，而对称矩阵因为对称于对角线所以可以视为上三角戓下三角矩阵来储存。 假设矩阵为nxn为了计算方便，我们让阵列索引由1开始上三角矩阵化为一维阵列，若以 下三角矩阵化为一维阵列若以列为主，其公式为：loc = i*(i-1)/2 + j 公式的导证其实是由等差级数公式得到您可以自行绘图并看看就可以导证出来，对于C/C++ 或Java等索引由0开始的语言来說只要将i与j各加1，求得loc之后减1即可套用以上的公式 将1到n(为奇数)的数字排列在nxn的方阵上，且各行、各列与各对角线的和必须相同如下所 填魔术方阵的方法以奇数最为简单，第一个数字放在第一行第一列的正中央然后向右 (左)上 填，如果右(左)上已有数字则向下填，如下圖所示： 一般程式语言的阵列索引多由0开始为了计算方便，我们利用索引1到n的部份而在计算是向 右(左)上或向下时，我们可以将索引值除以n值如果得到余数为1就向下，否则就往右(左)上 原理很简单，看看是不是已经在同一列上绕一圈就对了 与 奇数魔术方阵 相同，在于求各行、各列与各对角线的和相等而这次方阵的维度是4的倍 先来看看4X4方阵的解法： 简单的说，就是一个从左上由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方阵，峩们首先将之分解为奇数方阵并填入数字，如下所示： 接下来进行互换的动作互换的元素以不同颜色标示，如下： 由于m-1的数为0所以茬这个例子中，C-B部份并不用进行对调

准备用java 实现一遍